[Lemon-user] Union Find

[Pierre Moulon]

Hi,

Again me...

I have look deeper (by looking to the usage in Kruskal) and I think I have
found how use the UnionFind lemon Algorithm.
It's a great shame that a "regular" unionFind algorithm was not implemented,
because the actual implementation works only with Graphs... and not simple
type (such like int, pair<,>, Element).

I think I have to create a graph with nodes that correspond to my
pair<int,int> and use the nodeMap as set initialization.
Ie. addNode for each value of my possible pair<int,int>

"Quote""
typedef typename Digraph::template NodeMap<int> IndexMap;
typedef typename Digraph::Node Node;

IndexMap index(digraph);
UnionFind<IndexMap> uf(index);
for (typename Digraph::NodeIt it(digraph); it != INVALID; ++it) {
uf.insert(it);
}
"
And after I will join my corresponding Node according the links that I get
between my pair<int,int>.

I will try this.

Regards,
Pierre.

=> The library need unit test/usage sample for the unionFind section. => I
will try to make one once I will have understand how use it.


2011/4/5 Pierre Moulon <pmoulon at gmail.com>

> HI,
>
> Thanks Alpár for your answer.
>
> I have meet a problem.
>
> I want use UnionFind algorithm on a type like a pair<int,int> and it seems
> I cannot use it with such a type.
>
> Could you give me pointer on how I could use UnionFind to use indexed
> object ?
>
> Thanks in advance.
> Regards,
> Pierre
>
>
> 2011/4/4 Alpár Jüttner <alpar at cs.elte.hu>
>
>> On Sat, 2011-04-02 at 16:58 +0200, Pierre Moulon wrote:
>> > Hi all,
>> >
>> >
>> >
>> > The PDF documentation of Lemon talk about Union Find structure :
>> > http://lemon.cs.elte.hu/pub/doc/lemon-intro-presentation.pdf
>> >
>> >
>> > Does is yet implemented ?
>>
>> Yes, there are four different implementations (UnionFind, UnionFindEnum,
>> HeapUnionFind and ExtendFindEnum), see here:
>>
>> http://lemon.cs.elte.hu/pub/doc/1.2.1/a00527.html
>>
>> BTW, latest doc (http://lemon.cs.elte.hu/pub/doc/latest/ ) has recently
>> got a search box in the top right corner.
>>
>> > Otherwise :
>> > The lemon library is excellent. Easy to use !
>> > I will use it to perform a student course in my old school.
>> > I will use Lemon to compute the shortest path between Paris Metro
>> > stations and make understand to them what such problem could pose.
>> > From file reading, graph construction and shortest path...  they will
>> > learn a lot and understand easily what a graph is with the ease of use
>> > of Lemon...
>> >
>> > I project to make the code accessible.. with small simplification it
>> > could become if you want a tutorial inside Lemon ...
>>
>> Good idea. The Tutorial is something that really needs (and will always
>> need) to be improved.
>>
>> Regards,
>> Alpar
>>
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20110405/7893fbbc/attachment.html>