Conseguir la raíz (cabeza) de un dígrafo en NetworkX (Python)
-
29-09-2019 - |
Pregunta
Estoy tratando de utilizar networkx
hacer alguna representación gráfica de un proyecto, y no estoy seguro de cómo hacer algunas cosas que deben ser simples. Creé un gráfico dirigido con un grupo de nodos y bordes, de manera que sólo hay un elemento raíz en este gráfico. Ahora, lo que me gustaría hacer es empezar en la raíz, y luego iterar a través de los hijos de cada elemento y extraer alguna información de ellos. ¿Cómo consigo el elemento raíz de este dígrafo?
Así 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 he visto 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
He intentado conseguir iter(myDiGraph)
con la esperanza de que sería iterar a partir de la raíz, pero el orden parece ser al azar ...: \
ayuda será apreciada, gracias!
Solución
Si por tener "un elemento raíz" que quiere decir que su grafo dirigido es un árbol , entonces la raíz será el único nodo con cero en grados.
Se 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() 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]
Como alternativa puede ser que sea más rápido para empezar con un nodo dado (al azar) y seguir los predecesores hasta que encuentre un nodo sin predecesores.