Bonjour !
 
Certains d'entre vous se souviennent un jour sans doute, dans votre jeunesse, ou alors en ce moment même   , avoir du faire vos premiers pas en C à la fac (voire plus tôt). Et un jour votre prof d'info chéri vous a demandé de lui rendre un bo projet totu bo et pas trop buggé avant al fin de l'année. Ben vala, aujourd'hui, c'est mon tour    
 
Le projet que je réalise conjointement avec deux copains de la promotion (de licence info), c'est un programme de gestion de graphe, composé des éléments classiques que sont les sommets, les arêtes et les "jetons" (objets que l'on dépose dans les sommets et qui se déplacent de sommets en sommets via les arêtes donc). Et pour motiver un peu la foule, on a aussi pour mission de faire de ce programme un mini-RPG, en assimilant les sommets à des salles ou lieux, les arêtes à des chemins, et les jetons à des personnages. Avec en plus une gestion d'attributs pour chacune de ces structures, on peut parvenir à en faire un truc "sympa" (l'espace de 10 minutes, le  temps que l'émerveillement d'avoir écrit un code qui bug pas passe . On "peut" parvenir, parce que le projet n'est pas tout à fait achevé, à cause d'un petit problème, lié à une fonction du graphe.
Le prof nous a demandé d'implanter une fonction chargée d'identifier dans le graphe ses composantes fortement connexes (ou SCCs pour Strongly Connected Components), et d'utiliser pour cela l'algorithme de Tarjan, qu'il nous a donné. Du fait de sa "simplicité", son implémentation ne pose pas vraiment de problème, mais ce qui me pose problème, c'est qu'il ne semble pas correct.
En effet, dans certains cas, il fournit les bons indices de Tarjan qui permettent de constituer les SCCs ... et d'entre d'autres cas non. Comme ce n'est sans doute pas très clair, je vais poster dans le message suivant un exemple de graph dans lequel ça ne marche pas.
Les raisons ne sont sans doute pas nombreuses : ou alors mon implémentation n'est pas correcte (toujours possible), ou alors mon algo ne l'est pas ... et s'agissant d'un problème assez classique, j'espère qu'il en sera parmi vous qui pourront me corriger !
 
Merci d'avance.

Le principe de l'algo de Tarjan est le suivant : les sommets du graph sont parcourus et numérotés de telle sorte que tous les
sommets faisant parti d?une même composante fortement connexe se voient attribuer une même valeur.
 
Il se décompose en trois parties, l?une ou les numéros (indices) des sommets sont initialisés à 0, suivi d?un premier passage sur tous les sommets qui leur attribue leur premier indice, puis un second qui "met à jour" les premiers indices attribués par le passage précédent.
 
 
 
Ci-après des extraits du code utilisé :
 
 
DFS1 : Depth First Search 1, c?est là qu?on affecte à chaque sommet du graph son premier indice de Tarjan.
 
DFS2  qui est appellé par Tarjan et n?est pas ici présent, est codé de la même manière, avec le paramètre entier en moins.
 
 
 
 
 
int LinfGraph_DFS1 (LinfVertex *V, int *n1)              /* n1 est un int* car il va être modifié   */
 
{
 
  int m, min;
 
  LinfListCursor *cursor ;
 
  LinfList *targets ;
 
 
 
  if (LinfVertex_FI(V)!=0) {                                        /* Si le 1er indice du sommet n?est pas 0*/
 
    return(LinfVertex_FI(V)) ; } ;                                 /* alors on arrête                                    */
 
  LinfVertex_SetFI (V, *n1) ;                                      /* sinon on lui affecte pour l?instant n1    */
 
  *n1=*n1+1;
 
  min=10000;                                                              /* min doit être fixé à une grande valeur  */
 
                                                                                  /* on suppose que le graph ne comptera */
 
                                                                                  /* pas plus de 10000 sommets                */
 
 
 
  targets=LinfVertex_Targets(V) ;
 
  cursor=LinfListCursor_New(targets) ;
 
 
 
  LinfListCursor_ResetOnFirstItem (cursor) ;               /* les calculs après sont propres à Tarjan */
 
  while (!LinfListCursor_IsAfterLastItem(cursor)) {
 
    m=LinfGraph_DFS1(LinfListCursor_Item(cursor), n1) ;
 
    if (m<min) (min=m) ;
 
    LinfListCursor_Increment (cursor) ;  
 
  }
 
  LinfListCursor_Free (cursor) ;
 
  LinfList_Free(targets) ;
 
  if (min<LinfVertex_FI(V)) LinfVertex_SetFI (V, min) ;
 
  return (LinfVertex_FI(V)) ;
 
}
 
 
 
 
 
 
 
void LinfGraph_Tarjan(LinfGraph *graph)
 
{
 
 
 
  int n=0;
 
  LinfListCursor *cursor ;
 
  LinfVertex *current ;
 
 
 
  if (!graph->Modified) return;                                       /* Tarjan n?est exécuté que si le graph           */
 
                                                                                    /* a été modifié depuis la dernière exécution   */
 
  cursor=LinfListCursor_New (graph->Vertices) ;
 
  LinfListCursor_ResetOnFirstItem(cursor) ;
 
  while (!LinfListCursor_IsAfterLastItem(cursor)) {
 
    current=LinfListCursor_Item (cursor) ;
 
    LinfVertex_SetFI(current,0) ;                                    /* initialisation des indices à 0                         */
 
    LinfVertex_SetSI(current,0) ;
 
    LinfListCursor_Increment (cursor) ;
 
  }
 
 
 
  LinfListCursor_ResetOnFirstItem(cursor) ;
 
  while (!LinfListCursor_IsAfterLastItem(cursor)) {
 
    current=LinfListCursor_Item (cursor) ;                                /* pour chaque sommet du graph          */
 
    LinfVertex_SetFI(current,LinfGraph_DFS1(current, &n)) ;  /* attribution du résultat de DFS1 au    */
 
    LinfListCursor_Increment (cursor) ;                                    /* premier indice du sommet                 */
 
  }
 
 
 
  LinfListCursor_ResetOnFirstItem (cursor) ;
 
  while (!LinfListCursor_IsAfterLastItem(cursor)) {
 
    current=LinfListCursor_Item (cursor) ;                                /* pour chaque sommet du graph           */
 
    LinfVertex_SetSI(current,LinfGraph_DFS2(current)) ;        /* attribution du résultat de DFS2 au      */
 
    LinfListCursor_Increment(cursor) ;                                      /* second indice du sommet                  */
 
  }
 
 
 
  LinfListCursor_Free(cursor) ;
 
  LinfGraphSCC_Scan(graph);              
 
  graph->Modified=0;                          /* indique que Tarjan n?a plus besoin d?être appliqué à condition*/
 
}                                                         /* que le graph ne soit pas modifié (ajout ou suppresion de         */
 
                                                           /* sommet(s) ou d?arête(s)).                                                       */
 
 
 
On voit à la fin du code que LinGraph_Tarjan appelle la fonction LinfGraphSCC_Scan, qui est chargée, après la numérotation des sommets par Tarjan de créer une liste des SCCs du graphe, afin que ceux-ci soient facilement accessibles.
 
 
Si les fonctions et structures employées nécessitent d'être expliquées, n'hésitez pas.
Comment faire pour poster une image ? (je veux dire, la syntaxe pour indiquer le lien?) Pour que je puisse poster le graphe avec lequel il ne fonctionne pas ...
 
P.S. : j'imagine que ce message risque d'être un peu long, et je m'en excuse par avance !

 
 
Désolé pour le post précédent
Au moins il est "clair" même si lisibilité peut mieux faire ... je peux reposter si vous voulez    mais en plus condensé.
 
L'algo donne ça :
 
DFS1(S,n1) :
 
Si S.i1!=0 retourner (S.i1);
S.i1<-n1;   n1<-n1+1;  min=[+oo] (une valeur sup à n1 en tt cas)
pour tous les sommets T tels qu'il existe un chemin de S à T,
   m<-DFS1(t,n1);
   si (m<min) min<-m;
si min<S.i1   S.i1<-min;
retourner (S.i1);
 
 
DFS2(S) :
Si S.i2!=0 retourner (S.i2);
S.i1<-S.i1;  min=[+oo] (une valeur sup à n1 en tt cas)
pour tous les sommets T tels qu'il existe un chemin de S à T,
   m<-DFS2(t);
   si (m<min) min<-m;
si min<S.i2   S.i2<-min;
retourner (S.i2);
 
 
Tarjan :
pour tous les sommets S du graphe
   S.i1<-0;   S.i2<-0;
n<-0;
pour tous les sommets S
   DFS1(S,n);
pour tous les sommets S
   DFS2(S,n);
 
 
et voilà ...
 
P.S. : j'ai tout de même effectué une rechercher sur ce forum avec les mots Tarjan et +Composante +Connexe, sans succès. J'ai également recherché sur Google, dans les groupes, où on indiquait des liens vers des sources sur des ftps qui n'existent plus, et sur le web, où j'ai bien des pages qui donnent des implémentations, mais ça ne m'a pas aidé à corriger ma version ...
 

 
Sur ce graphe on distingue assez nettement trois composantes connexes :
SCC1 : les sommets de S1 à S11
SCC2 : les sommets S12, S14 et S15
SCC3 : les sommets S16 à S19
(le sommet S13 est à ignorer).
Lorsque les trois SCCs ne sont pas reliés (pas d'arête S12->S1 et S19->S9), l'algo implanté trouve bien les trois SCCS.
Mais dès que ceux-ci sont reliés par le biais des deux arêtes précédentes, il ne trouve plus qu'une seul gros SCC qui englobe tous les sommets !  
 
Or il n'existe clairement pas de chemin permettant d'allant du SCC1 précédent au deux autres ... mon algo est-il fou ? ou juste faux ? Merci !

[jfdsdjhfuetppo]--Message édité par Zeusy--[/jfdsdjhfuetppo]

D'habitude mes explications sont pas suffisament claires, pour une fois ptêt que j'ai fait un tantinet ... complet    
 
Des 22 vues de ce topic je dois bien en avoir fait ... 22    
 
Y'a-t'y vraiment personne qui peut m'aider ?  

 
je cherche le principe de la recherche des CFC. en simple