Algorithme de tri topologique

Version imprimable

11/04/2007, 11h25
maxime93

Algorithme de tri topologique

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:bug:
11/04/2007, 14h11
Trap D

Ben, je n'y connais rien, mais avec Google j'ai déjà trouvé ça
En espérant que ça t'aide :?
11/04/2007, 14h12
Nemerle

TrapD, tu fais la secrétaire maintenant? ;)

Une manière de faire qui devrait fonctionner :

Code:

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

Une autre façon de faire :

Code:

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.

11/04/2007, 16h48
borisd

A part les erreurs d'indentation, j'ai du mal à voir la différence avec ma proposition ;)
12/04/2007, 09h36
maxime93

merci

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!
12/04/2007, 10h02
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 :aie:.Tu n'as que trois éléments, c'est-à-dire que trois sommets ? Pourquoi tu cherches à faire un tri topologique ?
12/04/2007, 10h57
maxime93

en faite
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:

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?
12/04/2007, 11h09
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.
12/04/2007, 11h11
maxime93

merci

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

je galer encore

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:

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!!:oops:

12/04/2007, 15h24
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...).
12/04/2007, 15h27
maxime93

merci

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
12/04/2007, 15h31
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 ?

Code:

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:

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

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:

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