python - 在networkx(Python)中获取DiGraph的根(头)

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

所以会是这样的:

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

我没有在文档中看到任何建议简单的方法来检索DiGraph根的方法-我应该手动推断吗？ :O
我尝试获取iter(myDiGraph)，希望它会从根开始进行迭代，但是顺序似乎是随机的...:\

帮助将不胜感激，谢谢!

最佳答案

如果使用“一个根元素”表示您的有向图是rooted tree，则根将是唯一一个度数为零的节点。

您可以通过以下方式在线性时间(以节点数为单位)中找到该节点:

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]

或者，您可以使用拓扑排序(root是第一项):

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

或者，从给定的(随机)节点开始并跟随先前的节点，直到找到没有先前节点的节点，可能会更快。

关于python - 在networkx(Python)中获取DiGraph的根(头)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4122390/