Finding Successors of Successors in a Directed Graph in NetworkX

Question

I'm working on some code for a directed graph in NetworkX, and have hit a block that's likely the result of my questionable programming experience. What I'm trying to do is the following:

I have a directed graph G, with two "parent nodes" at the top, from which all other nodes flow. When graphing this network, I'd like to graph every node that is a descendant of "Parent 1" one color, and all the other nodes another color. Which means I need a list Parent 1's successors.

Right now, I can get the first layer of them easily using:

descend= G.successors(parent1)

The problem is this only gives me the first generation of successors. Preferably, I want the successors of successors, the successors of the successors of the successors, etc. Arbitrarily, because it would be extremely useful to be able to run the analysis and make the graph without having to know exactly how many generations are in it.

Any idea how to approach this?

Composition

Answer 1

You don't need a list of descendents, you just want to color them. For that you just have to pick a algorithm that traverses the graph and use it to color the edges.

For example, you can do

from networkx.algorithms.traversal.depth_first_search import dfs_edges

G = DiGraph( ... )
for edge in dfs_edges(G, parent1):
    color(edge)

See https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.traversal.depth_first_search.dfs_edges.html?highlight=traversal

Surgeonfish

It looks like a DFS algorithm might be my best bet. Rather than using the code suggested above, I used dfs_successors, and it looks like that gives me a dictionary of all successors from parent 1. Now just need to get that dictionary into a useful format. hate dictionaries. – Composition

Modifying the above answer just slightly, ended up using dfs_successors(G, parent1) which does indeed return a dictionary of all successors, turning that dictionary into a list, then flattering the list per #953414. Thank you to both commenters for your help. – Composition

Does not work... not clearly illustrated in example. – Humor

Answer 2

If you want to get all the successor nodes, without passing through edges, another way could be:

import networkx as nx
G = DiGraph( ... )
successors = nx.nodes(nx.dfs_tree(G, your_node))

I noticed that if you call instead:

successors = list(nx.dfs_successors(G, your_node))

the nodes of the bottom level are somehow not included.

Richmal

Sweet! Was looking exactly for something like nx.dfs_tree – Rijeka

This should be higher up, even though the accepted answer solves OP's problem, the question was actually framed in a way that only this question answers – Kesterson

Answer 3

So that the answer is somewhat cleaner and easier to find for future folks who stumble upon it, here's the code I ended up using:

G = DiGraph() # Creates an empty directed graph G
infile = open(sys.argv[1])
for edge in infile:
    edge1, edge2 = edge.split() #Splits data on the space
    node1 = int(edge1) #Creates integer version of the node names 
    node2 = int(edge2)
    G.add_edge(node1,node2) #Adds an edge between two nodes

parent1=int(sys.argv[2])   
parent2=int(sys.argv[3])

data_successors = dfs_successors(G,parent1)
successor_list = data_successors.values()
allsuccessors = [item for sublist in successor_list for item in sublist]

pos = graphviz_layout(G,prog='dot') 
plt.figure(dpi=300)
draw_networkx_nodes(G,pos,node_color="LightCoral")
draw_networkx_nodes(G,pos,nodelist=allsuccessors, node_color="SkyBlue")
draw_networkx_edges(G,pos,arrows=False) 
draw_networkx_labels(G,pos,font_size=6,font_family='sans-serif',labels=labels)

Composition

Answer 4

Well, the successor of successor is just the successor of the descendants right?

# First successors
descend = G.successors(parent1)
# 2nd level successors
def allDescendants(d1):
   d2 = []
   for d in d1:
       d2 += G.successors(d)
   return d2

descend2 = allDescendants(descend)

To get level 3 descendants, call allDescendants(d2) etc.

Edit: Issue 1: allDescend = descend + descend2 gives you the two sets combined, do the same for further levels of descendants.

Issue2: If you have loops in your graph, then you need to first modify the code to test if you've visited that descendant before, e.g:

def allDescendants(d1, exclude):
   d2 = []
   for d in d1:
       d2 += filter(lambda s: s not in exclude, G.successors(d))
   return d2

This way, you pass allDescend as the second argument to the above function so it's not included in future descendants. You keep doing this until allDescandants() returns an empty array in which case you know you've explored the entire graph, and you stop.

Since this is starting to look like homework, I'll let you figure out how to piece all this together on your own. ;)

Refractory

Two issues. 1: Running the above code gives only the 2nd level descendants. Is there a way to append the results to get essentially a running list of all descendants? 2: This solution assumes I know how many levels I have. Is there a way to run it for n levels, until it essentially stops getting new descendants? – Composition

It is, incidentally, not homework. Far enough along that I'm past homework and into "Great, that sounds like a splendid idea, go implement it..." – Composition

Quick comment: using += is more expensive than append, because new list objects are destroyed and created in every loop iteration. pympler and line_profiler can be used to observe the difference. – Conventionality

Answer 5

I believe Networkx has changed since @Jochen Ritzel 's answer a few years ago.

Now the following holds, only changing the import statement.

import networkx
from networkx import dfs_edges

G = DiGraph( ... )
for edge in dfs_edges(G, parent1):
    color(edge)

Spada

Answer 6

Oneliner:

descendents = sum(nx.dfs_successors(G, parent).values(), [])

Smaze

Answer 7

nx.descendants(G, parent)

more details: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.dag.descendants.html

Cupped

Answer 8

you can use the dfs_predecessors and dfs_successors in networkx.algorithms.traversal.depth_first_search to solve the problem.

import networkx.algorithms.traversal.depth_first_search as dfs
dfs.dfs_successors(graph, node)
dfs.dfs_predecessors(graph, node)

Swatch