获取NetworkX(Python)中的Digraph的根(头)
-
29-09-2019 - |
题
我正在尝试使用 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)
我在文档中没有看到任何简单的方法来检索Digraph的根源的简便方法 - 我应该手动推断出这一点吗? :o我尝试得到 iter(myDiGraph)
希望它能从根部开始迭代,但是顺序似乎是随机的...
帮助您将不胜感激,谢谢!
解决方案
如果通过“一个根元素”,您的意思是您的定向图是一个 生根, ,然后根部将是唯一具有零度内的节点。
您可以在线性时间(在节点数)中找到该节点,并带有以下方式:
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]
另外,从给定的(随机)节点开始并关注前身,直到找到没有前身的节点为止,它可能会更快。
不隶属于 StackOverflow