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://listarchives.boost.org/mailman/
> listinfo.cgi/boost
>