RE: [boost] How to do BGL simple connectiviy test

From: Rich Lee (llee1_at_[hidden])
Date: 2000-10-09 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.

Lie-Quan 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/
>
>
>
>
>