Obteniendo la raíz (cabeza) de un DiGraph en networkx (Python)

Question

Estoy tratando de usar networkx para hacer alguna representación gráfica en un proyecto, y no estoy seguro de cómo hacer algunas cosas que deberían ser simples. Creé un gráfico dirigido con un grupo de nodos y bordes, de modo que solo hay un elemento raíz en este gráfico. Ahora, lo que me gustaría hacer es comenzar desde la raíz, y luego repetir a través de los elementos secundarios de cada elemento y extraer algo de información de ellos. ¿Cómo obtengo el elemento raíz de este DiGraph?

por lo que sería algo como esto:

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

no vi nada en la documentación que sugiere una manera fácil de recuperar la raíz de un dígrafo - se supone que debo inferir de forma manual? : O Intenté obtener iter(myDiGraph) con la esperanza de que iteraría comenzando en la raíz, pero el orden parece ser aleatorio ...: \

Ayuda será apreciada, gracias!

Answer 1

Si al tener "un elemento raíz" quiere decir que su gráfico dirigido es un rooted tree, entonces la raíz será el único nodo con cero en grado.

puede encontrar ese nodo en el tiempo lineal (en el número de nodos) 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] 

O usted podría utilizar una ordenación topológica (raíz es el primer elemento):

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

Alternativamente podría ser más rápido comenzar con un nodo dado (aleatorio) y seguir los predecesores hasta que encuentre un nodo sin predecesores.