在NetworkX中查找有向图的后继的后继

Question

我正在用NetworkX写一个有向图的代码，但遇到了一些问题，可能是因为我编程经验不太丰富。我的目标是这样的：

我有一个有向图G，顶部有两个“父节点”，所有其他节点都是从这两个父节点延伸出来的。在绘制这个网络时，我想把“父节点1”的所有后代节点用一种颜色表示，而其他节点用另一种颜色。这就意味着我需要一个“父节点1”的后继节点列表。

现在，我可以很容易地获取到它们的第一层后继节点，方法是：

descend= G.successors(parent1)

问题是，这样只能得到第一代的后继节点。其实，我希望能获取到后继节点的后继节点，也就是后继节点的后继节点的后继节点，依此类推。这样做是为了方便分析和绘制图形，而不需要确切知道有多少代节点。

有没有什么好的方法来解决这个问题呢？

Answer 1

为了让这个答案看起来更简洁，也方便以后遇到这个问题的人找到，这里是我最终使用的代码：

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)

Answer 2

如果你想获取所有的后继节点，而不通过边连接，另一种方法可以是：

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

我注意到如果你改用下面的方式调用：

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

那么底层的节点似乎就没有被包含在内。

Answer 3

你不需要一个后代的列表，你只想给它们上色。为此，你只需要选择一个遍历图形的算法，然后用它来给边上色。

比如，你可以这样做：

from networkx.algorithms.traversal.depth_first_search import dfs_edges

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

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