
Boost : 
From: John Britton (johnb_at_[hidden])
Date: 20001009 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/
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk