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