Re: [Boost-users] Looking for a boost graph algorithm

From: Christian Sturz (linuxkaffee_at_[hidden])
Date: 2008-02-28 06:17:56

> > 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