[Lemon-user] disjoint set union find

[Sven Peter]

Hi Balázs,

Thank you, that's exactly what I've been looking for!



Cheers,


Sven

On Nov 1, 2012, at 7:48 PM, Balázs Dezső <deba.mf at gmail.com> wrote:

> 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
>