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