[Boost-users] [BGL] boost::disjoint_set getting new representative after link()

Subject: [Boost-users] [BGL] boost::disjoint_set getting new representative after link()
From: Adi Shavit (adishavit_at_[hidden])
Date: 2013-03-21 05:07:58

Hi,

  I'm using boost::disjoint_sets_with_storage<>.
After calling link(rep1, rep2), I want to know the new rep - the
representative of the merged set.

Obviously, I can call find_set(rep1) to find it.
I assume that the extra call to find_set incurs an additional run-time cost
per call to link.
Is this true or is the call immediate (as in returning the immediate parent
of rep1)?

If it does incur a run-time cost, then we know that the new-rep is
*either *rep1
or rep2.
Is there some other way to know which one it is?

On a related matter, I am also tracking the *size *of the sets for each
link().
Does knowing the size of the rep set before the link help in determining
which of rep1 or rep2 will be the new rep?

Is there a simple way to extend boost::disjoint_sets_with_storage<> to do
the size tracking internally (currenlty I keep an external size vector per
rep to keep track of the link()s).

Thanks,
Adi