Finding All Successors of a Node in a Directed Graph

[EpiGrad]

Hey all,

I'm working on a problem, and I've hit a spot where my relative
inexperience with Python, and programming in general, has hit a wall.

I have a directed graph G, with two parent nodes all the other nodes
are connected from. What I'm looking to do is produce a graph of this
network, with every node that came from one parent colored one way,
and all the others colored a second way. So essentially, I need a list
of nodes that's not only the successors to "Parent 1" but the
successors of those successors, the successors of the successors
successors, etc. Preferably for an arbitrary number of generations,
because while I could hard code it for each network, it would be nice
to be able to just throw a network at it and have it work.

Any idea how to approach this?

Thanks,

Eric

[Dan Schult]

I think you are looking for connected components.
Take a look at this page and see if any are what you need:
http://networkx.lanl.gov/preview/reference/algorithms.component.html
I think the node_connected_components() will do the trick.
Dan

[Aric Hagberg]

You could use a depth-first-search starting first from Parent 1 and
then from Parent 2.
If you want a graph, the function dfs_tree(G,start) will give you the
tree of nodes in G reachable from "start".

Aric

[EpiGrad]

Connected components only works for undirected graphs, and allows for
"upstream" flows if one converts the DiGraph to a regular graft. Ended
up using dfs_successors, which works like a charm.