[Lemon-user] disjoint set union find

[Balázs Dezső]

Hi Sven,

UnionFind is good for you, but you also need to store the representative of
the set in a vector. The indices of the union find structure are always in
the range [0, size - 1];

Data:
SmartGraph graph;
SmartGraph::NodeMap<int> union_find_ref(graph);
UnionFind<SmartGraph::NodeMap<int> > union_find(union_find_ref);
std::vector<SmartGraph::Node> representative(countNodes(graph));

....
Creation:
for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
  representative[union_find.insert(n)] = n;
}

....
Join:
union_find.join(n1, n2);
representative[union_find.find(n1)] = n1; // or any other item from the set.

....
Lookup:
rep = representative[union_find.find(n)];

I hope these code snippets will help you.

Balazs


On Wed, Oct 31, 2012 at 4:05 PM, Sven Peter <
sven.peter at stud.uni-heidelberg.de> 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.
>
> 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!
>
>
> Thanks,
>
>
> Sven
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20121101/48248e46/attachment.html>