[Lemon-user] disjoint set union find

[Alpár Jüttner]

On Wed, 2012-10-31 at 16:05 +0100, Sven Peter wrote:
> Hi,
> 
> I'm currently using the LEMON library to implement a graph algorithm
> and need a disjoin set union find data structure. It seems that LEMON
> provides an implementation of this with the UnionFind template, I am
> however having trouble using it. Is there any more documentation
> available? All I could find was the automatically generated source code
> documentation and the kruskal source code in lemon which uses
> UnionFind.

The doc of UnionFind is here:
http://lemon.cs.elte.hu/pub/doc/1.2.3/a00366.html
It is more than just an auto generated doc.

(Btw. there are more union-find implementations (UnionFindEnum<>,
ExtendFindEnum<>, HeapUnionFind<>) with different feature sets, you
might want to check them out. See
http://lemon.cs.elte.hu/pub/doc/1.2.3/a00527.html )


> What I really need in the end is a way to handle disjoint sets of the
> nodes of the graph where the representative is a node from that set.
> I.e., I need to first create a set for every node in the graph that
> only contains that single node. Then I need a way to FIND the
> representative of any node (figure out the set the node is in; return
> the representative) and I need to merge two sets. I am currently using
> my own (rather stupid) implementation and around 50% of the time is
> spent in there, which I'd like to optimize.
> 
> Could someone point me to the right direction? Some really simple example would be great!

The UnionFind class can be used with any data type as key. It requires a
Key->int read-write map (see
http://lemon.cs.elte.hu/pub/doc/1.2.3/a00270.html ) as a template
parameter.

For graph node keys the basic usage is like this:

ListGraph::NodeMap<int> aux_map(g);
UnionFind< ListGraph::NodeMap<int> > uf(aux_map);

//Insert the nodes (as much as you want):
for(ListGraph::NodeIt n(g);n!=INVALID;++n)
  uf.insert(n);

ListGraph::Node a,b;
...
//Join the component of a and b
uf.join(a,b)

//Check if two elements are in the same component
if(uf.find(a)==uf.find(b)) {}

etc.

UnionFindEnum<> can also list the component and the elements of each
components, at the cost of being slower and using more memory.

Regards,
Alpar