<div>Hi Sven,<br></div><div><br></div><div>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];</div>

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

<div><br></div><div>....</div><div>Creation:</div><div>for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {</div><div>  representative[union_find.insert(n)] = n;</div><div>}</div><div><br></div><div>....</div><div>Join:</div>

<div>union_find.join(n1, n2);</div><div>representative[union_find.find(n1)] = n1; // or any other item from the set.</div><div><br></div><div>....</div><div>Lookup:</div><div>rep = representative[union_find.find(n)];</div>

<div><br></div><div>I hope these code snippets will help you.</div><div><br></div><div>Balazs</div><div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, Oct 31, 2012 at 4:05 PM, Sven Peter <span dir="ltr"><<a href="mailto:sven.peter@stud.uni-heidelberg.de" target="_blank">sven.peter@stud.uni-heidelberg.de</a>></span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi,<br>
<br>
I'm currently using the LEMON library to implement a graph algorithm and need a disjoin set union find data structure.<br>
It seems that LEMON provides an implementation of this with the UnionFind template, I am however having trouble using it.<br>
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.<br>
<br>
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.<br>
I.e., I need to first create a set for every node in the graph that only contains that single node.<br>
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.<br>
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.<br>
<br>
Could someone point me to the right direction? Some really simple example would be great!<br>
<br>
<br>
Thanks,<br>
<br>
<br>
Sven<br>
_______________________________________________<br>
Lemon-user mailing list<br>
<a href="mailto:Lemon-user@lemon.cs.elte.hu">Lemon-user@lemon.cs.elte.hu</a><br>
<a href="http://lemon.cs.elte.hu/mailman/listinfo/lemon-user" target="_blank">http://lemon.cs.elte.hu/mailman/listinfo/lemon-user</a><br>
</blockquote></div><br></div>