Получение корня (головы) DiGraph в сети x (Python) - PullRequest
Новая
       35

Получение корня (головы) DiGraph в сети x (Python)

22 голосов
/ 08 ноября 2010

Я пытаюсь использовать 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 Ответ

46 голосов
/ 08 ноября 2010

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

Вы можете найти этот узел за линейное время (по количеству узлов) с помощью: 

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]

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

...