Boost logo

Boost Users :

From: Dmitry Bufistov (dmitry_at_[hidden])
Date: 2006-05-02 09:45:49

Sean Kelly wrote:
> Hi All,
> I couldn't figure out how to use the component_index facility of the
> incremental components algorithm when operating on an listS, listS
> adjecency_list so I rolled my own as per below.
> Any suggestion on how to use the provided interface are appreciated.
Hi Kelly,
A couple of weeks ago I saw a good example of "iterator_property_map"
usage in the similar situation but for connected_components() algorithm
(you need to add vertex_index property). Probably this can help you,
mainly to improve perfomance. Please, take a look on this example.

#include <boost/config.hpp>
#include <vector>
#include <map>
#include <iostream> // for std::cout
#include <algorithm> // for std::for_each
#include <boost/utility.hpp> // for boost::tie
#include <boost/graph/graph_traits.hpp> // for boost::graph_traits
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>

using namespace boost;

struct Node
  int index;
  //****color property******************************
  boost::default_color_type m_algo_color;
  //****color property******************************

struct Boundary
  double something;

typedef boost::adjacency_list<
    boost::setS, boost::listS, boost::undirectedS,
    Node, Boundary, boost::setS> Graph;

int main(int argc, char*argv[])
  Graph g(5);
  boost::graph_traits<Graph>::vertex_iterator vi, viend;
  std::vector< int > c( num_vertices(g) );
  int num;
  // manually intialize the vertex index,
  // because we have listS as vertex list type
  int n = 0;
  for (tie(vi, viend) = vertices(g); vi != viend; ++vi, ++n) {
      g[*vi].index = n;

  //****modified call******************************
  num = connected_components(g, make_iterator_property_map(c.begin(),
get(&Node::index, g)), boost::color_map( get(&Node::m_algo_color, g) ));
  //****modified call******************************
  return 0;

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at