From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p6RKLqaV029246 for ; Wed, 27 Jul 2011 22:21:55 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AlADAA9zME5V2gB4h2dsb2JhbABoEz6BCgEtmQiPGAEBAQoLCQcWJYh+AqFboAEOhjIEo1k X-IronPort-AV: E=Sophos;i="4.67,278,1309730400"; d="scan'208";a="114254415" Received: from emailfrontal1.citycable.ch ([85.218.0.120]) by mail1-smtp-roc.national.inria.fr with SMTP; 27 Jul 2011 22:21:55 +0200 X-Alinto-smtpauth-localdomain: Yes Received: from seldon (unknown [85.218.93.111]) (Authenticated sender: guillaume.yziquel@citycable.ch) by emailfrontal1.citycable.ch (Postfix) with ESMTPA id 83989E640F0; Wed, 27 Jul 2011 22:21:48 +0200 (CEST) Received: from yziquel by seldon with local (Exim 4.72) (envelope-from ) id 1QmAaO-0006m0-7X; Wed, 27 Jul 2011 22:20:08 +0200 Date: Wed, 27 Jul 2011 22:20:08 +0200 From: Guillaume Yziquel To: caml-list@inria.fr Message-ID: <20110727202007.GG21817@localhost> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.5.20 (2009-06-14) Subject: [Caml-list] Poset variant of union-find datastructure Hi. I'm wondering if people on this list may have any insight as to how implement a "poset-find" datastructure much like a union-find datastructure. A typical union find signature can be found here: http://www.enseignement.polytechnique.fr/informatique/INF564/html/unionFind.mli.html The core of the signature I'm interested in is: type 'a point val fresh : 'a -> 'a point val find : 'a point -> 'a val union : 'a point -> 'a point -> unit val equivalent : 'a point -> 'a point -> bool and I'd like a similar signature like: type 'a point type rel : G | Geq | Eq | Leq | L val fresh : 'a -> 'a point val find : 'a point -> 'a val relate : rel -> 'a point -> 'a point -> unit val relation : 'a point -> 'a point -> rel option Has anybody given thought to this kind of datastructure, or is there any prior work? Or is there really no better alternative than a graph? What worries me about a graph is that I do not really perceive an efficient way to query the order between two 'a points. -- Guillaume Yziquel