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