在networkx(Python)中获取DiGraph的根(头) [英] Getting the root (head) of a DiGraph in networkx (Python)

问题描述

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

I'm trying to use networkx to do some graph representation in a project, and I'm not sure how to do a few things that should be simple. I created a directed graph with a bunch of nodes and edges, such that there is only one root element in this graph. Now, what I'd like to do is start at the root, and then iterate through the children of each element and extract some information from them. How do I get the root element of this 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)，希望它会从根开始进行迭代，但是顺序似乎是随机的...:\

I didn't see anything in the documentation that suggested an easy way to retrieve the root of a DiGraph -- am I supposed to infer this manually? :O I tried getting iter(myDiGraph) with the hope that it would iterate starting at the root, but the order seems to be random... :\

我们将不胜感激，谢谢！

Help will be appreciated, thanks!

推荐答案

如果具有一个根元素"，则表示您的有向图是根树，则根将是唯一一个度数为零的节点.

If by having "one root element" you mean your directed graph is a rooted tree, then the root will be the only node with zero in-degree.

您可以使用以下时间在线性时间(以节点数为单位)中找到该节点:

You can find that node in linear time (in the number of nodes) with:

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]

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

Or you could use a topological sort (root is first item):

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

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

Alternatively it might be faster to start with a given (random) node and follow the predecessors until you find a node with no predecessors.

这篇关于在networkx(Python)中获取DiGraph的根(头)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！