Looking for a boost graph algorithm
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. 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. Obviously I need the the opposite direction. Do you know any approach/algorithm that might solve my problem? Regards, Chris -- Psssst! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger
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
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?
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). Christian -- Der GMX SmartSurfer hilft bis zu 70% Ihrer Onlinekosten zu sparen! Ideal für Modem und ISDN: http://www.gmx.net/de/go/smartsurfer
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
participants (2)
-
Christian Sturz -
Vladimir Prus