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

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2005-03-14 16:09:47

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