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 -- Caml-list mailing list. Subscription management and archives: https://sympa-roc.inria.fr/wws/info/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
