21 May
2007
21 May
'07
10:50 p.m.
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?