Obtenir la racine (tête) d'un digraphe dans networkx (Python)
je suis en train d'utiliser networkx à faire une certaine représentation graphique dans un projet, et je ne suis pas sûr de la façon de faire un peu de choses qui devrait être simple. J'ai créé un graphe orienté avec un tas de nœuds et d'arêtes, tel qu'il existe un seul élément racine dans ce graphique. Maintenant, ce que j'aimerais faire, c'est commencer à la racine, puis itérer à travers les enfants de chaque élément et en extraire quelques informations. Comment puis-je obtenir l'élément racine de ce Digraphe?
donc ce serait quelque chose comme ceci:
#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)
Je n'ai rien vu dans la documentation qui suggérait un moyen facile de récupérer la racine d'un digraphe -- suis-je censé le déduire manuellement? :O
J'ai essayé de faire iter(myDiGraph) avec l'espoir qu'il itérerait à partir de la racine, mais l'ordre semble être aléatoire... :
Aide sera appréciée, merci!
1 réponses
si en ayant "un élément racine" vous voulez dire que votre graphique dirigé est un enracinée arbre, puis la racine sera le seul nœud avec zéro degré.
vous pouvez trouver ce noeud en temps linéaire (dans le nombre de noeuds) avec:
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]
In [4]: nx.topological_sort(G)
Out[4]: [0, 1, 3, 8, 7, 4, 9, 10, 2, 5, 11, 12, 6, 13, 14]
alternativement il peut être plus rapide de commencer avec un noeud (aléatoire) donné et de suivre les prédécesseurs jusqu'à ce que vous trouviez un noeud avec aucun prédécesseur.