Получение корня (главы) DiGraph в networkx (Python)

Я пытаюсь использовать 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) с надеждой на то, что он будет начинаться с корня, но порядок кажется случайным...:\

Помощь будет оценена, спасибо!

Ответы

Ответ 1

Если, имея "один корневой элемент", вы имеете в виду, что ваш ориентированный граф является корневым деревом, тогда корень будет единственным node с нулевой степенью.

Вы можете найти, что node в линейном времени (в числе узлов):

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]

В качестве альтернативы, возможно, быстрее начать с данного (случайного) node и следовать за предшественниками, пока не найдете node без предшественников.