From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p6S8rckC028378 for ; Thu, 28 Jul 2011 10:53:42 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Aj8EAF4jMU7BMH5JgWdsb2JhbAA1AQEFLQsBRQYSDCEiDwkDAgECAQJRFQ8BARiYK48KFAEBFiYliH4CwjyGQQSYAItf X-IronPort-AV: E=Sophos;i="4.67,281,1309730400"; d="scan'208";a="104091229" Received: from dsi-mta-out.univ-savoie.fr ([193.48.126.73]) by mail4-smtp-sop.national.inria.fr with ESMTP; 28 Jul 2011 10:53:38 +0200 Received: from localhost (localhost [127.0.0.1]) by dsi-mta-out.univ-savoie.fr (Postfix) with ESMTP id 0B514260B7 for ; Thu, 28 Jul 2011 10:53:38 +0200 (CEST) X-Virus-Scanned: Debian amavisd-new at dsi-mta-out Received: from dsi-mta-out.univ-savoie.fr ([127.0.0.1]) by localhost (dsi-mta-out.univ-savoie.fr [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id vjc8oDaHHK4A for ; Thu, 28 Jul 2011 10:53:37 +0200 (CEST) Received: from dsi-mail-msa1.univ-savoie.fr (dsi-mail-msa1.univ-savoie.fr [193.48.126.83]) by dsi-mta-out.univ-savoie.fr (Postfix) with ESMTP id E963B260AC for ; Thu, 28 Jul 2011 10:53:37 +0200 (CEST) Received: from localhost (localhost [127.0.0.1]) by dsi-mail-msa1.univ-savoie.fr (Postfix) with ESMTP id E19821C06F for ; Thu, 28 Jul 2011 10:53:37 +0200 (CEST) X-Virus-Scanned: Debian amavisd-new at dsi-mail-msa1 Received: from dsi-mail-msa1.univ-savoie.fr ([127.0.0.1]) by localhost (dsi-mail-msa1.univ-savoie.fr [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id gE9-sJJBcoTf for ; Thu, 28 Jul 2011 10:53:37 +0200 (CEST) Received: from [192.168.144.15] (bin73-1-78-240-16-62.fbx.proxad.net [78.240.16.62]) by dsi-mail-msa1.univ-savoie.fr (Postfix) with ESMTPSA id AE3B41C054 for ; Thu, 28 Jul 2011 10:53:37 +0200 (CEST) Message-ID: <4E312391.9030703@univ-savoie.fr> Date: Thu, 28 Jul 2011 10:53:37 +0200 From: Christophe Raffalli User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.18) Gecko/20110617 Lightning/1.0b2 Thunderbird/3.1.11 MIME-Version: 1.0 To: caml-list@inria.fr References: <20110727202007.GG21817@localhost> In-Reply-To: <20110727202007.GG21817@localhost> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit Subject: Re: [Caml-list] Poset variant of union-find datastructure Le 27/07/2011 22:20, Guillaume Yziquel a écrit : > 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. > Hello, I only see the graph solution (unfortunately) ... With variants: - just a graph, querying the relation requiring to traverse the graph - computing the transitive closure of the graph (relate taking more time), but querying being much faster. - computing both the transitive closure and the transitive reduction of the grap which reduce a bit the time for relate (less edges to follow). But not changing the worst case complexity, I think. I would be very happy too if there were a more efficient solution (logarithmic complexity both for relation and relate ?) Cheers, Christophe