Ottenere la radice (testa) di un grafo orientato a NetworkX (Python)

Question

Sto cercando di utilizzare networkx per fare qualche rappresentazione grafica in un progetto, e io non sono sicuro di come fare un paio di cose che dovrebbero essere semplici. Ho creato un grafo orientato con un gruppo di nodi e spigoli, in modo tale che v'è un solo elemento radice in questo grafico. Ora, quello che mi piacerebbe fare è iniziare alla radice, e poi iterare attraverso i bambini di ogni elemento ed estrarre alcune informazioni da loro. Come faccio a ottenere l'elemento principale di questa digraph?

Quindi sarebbe qualcosa di simile:

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

Non ho visto nulla nella documentazione che ha suggerito un modo semplice per recuperare la radice di un digramma - dovrei dedurre manualmente? : O Ho provato a ottenere iter(myDiGraph) con la speranza che sarebbe iterare a partire dalla radice, ma l'ordine sembra essere casuale ...: \

Guida sarà apprezzato, grazie!

Answer 1

Se per avere "un elemento root" vuoi dire la tua grafo orientato è un radicata albero , allora la radice sarà l'unico nodo con zero gradi.

Potete trovare quel nodo in tempo lineare (nel numero di nodi) con:

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]

Oppure si potrebbe usare un ordinamento topologico (root è il primo articolo):

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

In alternativa potrebbe essere più veloce di iniziare con un dato nodo (casuale) e seguire le predecessori fino a trovare un nodo senza precedenti.