Re: [boost] Graph library connected_components usage

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-07-24 13:55:29

Hi Rob,

On Tue, 24 Jul 2001, Rob Smallshire wrote:
> Q1:
>
> Compiling the following two lines:
>
> std::vector<int> component(boost::num_vertices(G));
> int num = boost::connected_components(G, &component[0]);

Could you show my what type G is. A small compilable program example
demonstrating the problem would be best.

> Q2.
>
> Is it possible to use an internal property map with this algorithm ?
> I don't like using an arbitrary mix of internal and external maps.

Yes.

> I tried to define a new property:
>
> I want to be able to write something like :
>
> int num = boost::connected_components(G, component);
>
> but I can't work out what the syntax is.

It looks like you've got it right. The following program worked for me
on g++:

#include <boost/config.hpp>
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>

using namespace std;

struct component_t
{
   enum { num = 4564 };
   typedef boost::vertex_property_tag kind;
};

typedef boost::property<component_t, int>
  VertexComponentProperty;

typedef boost::adjacency_list <boost::vecS, boost::vecS,
boost::undirectedS,
  VertexComponentProperty> Graph;

typedef boost::property_map<Graph, component_t>::type
  ComponentPropertyMap;

int main(int , char* [])
{
  using namespace boost;
  {

    Graph G;
    add_edge(0, 1, G);
    add_edge(1, 4, G);
    add_edge(4, 0, G);
    add_edge(2, 5, G);

    ComponentPropertyMap component = boost::get(component_t(), G);
    int num = connected_components(G, component);

    std::vector<int>::size_type i;
    cout << "Total number of components: " << num << endl;
    for (i = 0; i != num_vertices(G); ++i)
      cout << "Vertex " << i <<" is in component " << component[i] <<
endl;
    cout << endl;
  }
  return 0;
}

----------------------------------------------------------------------
 Jeremy Siek                        www: http://www.lsc.nd.edu/~jsiek/
 Ph.D. Candidate, IU B'ton          email: jsiek_at_[hidden]
 Summer Manager, AT&T Research      phone: [phone]
----------------------------------------------------------------------