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

Question

我正在 NetworkX 中编写有向图的一些代码，并且遇到了一个障碍，这可能是我可疑的编程经验的结果。我想做的是：

我有一个有向图 G，顶部有两个“父节点”，所有其他节点都从其流动。在绘制该网络的图形时，我想将“Parent 1”的后代的每个节点绘制为一种颜色，并将所有其他节点绘制为另一种颜色。这意味着我需要一份 Parent 1 的继任者列表。

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

descend= G.successors(parent1)

问题是这只能给我第一代接班人。最好是，我想要后继者的后继者，后继者的后继者的后继者，等等。任意，因为能够运行分析并制作图表而不必确切知道其中有多少代将非常有用.

知道如何解决这个问题吗？

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

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

为了让未来偶然发现它的人更清晰、更容易找到答案，这是我最终使用的代码：

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 4

那么，继承人的继承人就是后代的继承人吧？

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

要获得 3 级后代，请调用 allDescendants(d2) 等。

编辑： 问题一：

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

返回一个空数组，在这种情况下您知道您已经探索了整个图表，然后停止。

由于这开始看起来像家庭作业，我将让您自己弄清楚如何将所有这些拼凑在一起。 ;)

Answer 5

我相信自几年前 @Jochen Ritzel 的回答以来 Networkx 已经发生了变化。

现在以下内容成立，仅更改导入语句。

import networkx
from networkx import dfs_edges

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

Answer 6

单行：

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

Answer 7

nx.descendants(G, parent)

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

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)