在网络x（Python）中获取DiGraph的根（头部）

我试图使用networkx在项目中做一些图形表示，我不确定如何做一些应该很简单的事情。我用一堆节点和边创建了一个有向图，这样在这个图中只有一个根元素。现在，我想要做的是从根开始，然后遍历每个元素的子元素并从中提取一些信息。我如何获得这个DiGraph的根元素？在网络x（Python）中获取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)

我没有看到，建议一个简单的方法来检索有向图的根文档中任何东西 - 我应该手动推断呢？：O 我试图得到iter(myDiGraph)与希望它会迭代开始在根，但顺序似乎是随机的...：\

帮助将不胜感激，谢谢！

来源

2010-11-08 mindthief

在我不明白的观点中，图形不一定有根，因此没有找到它的函数。 – fmark 2010-11-08 09:11:17

这是有道理的。 – mindthief 2010-11-08 18:03:32

如果通过“一个根元素”表示您的有向图是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().items() 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]

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

来源

2010-11-08 10:54:30 Aric

+12

Aric写了networkx。 – hughdbrown 2010-11-08 15:01:51

我尝试了拓扑排序和工作。速度不是这项行动的主要关注点，所以我可能会坚持这一点，但如果它确实成为一个问题，我会考虑你的第三种选择 – mindthief 2010-11-08 18:02:04

在网络x（Python）中获取DiGraph的根（头部）

回答

相关问题