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?

Solution 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

Solution 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.

Solution 3

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)

Solution 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. ;)

Solution 5

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)

View more solutions