[C++-sig] boost/pending/disjoint_sets.hpp

[Charles Harris]

This is really about boost, not boost/python, so ignore it
if it doesn't interest you.

Anyway, I have written a union-find class for my own use, but
after finding disjoint_sets I hoped to replace it with a more
standard version. I was unable to do so because of missing
functionality. Typically, I want to do the following:

1) iterate over sets.
2) iterate over set elements
3) store element properties - color, position, etc.

The set iterator is pretty easy to achieve, it is a filtered_iterator
derived from an iterator over all elements in all sets.

The set element iterator can be implemented by linking elements in a
set into a circular list. All that is needed is a sibling link in 
addition to the parent link. The lists are then merged whenever the
sets are unioned. All elements belonging to the same set as any
given element are then easily accessible.

The container properties may already be there: I haven't yet completely
understood what the template implements.

Just my $.02 .

Chuck

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/ms-tnef
Size: 3012 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/cplusplus-sig/attachments/20051023/414bc02f/attachment.bin>