python - directed - networkx draw

Obtención de la raíz(cabecera) de un DiGraph en networkx(Python)

Question

Estoy tratando de usar networkx para hacer una 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 montón de nodos y bordes, de manera que solo hay un elemento raíz en este gráfico. Ahora, lo que me gustaría hacer es comenzar en la raíz y luego recorrer los elementos secundarios de cada elemento y extraer información de ellos. ¿Cómo obtengo el elemento raíz de este DiGraph?

Entonces sería algo así:

#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 sugiriera una forma fácil de recuperar la raíz de un DiGraph. ¿Se supone que debo inferir esto manualmente? : O Intenté obtener iter(myDiGraph) con la esperanza de que fuera iterativo comenzando desde la raíz, pero el orden parece ser aleatorio ...: /

Se agradecerá la ayuda, gracias!

Answer 1

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

Puede encontrar ese nodo en 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() if d==0]
Out[3]: [0]

O podrías usar una ordenación topológica (la 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 a los predecesores hasta que encuentre un nodo sin predecesores.