[Boost-users] Creating custom depth first search visitor for Boost graph

[Stephen Torri]

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...@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Elvanör]

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

[Stephen Torri]

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;

};

[Douglas Gregor]

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

[Stephen Torri]

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

[Douglas Gregor]

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

[Stephen Torri]

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