Discussion :

[sebus]

Bonjour,

Je cherche des algorithmes sur les graphes et plus précisément les DAG.
Mon premier besoin et but et de montrer qu'un graphe est un DAG, mais j'arrive plus a me souvenir de la méthode !!!

Quelqu'un sait il ou il y aurait un bon lien vers de telles informations? (Désolé mais j'ai pas trouvé dans FAQ ni les liens conseillés...)

Si ca n'existe pas, ne faudrait il pas crée un mémo pour rassembler tout les algos? (Stable, bipolaire et autre....)

[progfou]

Tu peux traduire DAG ?

[sebus]

DAG = Direct Acyclic Graph

Donc un graphe orienté sans cycle

[millie]

Des parcours en profondeur devrait suffir. Si lors d'un parcours tu retombes sur le sommet initial, c'est que la partie du graphe la n'etait pas acyclique.

[sebus]

Je suis d'accord mais ca oblige a faire un parcours en profondeur par sommet ......

Et comme je risque d'avoir plusieurs millier de sommets....

Sinon y'a pas moyen d'optimiser un peu le truc ? Je sais qu'il existe un algo minimal, mais je m'en souviens plus (j'ai completement oublié tous mes précieux cours d'algo et de théorie des graphes de la fac....)

Sinon une FAQ special Graphe ca existe? Ou serait il interessant d'en créer une ? (arbre, graphe, DAG + théorie avec stable, coloration, bipolarité, parcours, flots et autres)

[borisd]

Tu as moins de parcours en profondeur à faire qu'un par sommet : tu n'as besoin de recommencer qu'à partir d'un sommet non marqué par les parcours précédents. La complexité globale est de O(M), M étant le nombre d'arcs, ce qui est déjà assez faible.

[sebus]

Si je reprend ton idée borisd:

Si mon premier parcours commence à partir de la racine, je risque de tout couvrir sans savoir s'il n'y a pas de cycle entre d'autre noeud du graphe...


Pourrais tu être plus précis ?

Parceque mon probleme est que je risque de passr plusieurs fois par un noeud lors d'un parcours en profondeur sans qu'il n'y ait de cycle....

Dois je utiliser 2 marqueurs par noeud alors ?

[millie]

Sinon une FAQ special Graphe ca existe?

Une cours introductif sur les graphes est en préparation par l'un des membres de developpez.com. Le premier jet de ce cours devrait définir les notions de base, les implémentations possibles des graphes et leur parcours.

Ou serait il interessant d'en créer une ? (arbre, graphe, DAG + théorie avec stable, coloration, bipolarité, parcours, flots et autres)

Oui, effectivement, il serait intéressant d'aborder toutes ces théories. Si tu souhaites contribuer à un cours sur ces notions, tu es le bienvenu Certains d'entre nous ont les connaissances pour réaliser un cours sur certaines de ces parties, mais nous n'avons pas forcement le temps car on travaille en général sur d'autres choses à côté.

[borisd]

Tu as un tableau de marques qui indique si un sommet a été visité par un des parcours en profondeur. Il est inutile d'empiler ces sommets puisque leur fermeture transitive a déjà été explorée.

A une étape d'un parcours en profondeur, il existe un cycle dans ton graphe si un successeur du sommet courant se trouve déjà dans la pile.

J'en suis convaincu pour l'instant, mais depuis quelques temps j'écris des boulettes en répétition sur ce forum, alors si quelqu'un a une réponse sûre, elle est la bienvenue.

[sebus]

j'en suis pas convaincu car un DAG peut avoir des chemins qui fusionnent au bout dun certain temps .......

Donc si un chemin est plus rapide que l'autre, quand tu vas passer pour la deuxieme fois sur le sommet, tu vas voir que tu y ai déjà passé donc tu vas dire qu'il y a un cycle, or ce n'est pas vrai .....

Si ton idée est plus profonde que ce que j'en ai compris, peut tu détailler un peu plus ton algo ?

[FrancisSourd]

En attendant le cours introductif de developpez.com, tu peux regarder ce livre en ligne
http://www-igm.univ-mlv.fr/%7Eberste.../Elements.html
Chapitre 4, Section 4.4.4

[borisd]

Il n'y a un cycle que si un successeur du sommet courant se situe déjà dans la pile (et il te faudrait donc en toute logique réempiler les mêmes sommets -> cycle).
Tu dois donc gérer deux types de marque : une marque qui indique si oui ou non le sommet a été visité une fois, et une autre qui indique si le sommet se trouve dans la pile (i.e. dans l'arbre en cours d'exploration).

Un exemple d'implémentation :

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
 
Pour tout sommet i
  marque[i] <- faux;dansPile[i] <- faux
Fin pour
Tant qu'il existe un sommet s non marqué
  empiler s
  marque[s] <- vrai;  num[s] <- 1; dansPile[s] <- vrai
  Répéter
    x <- sommet de la pile
    chercher y, premier succ de x à partir de num[x], tel que dansPile[y]=Vrai
    Si y existe, alors il existe un cycle (y,...,x,y)
    Sinon
      chercher y, premier succ de x tel que non marque[y], à partir de num[x]
      Si y existe alors
        marque[y] <- vrai
        empiler y ; dansPile[y] <- vrai
        num[y]<-1 ; num[x] <- y+1
      Sinon
        dépiler x ; dansPile[x] <- faux
      FinSi
    Fin Si
  Jusqu'à ce que la pile soit vide
Fin Tant Que

Les deux recherches de y peuvent être fusionnées pour plus d'efficacité, je les ai distinguées pour la simplicité d'écriture.

[sebus]

J'ai pas le temps de le lire la ca r je suis au boulot, mais c clair que ton lien semble extrememnt interessant !!!!!

Il a l'air super bien fait !!!

A conseiller a bcp de monde (en plus ca me semble pas mal complet sur les théories de base....)

[sebus]

Ok je te comprends mieux Boris !!!

Il me semblait bien qu'il fallait utiliser 2 marqueurs par sommet .....

[sebus]

Bon je viens de tester ton algo sur un exemple Boris, et voila ce que je propose (je simplifie ta version) :

Objets/variables : une pile (comme tu le proposais au début je crois nan?)
un tableau[nombre de sommets] pour cocher les sommets déja vu.
Appelons donc P la pile et vu le tableau, X,Y,Z des sommets du graphe

Pour tout sommet i
vu[i] = faux
Tant qu'il reste un sommets pas encore vu
P.empile (X)
vu[X] = vrai
Tant que la pile n'est pas vide
X = P.dépile //On récupère le sommet
Si X a au moins un fils et que tout les fils sont dans P
IL Y A UN CYCLE
Sinon
Si X a au moins un fils et que vu[X] == faux
vu[X] = vrai
P.empile (X)
Sinon
P.dépile
Fin Si
Fin Tant que (pile non vide)
Fin Tant que



Voili voilou....
Donne moi ton avis sur l'algo, ca m'interesse (la pile c sur il l'a faut, je m'en souviens maintenant !!)

Bonus: Comme je fais le test sur DAG, et que mon DAG possède une racine (un sommet source/de départ), Je dois normalement faire une seule passe dans le premier tant que (tat qu'il y a des sommets non vus), il devient donc inutile.......
C vrai ca?

[borisd]

Je ne suis pas vraiment d'accord en général, mais peut-être qu'avec les balises CODE et un peu d'indentation j'aurais mieux compris ?

Si X a au moins un fils et que tout les fils sont dans P
IL Y A UN CYCLE

Je ne comprends pas cette partie. Tous les fils de qui ? Il suffit que le sommet au sommet de la pile ait un successeur déjà dans la pile pour qu'il y ait un cycle.

Je ne comprends pas non plus certaines parties de l'algo ambigües (variable X représentant à la fois un sommet et son successeur...).

Par ailleurs, le tableau Num est utile : il permet de repartir directement au prochain successeur après dépilement, sans avoir à recontrôler certains sommets déjà parcourus (bien que cela fonctionne sans, c'est moins efficace).

Bonus: Comme je fais le test sur DAG, et que mon DAG possède une racine (un sommet source/de départ), Je dois normalement faire une seule passe dans le premier tant que (tat qu'il y a des sommets non vus), il devient donc inutile.......
C vrai ca?

Oui, ça c'est vrai. C'est la seule simplification que je ferais à ta place (mais je n'y suis pas ).

[sebus]

OUPS pour l'algo !!!
Je l'avais bien écris mais j'ai zappe les BALISE CODE

Je recommence

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
 
Pour tout sommet i
    vu[i] = faux
Tant qu'il reste un sommets pas encore vu
    P.empile (X)
    vu[X] = vrai
    Tant que la pile n'est pas vide
        Y = P.dépile //On récupère le sommet
        Si Y a au moins un successeur et que l'un d'entre eux est dans P
            IL Y A UN CYCLE
        Sinon
            Si y a au moins un successeur et que vu[y] == faux
                vu[Y] = vrai
                P.empile (y)
            Sinon
                P.dépile
        Fin Si
    Fin Tant que (pile non vide)
Fin Tant que

Suis je plus clair?

Il suffit que le sommet au sommet de la pile ait un successeur déjà dans la pile pour qu'il y ait un cycle.

Ok exact, suffit d'avoir un successeur dans la pile pour avoir un cycle !!

Sinon a mon avis le tablueau num sert surtout pour l'implementation pour l'ordinateur nan? (sinon j'e l'ai pas compris)

[borisd]

C'est plus clair, oui

Est-ce que par

Code :

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

Si y a au moins un successeur et que vu[y] == faux

tu n'entendrais pas par hasard :

Code :

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

Si y a au moins un successeur z et que vu[z] == faux

(et après, empiler(z),...)

Un petit exemple pour l'utilité de Num : imagine un arbre dont la racine R comporte 500 successeurs.
Tu explores la première branche, la deuxième... arrivé à la 500ème, après avoir dépilé le 499è successeur de R, tu recherches un successeur de R non visité. Tu vas donc forcément parcourir les 499 premiers avant d'enfin tomber sur le dernier.

Si tu avais stocké quelque part où tu étais rendu (Num[R]=500), tu aurais poursuivi ta recherche directement au 500ème successeur. Si tu as un graphe gros et dense, la différence se voit.

[sebus]

Est-ce que par

Code :
Si y a au moins un successeur et que vu[y] == fauxtu n'entendrais pas par hasard :

Code :
Si y a au moins un successeur z et que vu[z] == faux(et après, empiler(z),...)

Oui c exactement ca !!
J'ai perdu l'habitude d'écrire des algos ....

Sinon c ok pour num, j'i pigé maintenant

MERCI