Boost logo

Boost :

From: jsiek_at_[hidden]
Date: 2000-07-07 19:52:37

Hi Michael,

The GGCL library has an implementation of the disjoint set algorithm
with the union by rank and path compression optimizations (see the
distjoint_set class). The algorithm used is the one described in
"Introduction to Algorithms" by Cormen, Leiserson, Rivest.

I'm currently trying to catch up with a backlog of email... so
it will take some time to catch up with the rest of the discussion
between Michael and Deitmar...



Michael S. Tsirkin writes:
> Hello!
> Does there exist a library for union/find type of problem?
> I have written a simple library that uses a forest of
> splay trees to solve this in O(NlogN), with low memory overhead.
> [This is not optimal in terms of speed, AFAIK , but memory overhead
> would have to be higher]
> The forest of splay trees class migth have other uses
> (e.g. as a replacement to "map": it has lower memory overhead
> per node as compared to the standard RB tree implementation-
> -does not need the "color" bit- while providing amortized
> O(ln N) time for operations, as opposed to O(ln N) for one
> operation in an RB tree - as usual speed/ memory tradeoff).
> It might also be useful for teaching teh data structures course :)
> My implementation is templated to allow keeping different
> types of data in the nodes, and uses STL-like iterators for access,
> to simplify the usage.
> I would like to know:
> - Does someone have another implementation , that I can compare
> with in terms of memory/speed?
> - Is someone interested in my implementation of this library?
> If yes, I think I could publish the library to teh public domain.
> Thank you,
> --
> This message content is not part of Intel's views or affairs
> Michael S. Tsirkin
> > Four things are to be strengthened: Torah,and good deeds,
> > prayer and one's good manners (Berachoth)
> ------------------------------------------------------------------------
> Where do sports heroes like Derek Jeter, Mia Hamm,
> Vince Carter and Peyton Manning hang out? Where else?
> Click now and find ‘em all here!
> ------------------------------------------------------------------------

Boost list run by bdawes at, gregod at, cpdaniel at, john at