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

Question

我正在为NetworkX中的有向图编写代码，遇到了一个问题，这可能是我编程经验不足的结果。我想要做的是：

我有一个有向图G，其中有两个“父节点”在顶部，所有其他节点都从它们那里流入。在绘制此网络图时，我想将所有“Parent 1”的后代节点绘制成一种颜色，并将所有其他节点绘制成另一种颜色。这意味着我需要一个“Parent 1”的后继列表。

现在，我可以轻松地使用以下方法获取它们的第一层：

descend= G.successors(parent1)

问题在于这只给了我第一代后继者。更好的是，我想要后继者的后继者，后继者的后继者的后继者等等。任意地，因为能够运行分析并制作图表而无需知道有多少代会非常有用。

有什么方法可以解决这个问题吗？

- Fomite

Answer 1

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

例如，您可以执行以下操作：

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。

- Jochen Ritzel

---

看起来DFS算法可能是我最好的选择。与使用上面建议的代码不同，我使用了dfs_successors，并且看起来它给我提供了从父节点1到所有后继节点的字典。现在只需要将该字典转换为有用的格式。讨厌字典。 - Fomite

稍微修改上面的答案，最终使用了dfs_successors(G, parent1)，它确实返回所有后继节点的字典，将该字典转换为列表，然后按照https://dev59.com/qnNA5IYBdhLWcg3wdtld#952952中的方法展开列表。感谢两位评论者的帮助。 - Fomite

无法工作...在示例中没有清晰说明。 - Patel Sunil

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)

底层的节点不知何故未被包含。

- abreschi

---

太好了！我正需要像 nx.dfs_tree 这样的东西。 - yatu

这个应该放得更高一些，即使被接受的答案解决了 OP 的问题，但实际上问题的表述只有这个问题回答了。 - LoicM

Answer 3

嗯，继承者的继承者就是后代的继承者对吧？

# 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)

要获取第三级后代，请调用allDescendants(d2)等。

编辑： 问题1： allDescend = descend + descend2会给你两个集合的组合，对于更深层次的后代也是一样的。

问题2：如果您的图中有循环，则需要先修改代码以测试是否已经访问过该后代，例如：

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

这样，您将allDescend作为上述函数的第二个参数传递，以便它不包括在未来的后代中。您一直这样做，直到allDescandants()返回一个空数组，这样您就知道已经探索了整个图形，并停止。

由于这开始看起来像作业，我会让您自己想出如何将所有这些组合在一起。 ;)

- Charles Ma

---

两个问题。1：运行上述代码只会给出第二级后代。有没有一种方法将结果附加到基本上获取所有后代的运行列表中？2：这个解决方案假定我知道我有多少级。有没有一种方法运行它n级，直到它基本上停止获取新的后代？ - Fomite

顺便说一下，这不是作业。我已经做得足够好了，超过了作业的范畴，进入了“太棒了，听起来像个绝妙的想法，去实现它吧...”的阶段。 - Fomite

快速注释：使用 += 操作符比使用 append 更加昂贵，因为每次循环迭代时都会销毁并创建新的 list 对象。可以使用 pympler 和 line_profiler 观察差异。 - 0 _

Answer 4

为了让未来遇到这个问题的人更容易找到并且更清晰，以下是我最终使用的代码：

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)

- Fomite

Answer 5

我相信自从 @Jochen Ritzel 几年前回答以来，Networkx已经有所改变。

现在只需要更改导入语句即可实现以下操作。

import networkx
from networkx import dfs_edges

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

- HeyWatchThis

Answer 6

nx.descendants(G, parent)

更多细节：https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.dag.descendants.html

- Neil

Answer 7

一行代码：

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

- TurtleIzzy

Answer 8

你可以使用networkx.algorithms.traversal.depth_first_search中的dfs_predecessors和dfs_successors来解决这个问题。

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

- Draculaaair