在networkx中按顺序获取源的祖先

Question

我正在使用 networkx 2.1 版来生成图表。

g = nx.DiGraph()
g.add_nodes_from([1, 2, 3, 4, 5, 6])
g.add_edges_from([(1, 2), (2, 4), (4, 5), (1, 3), (3, 6)])

如果我通过检查节点= 5的祖先nx.ancestors(g, 5)，它{1, 2, 4}有时会不按顺序返回集合，例如{1, 4, 2}如何按顺序获取它？有什么办法可以按顺序获取吗？

Answer 1

你的有向图看起来像一棵树（也就是每个节点最多可以有 1 个父节点，唯一没有父节点的节点是根）。

如果您的真实图是一棵树，那么按顺序获取所有祖先的最简单方法是使用该shortest_path()函数。

import networkx as nx
g = nx.DiGraph()
g.add_nodes_from([1, 2, 3, 4, 5, 6])
g.add_edges_from([(1, 2), (2, 4), (4, 5), (1, 3), (3, 6)])
nx.shortest_path(g, source=1, target=5)
# return [1,2,4,5] which is the list of all nodes from root 1 to my node 5

如果您不知道树的根，那么找到它的一个简单方法是查找唯一等于in_degree0 的节点。例如：

def get_root(g):
    for node, indegree in g.in_degree():
         if indegree == 0:
              # if you'r graph is a tree you only have one root so you don't need to check every node, once you find it it's done
              return node

或者只是拓扑排序中的第一个元素：next(nx.topological_sort(g))

如果您的图不是树，您可能需要使用predecessors()（或successors()取决于您如何执行方法）定义新的递归方法

编辑：更改代码以使用您的示例