Ottenere la radice (testa) di un DiGraph in networkx (Python)

Question

Sto provando a usare networkx per fare una rappresentazione grafica in un progetto, e non sono sicuro di come fare alcune cose che dovrebbero essere semplici. Ho creato un grafico diretto con un gruppo di nodi e spigoli, in modo tale che ci sia solo un elemento radice in questo grafico. Ora, quello che mi piacerebbe fare è iniziare dalla radice, quindi scorrere i figli di ciascun elemento ed estrarre alcune informazioni da essi. Come ottengo l'elemento principale di questo 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 ad ottenere iter(myDiGraph) con la speranza che sarebbe iterato iniziando dalla radice, ma l'ordine sembra essere casuale ...: \

L'aiuto sarà apprezzato, grazie!

Answer 1

Se con "un elemento radice" si intende il grafico diretto è un rooted tree, quindi la radice sarà l'unico nodo con zero in grado.

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().items() 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] 

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