Numéroter la place des noeud dans un graphe

Bonjour,
Je cherche à noter la placer des nœud dans un grâce c'est à dire que si un nœud dans un graphe a 0 prédécesseur il est a la place 1, si il en a un il est a la place 2 est ainsi de suite. J'ai réussi pour le premier cas (le noeud n'as pas de successeur) mais je bloque totalement pour la seconde partie... Pourriez vous m'aider s'il vous plait ?
Voici mon code :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
 
 
def placeDansGraphe(directed_graph):
 
    nbPred = 0
    noeudSansPred = []
    tabDePredessesseur = []
    passe = [] 
 
    for n in directed_graph.nodes(): 
        for pred in directed_graph.predecessors(n): 
            directed_graph.nodes[n]['estampille']=10
        if 'estampille' not in directed_graph.nodes[n]: 
            directed_graph.nodes[n]['estampille']=1
            noeudSansPred.append(n)
    for n in directed_graph.nodes(): 
        est = 1
        for suiv in directed_graph.nodes(): 
            if suiv not in noeudSansPred:
                est = est +1
                passe.append(n)
                directed_graph.nodes[suiv]['estampille']=est
 
 
edges_list=[('p_0_1', 'p_0_2'),('p_0_2', 'p_0_3'),('p_1_1','p_1_2'),('p_1_2','p_1_3'),('p_1_3','p_0_2'),('p_2_1','p_2_2'),('p_2_1','p_1_2'),('p_2_2','p_2_3')]

Merci d'avance pour vos réponse.

Cordialement.

Salut,

Dans un graphe orienté la notion de prédécesseur et de successeur est "locale". Chaque nœud pourra avoir n prédécesseurs et m successeurs, mais je ne vois pas trop comment vous allez pouvoir en sortir une "place" i.e. une position dans un chemin.

Et si vous écrivez un code comme:
Code:

1 2 3 4 5 6 for n in directed_graph.nodes(): for pred in directed_graph.predecessors(n): directed_graph.nodes[n]['estampille']=10 if 'estampille' not in directed_graph.nodes[n]: directed_graph.nodes[n]['estampille']=1 noeudSansPred.append(n)
Quel est l’intérêt d'exécuter directed_graph.nodes[n]['estampille']=10 pour chaque prédecesseur? Il serait plus simple de regarder len(directed_graph.predecessors(n)).

Puis:
Code:

1 2 3 4 5 6 7 for n in directed_graph.nodes(): est = 1 for suiv in directed_graph.nodes(): if suiv not in noeudSansPred: est = est +1 passe.append(n) directed_graph.nodes[suiv]['estampille']=est
n'éclaire pas plus sur ce que vous voulez faire.

- W

Citation:

Envoyé par wiztricks

Salut,

Dans un graphe orienté la notion ....

La partie du code suivant :
Code:

1 2 3 4 5 6 for n in directed_graph.nodes(): for pred in directed_graph.predecessors(n): directed_graph.nodes[n]['estampille']=10 if 'estampille' not in directed_graph.nodes[n]: directed_graph.nodes[n]['estampille']=1 noeudSansPred.append(n)
Me permet de trouver les sommet sans prédécesseur et de les retenir grace au tableau "noeudSansPred".

La seconde partie du code :
Code:

1 2 3 4 5 6 7 for n in directed_graph.nodes(): est = 1 for suiv in directed_graph.nodes(): if suiv not in noeudSansPred: est = est +1 passe.append(n) directed_graph.nodes[suiv]['estampille']=est
et la partie qui est censé numéroter les successeurs, mais ça numérote seulement en fonction du parcours ...

Citation:

Envoyé par hamster18

et la partie qui est censé numéroter les successeurs, mais ça numérote seulement en fonction du parcours ...

Censée peut être mais outre que çà ne marche pas, çà n'éclaire pas sur ce que vous voulez, c'est insensé: c'est supposé faire quelque chose dont on ne comprend peut être pas le sens.

Dessiner un graphe avec quelques nœuds et arcs et essayer de visualiser ce que vous cherchez à faire pourrait vous aider...

- W