Version imprimable
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....)
Tu peux traduire DAG ?
DAG = Direct Acyclic Graph
Donc un graphe orienté sans cycle
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.
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)
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.
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 ?
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.Citation:
Envoyé par sebus
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 :D 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é.Citation:
Ou serait il interessant d'en créer une ? (arbre, graphe, DAG + théorie avec stable, coloration, bipolarité, parcours, flots et autres)
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.
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 ?
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
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 :
Les deux recherches de y peuvent être fusionnées pour plus d'efficacité, je les ai distinguées pour la simplicité d'écriture.Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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....)
Ok je te comprends mieux Boris !!!
Il me semblait bien qu'il fallait utiliser 2 marqueurs par sommet .....
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?
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 ?
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.Citation:
Envoyé par sebus
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).
Oui, ça c'est vrai. C'est la seule simplification que je ferais à ta place (mais je n'y suis pas :mouarf: ).Citation:
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?
OUPS pour l'algo !!!
Je l'avais bien écris mais j'ai zappe les BALISE CODE
Je recommence
Suis je plus clair?Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Ok exact, suffit d'avoir un successeur dans la pile pour avoir un cycle !!Citation:
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.
Sinon a mon avis le tablueau num sert surtout pour l'implementation pour l'ordinateur nan? (sinon j'e l'ai pas compris)
C'est plus clair, oui ;)
Est-ce que par
tu n'entendrais pas par hasard :Code:Si y a au moins un successeur et que vu[y] == faux
(et après, empiler(z),...)Code:Si y a au moins un successeur z et que vu[z] == faux
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.
Oui c exactement ca !!Citation:
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),...)
J'ai perdu l'habitude d'écrire des algos ....
Sinon c ok pour num, j'i pigé maintenant ;)
MERCI