CODEWITHSUNDEEP
c++boostdisjoint-sets
mkuse
mkuse

Reputation: 2508

Boost disjoint set

I need to make a disjoint set of the type dataum.

I have all the data in the vector as follows 

vector<dataum> S;
S.push_back( dataum(0,0) );
S.push_back( dataum(0,1) );
S.push_back( dataum(0,2) );
 .
 .

Then I create the disjoint_set 

std::vector<int>  rank (100);
std::vector<dataum>  parent (100);
boost::disjoint_sets<int*,dataum*> ds(&rank[0], &parent[0]);

for( int i=0 ; i<S.size() ; i++ )
{
    ds.make_set( S[i] );
}

This seem to not work. What am I missing? I want to create a disjoint set with custom datatype. In this case dataum. Initially each of my dataums should be in different sets.

Upvotes: 1

Views: 1370

Answers (1)

sehe
sehe

Reputation: 394054

The documentation states that

  • Rank must be a model of ReadWritePropertyMap with an integer value type and a key type equal to the set's element type.
  • Parent must be a model of ReadWritePropertyMap and the key and value type the same as the set's element type.

At your previous question I posted the following sample code in a comment:

After looking at the (new for me) disjoint_set_* classes, I don't think that they afford iterating members of sets. They act like unidirectional mapping from element to set representative. In case it helps you: http://paste.ubuntu.com/8881626 – sehe 9 hours ago

Here it is, reworked for an imagined dataum type:

struct dataum { 
    int x,y; 
    bool operator< (const dataum& o) const { return tie(x,y)  < tie(o.x,o.y); } 
    bool operator==(const dataum& o) const { return tie(x,y) == tie(o.x,o.y); } 
    bool operator!=(const dataum& o) const { return tie(x,y) != tie(o.x,o.y); } 
};

Here's how I can see a disjoint_set declaration for it:

std::map<dataum,int> rank;
std::map<dataum,dataum> parent;

boost::disjoint_sets<
    associative_property_map<std::map<dataum,int>>,
    associative_property_map<std::map<dataum,dataum>> > ds(
            make_assoc_property_map(rank),
            make_assoc_property_map(parent));

The mechanics of this are to be found in the documentation for Boost PropertyMap, which is a very powerful generic data structure abstraction layer, mostly used with Boost Graph Library. It's wildly powerful, but I can't say it's user friendly.

Here's the full demo Live On Coliru¹

#include <boost/pending/disjoint_sets.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/tuple/tuple_comparison.hpp>
#include <iostream>
#include <map>
#include <cassert>

using namespace boost;
struct dataum { 
    int x,y; 
    bool operator< (const dataum& o) const { return tie(x,y)  < tie(o.x,o.y); } 
    bool operator==(const dataum& o) const { return tie(x,y) == tie(o.x,o.y); } 
    bool operator!=(const dataum& o) const { return tie(x,y) != tie(o.x,o.y); } 
};

int main() {
    std::vector<dataum> S { {0,0}, {0,1}, {0,2} };

    std::map<dataum,int> rank;
    std::map<dataum,dataum> parent;

    boost::disjoint_sets<
        associative_property_map<std::map<dataum,int>>,
        associative_property_map<std::map<dataum,dataum>> > ds(
                make_assoc_property_map(rank),
                make_assoc_property_map(parent));

    for(auto i=0ul; i<S.size(); i++)
        ds.make_set(S[i]);

    assert((ds.count_sets(S.begin(), S.end()) == 3));
    assert((ds.find_set(dataum{0,2}) == dataum{0,2}));
    assert((ds.find_set(dataum{0,1}) == dataum{0,1}));

    ds.union_set(dataum{0,2},dataum{0,1});

    assert((ds.count_sets(S.begin(), S.end()) == 2));
    assert((ds.find_set(dataum{0,2}) == dataum{0,1}));
    assert((ds.find_set(dataum{0,1}) == dataum{0,1}));

    std::cout << "done";
}

¹ Coliru still not cooperating

Upvotes: 3

Related Questions