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 13:44:59

On Aug 7, 2009, at 10:09 AM, K. Noel Belcourt wrote:

> 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:
>

Of course, this:

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

should read:

        bool is_vertex_white(vertex_descriptor v, Graph) {
                return !done && get(color, v) == 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
>
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/ 
> listinfo.cgi/boost
>