Discussion :

[maxime93]

Bonjour ,
je cherche a faire un alogorithme de tri topologique de graphe et je galère pour ça...je comprends meme pas comment me procédé pour le faire...
si quelqu'un peu me donné un coup de main ..

merci d'avance

[Trap D]

Ben, je n'y connais rien, mais avec Google j'ai déjà trouvé ça
En espérant que ça t'aide

[Nemerle]

TrapD, tu fais la secrétaire maintenant?

[borisd]

Une manière de faire qui devrait fonctionner :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
Pour chaque sommet i faire
  d[i] <- degré intérieur de i, niveau[i] <-0
Fin Pour
Pour i de 1 au nombre de sommets faire
  Chercher un sommet j tel que d[j]=0
  S'il n'en existe pas, le graphe comporte un cycle.
  Sinon
    d[j]<- -1
    Pour tout sommet x successeur de j faire
      d[x] <- d[x]-1 ; niveau[x] <- max(niveau[x],niveau[j]+1)
    Fin Pour
  Fin Si
Fin Pour

[mchk0123]

Une autre façon de faire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
Compute and store the in degree d[j] for each j
  (this is the number of i's for which i -> j). 
 
Initialise a collection (typically a queue or a stack, doesn't matter which)
  C to {j : d[j] == 0}. 
While C is not empty: 
  Remove some element i from C. 
  Output i. 
  For each j such that i -> j, decrement d[d];
    if this zeros it, add j to C. 
    If we output n values in the previous step, the sort succeeded;
    otherwise it failed, and a loop exists in the input.

[borisd]

A part les erreurs d'indentation, j'ai du mal à voir la différence avec ma proposition

[maxime93]

merci pou les réponses .

en fait je dois faire un tri topologique entre 3 élements :

1-nkernel
2 nkbsp (qui attend la construction de nkernel )
3- nkconf (lui il a pas de dependance particulieur)

comment je peux procéder pour fiare mon algo en python si quelqu'un peux m'aider!

[borisd]

L'algorithme que j'ai donné s'applique à un graphe.
Il suffit de transformer tes "nkernel", "nkbsp"... en graphe, puis d'appliquer l'algo.
J'avoue que ta précision n'est pas très claire pour moi .Tu n'as que trois éléments, c'est-à-dire que trois sommets ? Pourquoi tu cherches à faire un tri topologique ?

[maxime93]

c'est vrai que je suis pas trés précis.

en réalité j'ai plus d'éléments que ça,je veux pas compliqué le probleme pour l'instant ,car c'est la premier fois que j'aborde le probleme et j'ai du mal , mais aprés je vais l'appliqué a tout les éléments que j'ai ,aumois 150 sommets,mais deja je vais commencer par cette étape .
je te donne un code que j'ai pensé l'ecrire en python et donner moi votre avis

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
Graphe=('nkernel','nkbsp','nkconf')  #ma liste
function tri_top(Graphe) :
 for i in len(Graph) #sert a parcourire la liste

apres je sais pas comment faire la suite sachant que nkbsp depand de nkernel
et nkonf ne depand pas des deux
si vous avez une idées donnez la moi svp?

[borisd]

Je ne connais pas Python, désolé. Je peux tout de même de donner des pistes.

Tu as besoin d'un moyen de connaître, pour chaque sommet x (ou "élément"), tous ses successeurs (éléments devant obligatoirement attendre la fin de x pour démarrer) et le nombre de ses prédécesseurs (dans l'algo que j'ai donné, c'est le "degré intérieur" du sommet ; d'ailleurs on dit plutôt "demi-degré intérieur" ; les prédecesseurs sont les éléments qui doivent se terminer avant que x ne commence.

Des éléments sans lien entre eux ne figurent simplement pas dans leurs listes de successeurs mutuelles.

Ce sont ces informations que tu dois stocker dans ta structure de graphe (ici, tu peux donc implémenter un graphe comme un tableau de listes (une par sommet) ; ajoute un tableau d'entier pour l'efficacité de l'algo ("d" dans l'algo)).

Une fois que tu auras construit cette structure, tu pourras appliquer l'algo directement.

[maxime93]

merci je vais essayé pour voir ce que sa va donné
je te tiens au courant

[maxime93]

je galer encore dans la construction du code peut etre je maitrise pas ou je comprends pas trop comment ça marche le tri topologique

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
#!/usr/bin/env python  
 
import os 
import sys 
class Graph : 
  list_component=['nkernel','nkbsp','nkconf']
  list_successeur=[list_component[1],'0','0']
  list_predecesseur=['0',list_component[0],'0']
  list_void=[ ] 
  list_void.append('toto')
  print list_component,list_predecesseur,list_successeur
  #def function(self):
  print list_void 
 
  for i in range(len(list_component)):
     print 'je suis dedans '
     if list_predecesseur[i] != 0 :
        print 'graph comporte un cycle '
     else : 
        list_predecesseur[i] = -1
 
        list_successeur[i]= list_predecesseur[i] -

je n'arrive pas encore!!

[borisd]

Je ne connais pas Python, mais il me semble que tu traduis l'algo vraiment de façon vague.
Pas étonnant que ça ne marche pas, peut-être qu'avec un petit effort ça marchera une fois l'algorithme implémenté intégralement (il manque au moins deux boucles pour...).

[maxime93]

est ce que tu peut me le faire avec un autres langage si tu peux biensur

comme ça je vais faire la conversion c'est plus pratique pour moi

merci pour la réponse

[borisd]

Je te l'ai déjà écrit en pseudo-code et tu n'as déjà plus qu'à traduire.
Qu'est-ce que tu n'arrives pas à traduire dans cet algo ?

[maxime93]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
Sinon
    d[j]<- -1
    Pour tout sommet x successeur de j faire
      d[x] <- d[x]-1 ; niveau[x] <- max(niveau[x],niveau[j]+1)
    Fin Pour

j'arrive pas a traduire cette partie
je reprends dés le debut

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
Pour chaque sommet i faire   /*pour parcourir notre liste d'element */
   d[i] <- degré intérieur de i, niveau[i] <-0 /*je comprend pas */
Fin Pour
Pour i de 1 au nombre de sommets faire /* boucle for de 1 a nbre de sommet*/
  Chercher un sommet j tel que d[j]=0 
  S'il n'en existe pas, le graphe comporte un cycle.
  Sinon
    d[j]<- -1
    Pour tout sommet x successeur de j faire
      d[x] <- d[x]-1 ; niveau[x] <- max(niveau[x],niveau[j]+1)
    Fin Pour
  Fin Si
Fin Pour la dernier partie je comprens pas

[borisd]

J'ai oublié de préciser qu'on utilise un troisième tableau "niveau" qui stocke le niveau de chaque sommet : un sommet de niveau 0 n'a pas de successeur, un élément de niveau 1 doit s'exécuter après au moins un élément du niveau 0, un élément de niveau 2 doit s'exécuter après au moins un élement du niveau 1...

On peut aussi dire ça comme ça : le tri topologique du graphe permet (entre autres) de représenter ton graphe en mettant les sommets sans successeurs alignés en couche tout à gauche (niveau 0), puis, sur une couche immédiatement à leur droite, les sommets qui n'ont pas d'autres prédecesseurs que des sommets de niveau 0 (niveau 1), puis ceux qui n'ont pas d'autres prédecesseurs que des sommets de niveau 0 ou 1 (niveau 2)... Tous les sommets ont alors leurs ancêtres à leur gauche, et leurs descendants à leur droite.
Tu obtiens ainsi des "couches" de sommets appelées niveaux.

L'algorithme procède en recherchant un sommet sans prédecesseur (de demi-degré intérieur nul).
En supposant qu'on en trouve un (c'est toujours le cas si le graphe n'a pas de cycle), on le supprime virtuellement du graphe (en décrémentant les demi-degrés intérieurs de ses successeurs). A ce moment, on sait que chacun de ses successeurs sera de niveau strictement supérieur au sien ; on les met donc à jour.
On recommence jusqu'à ce qu'on ait traité tous les sommets, et c'est fini !

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
// on initialise les deux tableaux
Pour chaque sommet i faire
  d[i] <- degré intérieur de i
  niveau[i] <-0
Fin Pour
// on traite tous les sommets du graphe
Pour i de 1 au nombre de sommets faire
  // on cherche un sommet sans prédécesseur -> boucle Pour ou Tant que parcourant le tableau d
  Chercher un sommet j tel que d[j]=0
  S'il n'en existe pas, le graphe comporte un cycle.
  Sinon
    // on supprime virtuellement le sommet j du graphe
    d[j]<- -1
    // on met à jour les infos de ses successeurs (on parcourt la liste de successeurs de j, stockée dans le tableau des successeurs)
    Pour tout sommet x successeur de j faire
      // les successeurs de j ont maintenant un prédécesseur de moins      
      d[x] <- d[x]-1
      // et sont de niveau au moins égal à celui de j plus un
      niveau[x] <- max(niveau[x],niveau[j]+1)
    Fin Pour
  Fin Si
Fin Pour