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 <class Vertex, class Graph> void operator()(Vertex u, Graph& g) { Vertex v = g[u].get_parent_node(); typename graph_traits <Graph>::edge_descriptor e = edge(u,v,g).first; g[u].send_message( g[v].get_object(), g[e] ); } }; I guess in that example, you need to use the g variable with the color map in order to do what you want... take a look at "http://www.boost.org/libs/graph/doc/depth_first_search.html" and that should help you. I don't know exactly how to that, because I don't know about property maps, but that would be something like g.color_map[v] = ... (excuse me for the absolutely wrong syntax... you'd have to use put I guess) Jean-Noël On 7-Mar-05, at 10:37 PM, Stephen Torri wrote:
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 <class VertexType, class Graph> class filter_visitor : public boost::base_visitor< filter_visitor<Visitor> > { private: typedef on_discover_vertex event_filter; public: filter_visitor (Graph const& g) : m_color (internal_map (num_vertices(g))) {} template <class Vertex, class Graph> void operator() (Vertex child_node, Graph& g) { Vertex parent_node = g[child_node].get_parent_node(); typename graph_traits<Graph>::edge_descriptor e = edge(child_node, parent_node, g).first; g[child_node].send_message (g[parent_node].get_object(), g[e]); } private: ColorMap m_color; };
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_traits<infrastructure::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<Kurt_Filter_Visitor>::reference vis) { for (ExecOrder::iterator node = m_exec_order.begin(); node != m_exec_order.end(); ++node) { infrastructure::Component::ptr comp_obj = m_graph->get_Component (*node); vis.discover_vertex (*node, m_graph->get_Graph()); } } Isn't elegance nice! :) Stephen
participants (3)
-
Douglas Gregor -
Elvanör -
Stephen Torri