Re: [boost] [BGL] How to stopping prematurely a graph exploration

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);

to

         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);
     Q.push(s);
     while (! Q.empty()) {
       Vertex u = Q.top(); 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);
           Q.push(v);
         } else  
{                                             vis.non_tree_edge(*ei, g);
           if (vis.is_vertex_gray(v, g))        vis.gray_target(*ei, g);
           else                                                 
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