On Thursday 28 February 2008 14:17:56 Christian Sturz wrote:
my graph (based on adjacency_list) represents the control-flow graph of a program where each vertex is a statement and the control-flow relations between the statements are modeled by edges. Now I'm looking for an algorithm that finds all vertices that can be reached from a defined statement. So, what I need is a back-traversal of the graph, from the given vertex to all predecessors and so forth.
If you want to find all vertices reachable from a given one, you can use depth_first_search, using a custom visitor to record all seen vertices.
The problem with the Boost "depth_first_search" is that "once all reachable vertices have been visited, the algorithm selects from any remaining undiscovered vertices and continues the traversal". That would mean that even if I specify a start vertex and use reverse_graph, I would first get all the vertices reachable from the start vertex (that's what I need) but then the algorithm would continue with vertices I'm not interested in. I didn't find an approach to stop the DFS before further undiscovered vertices are considered. Do you have an idea how to modify depth_first_search for my needs?
Use depth_first_visit.
Well, unfortunately you did not explain clearly what exact program analysis problem you are trying to solve, so it's not obvious. In any case, reverse_graph can be used.
I have a control-flow graph of a C program where each statement represents a graph vertex. For a given statement (vertex) I want to find all statements that can have an effect on that statement (thus, the back traversal).
Seems like depth_first_visit will indeed work for your case. - Volodya