Creating custom depth first search visitor for Boost graph
I have a need to have a graph visitor algorithm similar to depth first search. The only difference is that if upon running discover_vertex the intended operation to be done on the vertex is not done I want the graph color value for this position to still be white. The reason is that the graph I am using the depth first search is a directed graph with no loops in it. A vertex might have two or more vertices providing information. If all the information is not there I want the visitor to try again. What do I have to do to gain access to the color map inside the visitor when I am in discover_vertex? Stephen
Hello,
when you are inside the visitor the () operator takes two arguments, a
vertex descriptor and a reference to the graph.
So I guess you can use this graph variable to access the property map
for color.
For example I have the following visitor:
struct SendMsg : public base_visitor <SendMsg>
{
typedef on_finish_vertex event_filter;
/* here what the visitor must do... */
template
I have a need to have a graph visitor algorithm similar to depth first search. The only difference is that if upon running discover_vertex the intended operation to be done on the vertex is not done I want the graph color value for this position to still be white.
The reason is that the graph I am using the depth first search is a directed graph with no loops in it. A vertex might have two or more vertices providing information. If all the information is not there I want the visitor to try again.
What do I have to do to gain access to the color map inside the visitor when I am in discover_vertex?
Stephen
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Here is my visitor after making the suggested changes. I am not sure
this does the job because I don't understand the following:
1) How is a custom visitor used as a replacement to depth_first_search?
The code for how to handle the coloring of the vertex nodes seems to be
handled by the depth_first_search algorithm and not the associated
visitor.
2) When is the operator() called?
Stephen
-------- CODE --------
template
On Mar 10, 2005, at 9:57 AM, Stephen Torri wrote:
Here is my visitor after making the suggested changes. I am not sure this does the job because I don't understand the following:
1) How is a custom visitor used as a replacement to depth_first_search? The code for how to handle the coloring of the vertex nodes seems to be handled by the depth_first_search algorithm and not the associated visitor.
The algorithm will handle the coloring of vertices, but will call the member functions of the visitor (discover_vertex, tree_edge, etc.) when it reaches the associated event.
2) When is the operator() called?
The "event_filter" typedef tells the BGL which event to associate operator() with. For instance, in the code below it is typedef'd to on_discover_vertex, so operator() will be called whenever a vertex is first discovered in the DFS traversal, e.g., when it's color goes from white to gray. Doug
On Mon, 2005-03-14 at 10:20 -0500, Douglas Gregor wrote:
On Mar 10, 2005, at 9:57 AM, Stephen Torri wrote:
Here is my visitor after making the suggested changes. I am not sure this does the job because I don't understand the following:
1) How is a custom visitor used as a replacement to depth_first_search? The code for how to handle the coloring of the vertex nodes seems to be handled by the depth_first_search algorithm and not the associated visitor.
The algorithm will handle the coloring of vertices, but will call the member functions of the visitor (discover_vertex, tree_edge, etc.) when it reaches the associated event.
I agree. That what I learned when I read the code. What I later realized is that I want to replace the algorithm and the visitor. My visitor only needs one assocaited event, discover_vertex, which returns a boolean (success calling the contained object's run() method = true. otherwise failure = false). Each vertex in my directed graph contains a object. Each object, called a Component, requires input from the vertices on each of the inbound edges to the object. Here is an example graph: A -> B \ \ \ \-> C -> D Component 'A' supplies information to Components 'B' and 'C' which in turn supply 'D'. In this case of I used any of the existing algorithms (e.g. depth_first_search) the Component 'D' is visited only once. On this first visit the result of run() would be false since it only has 1 of 2 inputs necessary to do its task. D only runs when it has inputs for B and C. So I am thinking about replacing the algorithm with the following: - Initialize Algorithm - Create color map containing a color entry for each vertex - Contain reference to Graph for use with visitor - Initialize vertex stack with all sources (e.g. 'A' - nodes with no inputs are called sources) - While stack is not empty - Graph vertex from top of stack - If vertex color is White - call visitor discover_vertex (vertex, graph) - if result is 'true' - Set color for vertex to Grey - If vertex has no children - Pop vertex - Set color for vertex to Black - Else if vertex color is Grey - Pop vertex - Set color for vertex to Black - Put all children of vertex on stack if all inputs for the child vertex are satisfied. - End if - Done Stephen
On Mar 14, 2005, at 10:52 AM, Stephen Torri wrote:
On Mon, 2005-03-14 at 10:20 -0500, Douglas Gregor wrote:
On Mar 10, 2005, at 9:57 AM, Stephen Torri wrote:
Here is my visitor after making the suggested changes. I am not sure this does the job because I don't understand the following:
1) How is a custom visitor used as a replacement to depth_first_search? The code for how to handle the coloring of the vertex nodes seems to be handled by the depth_first_search algorithm and not the associated visitor.
The algorithm will handle the coloring of vertices, but will call the member functions of the visitor (discover_vertex, tree_edge, etc.) when it reaches the associated event.
I agree. That what I learned when I read the code. What I later realized is that I want to replace the algorithm and the visitor. My visitor only needs one assocaited event, discover_vertex, which returns a boolean (success calling the contained object's run() method = true. otherwise failure = false).
Each vertex in my directed graph contains a object. Each object, called a Component, requires input from the vertices on each of the inbound edges to the object. Here is an example graph:
A -> B \ \ \ \-> C -> D
Component 'A' supplies information to Components 'B' and 'C' which in turn supply 'D'. In this case of I used any of the existing algorithms (e.g. depth_first_search) the Component 'D' is visited only once. On this first visit the result of run() would be false since it only has 1 of 2 inputs necessary to do its task. D only runs when it has inputs for B and C.
Is there any point in calling discover_vertex before all of the inputs have been visited?
So I am thinking about replacing the algorithm with the following:
[snip] I think there's a slightly more efficient work-list algorithm. It would use a queue instead of a stack and keep track of the # of inputs that each vertex still needs. The algorithm would look like this: 1) Create a vertex property map "deg". such that deg(v) = in_degree(v, g) for all vertices in g 2) Initialize queue Q to contain all vertices such that deg(v) = 0 3) While Q is not empty 3a) Pop vertex u off the queue [now call discover_vertex event] 3b) For each out edge (u, v) of u 3b1) decrement deg(v) 3b2) if deg(v) == 0, push it on Q Alternatively, you can use a topological ordering of the vertices computed on the reversed graph. Check out the file dependency example in the BGL docs: http://www.boost.org/libs/graph/doc/file_dependency_example.html You're essentially solving the same problem, but with the edges going in the opposite direction. Using the reverse_graph adaptor, you could use the same solution. Doug
On Mon, 2005-03-14 at 16:09 -0500, Douglas Gregor wrote:
Alternatively, you can use a topological ordering of the vertices computed on the reversed graph. Check out the file dependency example in the BGL docs:
http://www.boost.org/libs/graph/doc/file_dependency_example.html
Thanks for the suggestion. It greatly simplified my algorithm. :)
Here is the extent of the algorithm as implemented:
Filter_Search::Filter_Search
(call_traitsinfrastructure::Component_Graph::ptr::param_type g)
:
m_graph (g)
{
// Create execution order and store in 'm_exec_order'
boost::topological_sort (g->get_Graph(),
std::front_inserter (m_exec_order));
}
// Execute node order using simple default dfs visitor.
void Filter_Search::operator()
(call_traits
participants (3)
-
Douglas Gregor -
Elvanör -
Stephen Torri