Quelqu’un qui connait de bonnes références en matière d’algo pour graphe ( orienté de preference 
). J’ai pondu un algo de detection de cycle, mais bon moi et l’algorithmie ça fait deux…
Merci de votre pitié
–Fluidz
Bien sympa ce POST de Gloppy, ça fait du bien de lire des choses intéressantes :pleure: . Je vais rappeler une chose importante (comme l’a également rappelé Glop) :
Et évidemment c’est valable quelque soit le domaine :pleure:
Aller hop un autre site : http://llaic3.u-clermont1.fr/~mr/livreinfog/livreinfog.shtml
Profitons de ce thread pour balancer des sites d’algos :pleure:
un autre site tres riche sur le A* et autre methode:
http://www-cs-students.stanford.edu/~amitp/gameprog.html
Thx pour le lien et les précisions !
Oui tout a fait :pleure: Les plus rapide en general sont Dijkstra, Floyd qui est plus rapide en pratique d’un constante si on fait Dijkstra sur tout les noeuds et Bellman-Ford qui est valable pour les graphes avec des arc de poids negatif. Le plus rapide theorique, toute categorie confondue est Dijkstra en utilisant les piles (heap) de Fibonacci.
Ca c’est pour les solution exactes, pour une solution approchee on peut utiliser A* pour calculer plus rapidement et confirmer/affiner le resultat si on a du temps CPU avec un Dijkstra.
Enfin pour resumer tout est dans les structures de donnees. C’est la qu’un bel algo se fait tuer ou montre a quel point il est rapide :pleure: Allez un lien sympa d’un super site si vous connaissez pas encore: http://ai-depot.com/BotNavigation/Path.html
[Edité le 23/2/2003 par GloP]
Yep, bah vala, ce que tu fais, c’est une recherche des composantes fortements connexes, sauf que l’algo est modifié un chouia pour virer les arêtes qui font chier :pleure: Pile poil ce que j’ai fait il y a 15 jours en algo, sauf que mes arêtes étaient pas valuées (ça change pas grand chose)
[quote]Sinon l’autre algo super utile pour les graphe est l’algo qui permet de trouver le chemin le plus court entre deux noeuds dans un graphe oriente. L’ago malin est l’algo de Dijkstra. Il est super interessant de noter que cet algo trouve non seulement le chemin le plus court entre deux liens, mais tout les chemins les plus courts entre tout les liens (malin).[/quote]Waip, mais dans les jeux, c’est pas cool dkijkstra, faut utiliser A*, ou un mix des deux, je crois.
Bah c’est surtout qu’il n’est pas 3h12 pour lui :-/
J’aurai peut-etre du préciser que mes graphes sont pas valués et que je faisait déja un parcours à l’aide de l’algo de prim’ :-/. Le fait qu’il y ai pas de valuation, il me semble, change pas mal de truc ( surtout pour l’algo que t’a detaillé ). Mais je pense que ce que tu voulais dire c’est que le concept est adaptable ( sinon je te suis plus ). Merci pour le soucis du détail !
ps : je suis impressionné qu’à 3h12 quelqu’un me fasse un cour de graph 
( une holaa pour GloP ! )
Bon je me devoue alors.
Bon alors les definitions habituelles d’abord.
Avec un graphe G = (V, E)
avec V la liste de nodes et E la liste des liens (edge). E est compose de couple Vi Vj qui definissent un lien entre deux nodes.
Un chemin (path) P est une suite de liste de node ou chaque Vi,Vi+1 est dans E.
Donc avec tout ca on peut definir un cycle tel que un chemin de longueur non nulle
Pcycle = tel que V0=Vk
Les algos les plus utilises sont des algo « gourmands » ca veut dire que a chaque etape ils ne font que considerer les nodes qui sont a cote du node en court. Jamais ils ne vont voir plus loin. Il est assez difficile de prouver que ces algo donnent une solution optimale et la preuve se fait generalement par l’absurde.
Il est super super super important de noter qu’il ne sert a rien de reinventer la roue pour ecrire ces algorithmes. La plupart des algos que tu vas pouvoir pondre vont etre en O(n!) ce qui est carrement a la limite de la catastrophe. Je te conseille des recherches sur le net pour trouver la plupart des algo qui ont ete inventes pour trouver des solutions optimales.
En general quand on cherche un cylce dans un graphe le but c’est de trouver le sous arbre minimum optimal (je sais pas si c’est le terme exact en francais c’est loin tout ca), cad dans un graphe quel est le chemin minimal et de moindre cout tel que d’un noeud on puisse toujours en rejoindre un autre, il faut utiliser les algos dit de Kruskal ou l’algo de Prim. Ils sont repspectivement en O(n^2log(n)) et en O(nlog(n)) pour les cas ou E est proche de V. C’est en general pour faire un de ces deux algo la que tu veux empecher la creation de cycles, puisque tu veux creer exactement V-1 liens, par un de plus, et que donc un cycle serait une perte.
Bon je vais detailler Kruskal pour trouver cet arbre minimal c’est le plus simple.
L’ago consiste a faire les etapes suivantes:
- Construire une foret d’arbre contenant chacun un seul noeud du graphe (a la fin on aura un seul arbre dans la foret, la solution)
- Trier les liens (edges) par ordre de cout et les placer dans une pile
- Tant qu’on a pas rajoute n-1 liens (edge) a la foret (ce qui joint deux arbres):
a) ectraire le noeud le moins cher de la pile
B) si il forme un cycle, le rejeter
c) sinon le rajouter a la foret, creeant ainsi un lien entre deux arbres
On voit que chaque etape rejoint deux arbres, donc on voit bien qu’a la fin il n’en reste qu’un (highlander style).
Bon on en vient a ton probleme,la, trouver si on cree un cycle en rajoutant un lien entre deux arbres. Pour ca on utilise un union-find. Definissons une partition. Une partition est un decoupage d’un jeu d’elements tel que chaque element appartien a un et un seul sous jeu du jeu original. Quand on a cree la foret au debut on a cree une partition des noeuds et l’operation qui consiste a rajouter un lien consiste a faire l’union de ces deux jeux d’elements.
Chaque jeu d’element represente ce qu’on peut appeller une classe d’equivalence. Appartenant au meme jeu, ils represente tous la meme chose et forment donc une classe, on peut choisir un des element de chaque sous jeu comme representant de la classe d’equivalence formee par le sous-jeu. Au niveau algo, quand tu ajoutes un noeud dans un sous-jeu tu fais que chaque element pointe vers le representant de son sous-jeu. Quand tu fais l’union de deux sous-jeux tu fais juste en sorte que le representant d’un des sous-jeu pointe vers n’importe quel autre des element de l’autre sous-jeu. (Ouai c’est imbitable a lire mais c’est simple en fait).
Donc pour detecter si t’as un cylce tu as juste a faire en sorte que quand tu veux savoir si tu dois ajouter un lien entre deux noeud V1 et V2, tu trouve le representant de V1, celui de V2. Si ils ont les meme representants: c’est un cycle ! (ils sont dans la meme classe d’equivalence, tu es en train d’essayer de te lier a toi meme dans le sous jeu: c’est un cylce).
Comment trouver un representant? Tu suis la liste de liens. Au depart si il y a un seul noeud par arbre (sous-jeu), chaque noeud est son propre representant… Donc le pointer de chaque noeud qui pointe vers son representant est mis a null. Quand tu rejoins deux noeud pour former un arbre, tu en choisit un des deux au pif, pour devenir le representant de la classe. C’est a dire que tu prend un des deux pointeur et tu le fais pointer vers l’autre noeud. Pas de prise de tete… Quand tu veux faire l’union entre deux sous jeux c’est super simple, tu prend le representatif du premier sous jeu (celui qui a null dans son pointeur et vers lequel la fin de la chaine de pointeurs « representant » du sous jeu pointe) et tu le fais pointer vers n’importe quel element du deuxieme jeu… (bien sur les recherche sont plus rapide si tu fais pointer directement vers le representant du deuxieme jeu, mais on s’en fout a la limite…).
Voila c’est ca l’algo. Bon un exemple pour mieux comprendre… Il y a 10 etapes alors on s’accroche. J’ai ehontement repompe les images sur un autre site alors pas de honte :-/
gh est le plus court, on choisit g comme representant (au pif)
ci est le suivant, et on a deux arbres independants, c est pris comme representant du deuxieme arbre
fg est le suivant. cette fois ca rajoute au premier arbre. on prend g comme representant.
ab est le suivant le moins cher. ca cree un 3eme arbre. on choisit un representant (B).
cf est le suivant. ca fais une jointure entre deux arbres! on choisit c, comme le nouveau representant du nouveau plus gros arbre.
gi est le suivant. MAIS! ca creerait un cycle (ils ont le meme representant c)
on prend donc le suivant : cd
pareil hi ferait un cycle, donc
on prend ah
bc ferait un cycle, on prend de et magie on a rajoute n-1 liens, on a une seule classe d’equivalence (tout les liens sont accessible a partir de n’importe quel autre et c est l’unique representant de la classe d’equivalence youpi tralalala a poil pour feter ca.)
Voila ! J’espere que c’est vaguement ce que tu cherchais comme explication sinon je viens de me faire chier pour rien C’est pas grave ca m’aura fait reviser hehe.
Sinon l’autre algo super utile pour les graphe est l’algo qui permet de trouver le chemin le plus court entre deux noeuds dans un graphe oriente. L’ago malin est l’algo de Dijkstra. Il est super interessant de noter que cet algo trouve non seulement le chemin le plus court entre deux liens, mais tout les chemins les plus courts entre tout les liens (malin).
Un simple recherche google devrait t’aider a trouver des exemples d’implementation de chacun de ces deux algo avec le source et tout et tout. C’est super classique comme probleme et meme en francais, ca doit se trouver.
Voila !! Desole pour les explications pourries, faite a l’arrache vite fait pour faire le post le plus long du monde ! On pourrait presque en faire un article si je m’etais pas inspire sauvagement de plusieurs articles sur le net pour me rafraichir la memoire 
Plagiat is good
ouaip ! Tremaux a bossé la-dessus on dirait .
Bon je pense etre plus rapide que lui dans la mesure ou l’algo que j’ai écrit regarde seulement la partie du graphe que je vient de modifier… Pour etre plus précis le but de l’algo : dire si en ajoutant une arrete on creer un cycle.
Je vais continuer à fouiner dans ce sens. :-/
Merci.
Tu peux pas faire “simplement” une détection des composantes fortements connexes de ton graphe ?
Puisque dès qu’il y a un cycle, il y a une composante fortement connexe…
J’ai fait un bide là :-/
Glop, il me troue le cul. C’est exactement ce que je cherchais pour l’examen que j’ai lundi !