
Boost : 
From: Rich Lee (llee1_at_[hidden])
Date: 20001009 13:17:58
One approach to test connectivity is to count number of forests.
you only need to write a visitor to count vertices started and use this
visitor to
call depth_first_search. For example the visitor is like:
struct counter {
typedef boost::on_start_vertex event_filter;
counter(int* n) : number_of_started(n) {}
template <class Vertex, class Graph>
operator()(const Vertex& u, const Graph& g) {
++(*number_of_started);
}
shared_ptr<int> number_of_started;
};
Now you can call depth_first_search like that:
int* number_of_started = new int(0);
counter count(number_of_started);
//G is a graph object.
depth_first_search(G, boost::dfs_visitor<counter>(count), color.begin());
The above approach has complexity of O(N+M), where N and W are number of
vertices and edges, respectively.
Another approach is to use depth_first_visit. You could write a visitor like
above
but counting discovered vertices this time. The event_filter should be
boost::on_discover_vertex. You may write a new algorithm to set color first,
then call depth_first_visit:
template <class Graph, class Vecrtex, class DFSVisitor vis, ColorPA color>
void connectivity_test (Graph& g, Vertex u, DFSVisitor vis, ColorPA color) {
typename property_traits<ColorPA>::value_type c = get(color, Vertex());
typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end;
for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
put(color, *ui, white(c));
vis.initialize_vertex(*ui, g);
}
vis.start_vertex(u, g);
depth_first_visit(g, u, vis, color);
}
This approach may be faster if graph is disconnected.
LieQuan Lee
> Original Message
> From: John Britton [mailto:johnb_at_[hidden]]
> Sent: Monday, October 09, 2000 12:02 PM
> To: boost_at_[hidden]
> Subject: [boost] How to do BGL simple connectiviy test
>
>
> 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