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

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

[Guillaume Yziquel]

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

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

[Christophe Raffalli]

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
 

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

[Guillaume Yziquel]

Le Thursday 28 Jul 2011 à 10:53:37 (+0200), Christophe Raffalli a écrit :
> 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
>
> Hello,
>  
> I only see the graph solution (unfortunately) ... With variants:
> 
> I would be very happy too if there were a more efficient solution
> (logarithmic complexity both for relation and relate ?)

The most relevant paper I could find on the topic is the following:

	http://www.siam.org/proceedings/soda/2009/SODA09_044_daskalakisc.pdf

> Cheers,
> Christophe

Best regards,

-- 
     Guillaume Yziquel

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

[Radu Grigore]

On Wednesday, July 27, 2011 9:22:16 PM UTC+1, Guillaume Yziquel wrote:
> 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.

What you want is known as "dynamic transitive closure" or, more precisely, "incremental transitive closure." See, for example,
  http://scholar.google.co.uk/scholar?cluster=2214623839872244490
as a starting point.