partition.h

#ifndef SCIL_PARTITION_H
#define SCIL_PARTITION_H
#include <vector>
#include <boost/graph/graph_traits.hpp>


template<typename GraphTyp>
class Partition {
   typedef typename boost::graph_traits<GraphTyp>::vertex_descriptor vertex_descriptor;
   typedef typename boost::graph_traits<GraphTyp>::vertex_iterator vertex_iter;

public:
   Partition();
   Partition( GraphTyp& G );
   bool same_block(vertex_descriptor v, vertex_descriptor w);
   void union_blocks( vertex_descriptor v, vertex_descriptor w);
   Partition(const Partition& orig);

   template<typename T>
   friend std::ostream& operator<< (std::ostream& os, Partition<T> const& rhs);
   virtual ~Partition();

private:
   std::vector<unsigned int> block;

};

template<typename GraphTyp>
Partition<GraphTyp>::Partition(GraphTyp& G) : block( num_vertices(G) ) {
   for( unsigned int i=0; i<num_vertices(G); i++ )
      block[i] = i;
}

template<typename GraphTyp>
bool Partition<GraphTyp>::same_block(vertex_descriptor v, vertex_descriptor w) {
   return block[v]==block[w];
}

template<typename GraphTyp>
void Partition<GraphTyp>::union_blocks( vertex_descriptor v, vertex_descriptor w ) {
   for( unsigned int i=0; i<block.size(); i++ )
      if( block[i] = block[w] )
         block[i] = block[v];
}

template<typename GraphTyp>
Partition<GraphTyp>::Partition() : block(0) {
}

template<typename GraphTyp>
Partition<GraphTyp>::Partition(const Partition& orig) : block(orig.block) {
}

template<typename GraphTyp>
Partition<GraphTyp>::~Partition() {
}

template<typename T>
std::ostream& operator<< (std::ostream& os, Partition<T> const& part) {
   os << "Partition with " << part.block.size() << " elements" << std::endl;
   for( int i=0;i<part.block.size();i++)
      os << " (" << i << " <-> " << part.block[i] << ") ";
   return os << std::endl;
}

#endif  /* _PARTITION_H */

---