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...

Cheers,

Jeremy

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,
> MST
>
> --
> 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!
> http://click.egroups.com/1/6211/4/_/9351/_/962862200/
> ------------------------------------------------------------------------
>
>
>


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk