Получение корня (голова) диграфа в NetworkX (Python)
-
29-09-2019 - |
Вопрос
Я пытаюсь использовать 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)
Я ничего не видел в документации, которая предложила простой способ извлечь корень диграфа - я должен сделать это вручную? : 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]
В качестве альтернативы может быть быстрее начинаться с заданного (случайного) узла и следить за предшественниками, пока не найдете узел без предшественников.