Erhalten der Wurzel (Kopf) eines Digraphen in NetworkX (Python)

Question

Ich versuchen networkx zu verwenden, um einige Diagrammdarstellung in einem Projekt zu tun, und ich bin nicht sicher, wie ein paar Dinge zu tun, die einfach sein sollten. Ich habe einen gerichteten Graphen mit einem Bündel von Knoten und Kanten, so dass es nur ein Wurzelelement in dieser graphischen Darstellung ist. Nun, was ich möchte, ist an der Wurzel beginnen zu tun, und iterieren dann durch die Kinder jedes Elements und Auszug aus ihnen einige Informationen. Wie kann ich das Wurzelelement dieser Digraph?

erhalten

So wäre es so etwas wie diese:

#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)

Ich habe nichts gesehen in der Dokumentation, die eine einfache Möglichkeit vorgeschlagen, die Wurzel eines Digraphen abzurufen - soll ich diese manuell schließen? :Ö Ich versuchte immer iter(myDiGraph) mit der Hoffnung, dass es an der Wurzel beginnen würde laufen, aber die Reihenfolge scheint zufällig zu sein ...: \

Hilfe geschätzt wird, danke!

Answer 1

Wenn durch „ein Wurzelelement“ Haben Sie Ihren gerichteten Graphen bedeuten eine , wird die Wurzel der einzige Knoten ist mit Null-Grad-.

Sie können diesen Knoten in linearer Zeit finden (in der Anzahl der Knoten) mit:

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]

Sie können auch eine topologische Sortierung verwenden (root ist erster Punkt):

In [4]: nx.topological_sort(G)
Out[4]: [0, 1, 3, 8, 7, 4, 9, 10, 2, 5, 11, 12, 6, 13, 14]

Alternativ könnte es schneller sein, mit einem gegebenen (random) Knoten zu starten und den Vorgängern folgen, bis Sie einen Knoten ohne Vorgänger finden.