Obtenir la racine (tête) d'un DIGRAMME dans NetworkX (Python)

Question

Je suis en train d'utiliser networkx pour faire une représentation graphique d'un projet, et je ne sais pas comment faire quelques choses qui doivent être simples. Je crée un graphe orienté avec un groupe de noeuds et d'arêtes, de sorte qu'il n'y a qu'un seul élément racine dans ce graphique. Maintenant, ce que je voudrais faire est de commencer à la racine, puis à travers les enfants itérer de chaque élément et extraire des informations de leur part. Comment puis-je obtenir l'élément racine de ce DIGRAMME?

Alors, 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 ne vois rien dans la documentation qui a suggéré un moyen facile de récupérer la racine d'un DIGRAMME - dois-je en déduire manuellement? : O J'ai essayé d'obtenir iter(myDiGraph) avec l'espoir qu'il itérer à partir de la racine, mais l'ordre semble être au hasard ...: \

aide sera appréciée, merci!

Answer 1

Si en ayant « un élément racine » vous voulez dire votre graphe orienté est un racine arbre , puis la racine sera le seul noeud avec zéro degré.

Vous pouvez trouver ce nœud dans le temps linéaire (le nombre de nœuds) 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]

Ou vous pouvez utiliser une sorte topologique (racine est le premier élément):

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 par un noeud donné (aléatoire) et suivez les prédécesseurs jusqu'à ce que vous trouviez un nœud sans prédécesseurs.