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

From: Vladimir Prus (ghost_at_[hidden])
Date: 2008-02-16 11:11:07

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