CGAL users discussion list

[Guillaume Damiand <>]

Hi,

> Greetings,
>
> I was looking on the Union_find reference manual page to see what happens
> when two sets are unified. When having a call to P.unify_sets(p,q) is 
> there
> something in the implementation that certifies if the representative 
> of the
> resulting set is e.g. always the representative of what used to be the 
> set of p?

There is no such property. Since union find uses union by rank, the 
small tree is put under the big one thus you cannot control the 
representative of the new set and keep the complexity in inverse of 
Ackermann's function.

Guillaume


> If that's the case then it should be better to state that in the 
> manual, which
> gives the ability to the user to determine himself at each 
> unify-operation
> which is going to be the representative of the new set.
>
> thanks,
>
> Constantinos


--
===================================================================
Guillaume DAMIAND

LIRIS UMR 5205
Université Claude Bernard
Bâtiment Nautibus (710)
43 Boulevard du 11 Novembre 1918
69622 Villeurbanne Cedex (France)
-------------------------------------------------------------------
Tél: +33 (0)4.72.43.26.62                 Fax: +33 (0)4.72.43.15.36
Mail: 

===================================================================