在networkx中获取有向图的根（头）（Python）

Question

我正在尝试使用

networkx

在项目中进行一些图形表示，但我不确定如何做一些应该简单的事情。我创建了一个包含一堆节点和边的有向图，使得该图中只有一个根元素。现在，我想做的是从根开始，然后迭代每个元素的子元素并从中提取一些信息。我如何获得这个有向图的根元素？

所以会是这样的：

#This is NOT real code, just pseudopython to convey the general intent of what I'd like to do

    root = myDiGraph.root()
    for child in root.children():
        iterateThroughChildren(child)

def iterateThroughChildren(parent):
    if parent.hasNoChildren(): return
    for child in parent.children():
        //do something
        //
        iterateThroughChildren(child)

我没有在文档中看到任何建议检索有向图根的简单方法的内容——我是否应该手动推断这一点？ ：哦 我尝试获取

iter(myDiGraph)

，希望它能从根开始迭代，但顺序似乎是随机的......：\

我们将不胜感激，谢谢！

Answer 1

如果“一个根元素”意味着您的有向图是一棵“有根树”，那么根将是唯一入度为零的节点。 您可以通过以下方式在线性时间内（以节点数）找到该节点：

In [1]: import networkx as nx

In [2]: G=nx.balanced_tree(2,3,create_using=nx.DiGraph()) # tree rooted at 0

In [3]: [n for n,d in G.in_degree() if d==0] 
Out[3]: [0]

或者您可以使用拓扑排序（根是第一项）：

In [4]: nx.topological_sort(G)
Out[4]: [0, 1, 3, 8, 7, 4, 9, 10, 2, 5, 11, 12, 6, 13, 14]

或者，从给定（随机）节点开始并跟踪前驱节点，直到找到没有前驱节点的节点可能会更快。

Answer 2

root_node = [x for x in G.nodes() if G.out_degree(x)>1 and G.in_degree(x)==0]