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

From: Vladimir Prus (ghost_at_[hidden])
Date: 2008-02-28 06:58:53

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