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

From: Stephen Torri (storri_at_[hidden])
Date: 2005-03-14 10:52:37

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