Christian Sturz wrote:
Hi,
I'm looking for an appropriate Boost Graph algorithm for the following problem:
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. There's also the reverse_graph adaptor that can be used to traverse a graph in opposite direction.
I didn't find any algorithm in the Boost Graph Library. The "strong_components" algorithm might be OK since it assumes a directed graph (as is mine) but the algorithm seems to operate in the direction of the directed edges.
The strong_components will find strongly connected components, and it does not seem that's what you're after. In particular, for a asyclic program graph, strong_components will not give any results of interest at all.
Obviously I need the the opposite direction.
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. - Volodya