Re: [Boost-users] BGL - retrieving a subgraph

From: Doug Gregor (dgregor_at_[hidden])
Date: 2007-05-22 08:03:42

On May 21, 2007, at 6:50 PM, Noah Roberts wrote:

> To describe what I want to do I will use the following graph:
>
> digraph G {
> 0[label="test1"];
> 1[label="test2"];
> 2[label="test3"];
> 3[label="test4"];
> 2->0 ;
> 2->1 ;
> 3->0 ;
> 3->2 ;
> }
>
> Now, what I want to do is two things.  Both are for vertices such  
> as 2.
>   2 depends on 0 and 1, it has 3 as its only client.  Is there a graph
> algorithm that will extract those two subgraphs for me?  Take any  
> vertex
> in a directer graph and give me a subgraph of all its descendants or a
> subgraph for all its ancestors (I imagine those are two different
> algorithms).
>
> I looked at the connected components algorithms and none seemed to
> apply.  Still looking at others but there are a lot of functions.  Any
> ideas to narrow down the search?

To get all of the descendants, you could just run a breadth-first or  
depth-first search starting at vertex "2", and then record which  
vertices were visited.

To get the ancestors, you could do exactly the same thing using the  
reverse graph; see http://www.boost.org/libs/graph/doc/ 
reverse_graph.html

        - Doug