[Caml-list] Poset variant of union-find datastructure

[Guillaume Yziquel <guillaume.yziquel@citycable.ch>]

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