Boost logo

Boost :

Subject: Re: [boost] [BGL] How to stopping prematurely a graph exploration
From: K. Noel Belcourt (kbelco_at_[hidden])
Date: 2009-08-07 12:09:23

Hi Andrew,

On Aug 6, 2009, at 4:31 PM, Andrew Sutton wrote:

>> I combined queue emptying with marking all the vertices black to
>> ensure
>> that nothing else gets pushed into the queue. This has worked
>> fine for us.
> Hmm... recoloring is a linear operation. Maybe throwing an
> exception gives
> better performance.

I was unclear, let me explain what we did and why. Exceptions aren't
reasonable for us, we invoke, e.g. dijkstra, multiple times to search
parts of a graph with different starting vertices. We needed a way
to terminate the search very quickly and deterministically.

We started by changing (bfs line 352)

         if (v_color == Color::white()) { vis.tree_edge(*ei, g);


         if (vis.is_vertex_white(v, g)) { vis.tree_edge(*ei, g);

and added

        bool is_vertex_white(vertex_descriptor, Graph);

to the visitor.

This allows us to implement the new visitor function as:

        bool is_vertex_white(vertex_descriptor v_color, Graph) {
                return !done && v_color == Color::white;

So when our visitor detects our termination condition, we set done to
true and empty the queue. This change permits us to terminate the
algorithm as quickly as possible as the code protecting the queue
push operation is now protected.

In general, we created a new bfs algorithm, that is used with a new
default bfs color visitor. We did this so as not to compromise the
performance of existing bfs for those who know they need to traverse
the entire graph.

My suggestion would be to provide a new bfs variant that permits the
passed in visitor to implement the graph coloring / querying
operations, so users needing to terminate a search can do so by
changing the coloring functions.

We put the color stuff into a color_visitor.

        bool is_vertex_gray(vertex_descriptor, Graph);
        bool is_vertex_white(vertex_descriptor, Graph);
        void color_vertex_gray(vertex_descriptor, Graph);
        void color_vertex_black(vertex_descriptor, Graph);

and compose the new color visitor with the user's visitor. The
visitor supporting the new coloring interface is passed into a
restructured bfs that looks like this:

     vis.color_vertex_gray(s, g)); vis.discover_vertex(s, g);
     while (! Q.empty()) {
       Vertex u =; Q.pop(); vis.examine_vertex(u, g);
       for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
         Vertex v = target(*ei, g); vis.examine_edge
(*ei, g);
         if (vis.is_vertex_white(v, g)) { vis.tree_edge(*ei, g);
           vis.color_vertex_gray(v, g); vis.discover_vertex(v, g);
         } else
{ vis.non_tree_edge(*ei, g);
           if (vis.is_vertex_gray(v, g)) vis.gray_target(*ei, g);
vis.black_target(*ei, g);
       } // end for
       vis.color_vertex_black(u, g)); vis.finish_vertex(u, g);

This is what I meant by color vertices black.

-- Noel

Boost list run by bdawes at, gregod at, cpdaniel at, john at