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