How to do BGL simple connectiviy test

From: John Britton (johnb_at_[hidden])
Date: 2000-10-09 12:01:37

To perform a simple connectivity test, I thought a depth_first_search,
counting the vertices discovered, would be just the ticket. After
discovering that there is no way to restrict the search to those vertices
connected to a given start vertex in depth_first_search(), I tried using
depth_first_vist() instead. Lo and behold, I discovered that
depth_first_vist() does not initialize the vertex color thingy, yielding
incorrect (for my purposes) results. (I also found that there is no version
of depth_first_vist() that can find the internal vertex color property
thingy.) I'm not sure what the most correct approach to my simple problem
is, so I though I'd inquire. I'd prefer my code not have to do color
initialization - that seems better hid in the library IMO. I'm including
some sample code, though it's not all that interesting...

/*====
is_connected.cpp
====*/
#pragma warning (disable: 4786)
#include <vector>
#include <utility>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>

typedef std::pair<int, int> edge_t;
typedef std::vector< edge_t > edge_list_t;

/*==== dfsv_count_vertices_t */
class dfsv_count_vertices_t : public boost::dfs_visitor<> {
  size_t& num_found;
public:
  dfsv_count_vertices_t( size_t& num_found )
  : num_found( num_found ) {
  }

  template < class Vertex, class Graph>
  void discover_vertex( Vertex v, Graph& g ) {
    num_found++;
  }
};

/*==== is_connected */
size_t is_connected( int num_vertices, edge_list_t& the_edges )
{
  // create a graph from the edges
  typedef boost::adjacency_list<
    boost::vecS, boost::vecS, boost::undirectedS,
    boost::property<boost::vertex_color_t, boost::default_color_type>
  > graph_t;
  graph_t g( num_vertices, the_edges.begin(), the_edges.end() );

  // perform DFS analysis, counting the vertices discovered
  size_t num_found = 0;
  boost::depth_first_visit( g, boost::vertex( 0, g ),
    dfsv_count_vertices_t( num_found ),
    boost::get( boost::vertex_color, g )
  );

  // return connected if all vertices discovered
  return num_found == num_vertices;
}

John Britton
Very Important Engineer++
Peak Audio Inc.
1790 30th Street, Suite 414
Boulder, CO 80301
303.449.9337 x102
johnb_at_[hidden]
http://www.peakaudio.com/