Re: [Boost-users] incremental_components, component_index for listS, listS adjacency_list

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;
}