Application graphes orientés

Bonjour à tous,

Je viens chercher un peu d'aide pour une question qui me turlupine depuis quelques jours (en fait là j'en suis presque à m'arracher les cheveux ;) )...

En effet, admettons un graphe orienté avec un ensemble de sommets et d'arcs orientés. Ce que je cherche à faire avec ce graphe, c'est "tout simplement" déterminer s'il y a un chemin multiple. Ce que j'appelle chemin multiple est par exemple pouvoir aller du sommet 1 au sommet 3 par plusieurs chemins (chemin = ensemble d'arcs).

Exemple avec une liste d'arcs comme ceux-ci :
1->2
1->3
2->3
1->4
4->3

Avec ce graphe orienté, il y a 3 manière d'aller de 1 à 3.
Donc ce que je cherche c'est un algo qui permettrait de détecter dans un graphe orienté s'il y a des chemins multiples (je ne veux pas savoir leur nombre ni leur origine et extrêmité).
J'ai beaucoup réflechi sur le sujet, et je pense que la solution se trouve en utilisant l'algorithme de parcours en profondeur, mais j'ai beau chercher, je ne vois pas comment le modifier/exploiter pour résoudre mon problème...
Donc si l'un d'entre vous aurait une piste à suivre, je serais très reconnaissant parce que je suis à deux doigts de me taper la tête contre les murs :aie:

Merci beaucoup !

Bon, je ne suis pas sur de ce que j'avance, mais dans le cas ou tes chemins multiples sont disjoints (comme dans l'exemple), tu peux essayer ceci :

- lancer un parcours en profondeur (ou en largeur ?)
- si tu trouve un chemin de 1 à 3 (ie. la récursion se termine sur 3),
tu retire de ton graphe tous les arcs de ce chemin
- tu relance le parcours une 2ème fois
- si tu trouve de nouveau un autre chemin, c'est qu'il existe au moins 2 chemins disjoint

:)

Citation:

---

Envoyé par mchk0123

Bon, je ne suis pas sur de ce que j'avance, mais dans le cas ou tes chemins multiples sont disjoints (comme dans l'exemple), tu peux essayer ceci :

- lancer un parcours en profondeur (ou en largeur ?)
- si tu trouve un chemin de 1 à 3 (ie. la récursion se termine sur 3),
tu retire de ton graphe tous les arcs de ce chemin
- tu relance le parcours une 2ème fois
- si tu trouve de nouveau un autre chemin, c'est qu'il existe au moins 2 chemins disjoint

:)

---

Qu'est-ce que des chemins disjoints ?
Le problème est que quand je lance le parcours, je ne sais pas s'il existe un chemin mutliple et encore moins entre quels sommets donc comment savoir si je retire les arcs ?

Ton idée est peut -être bonne mais je n'ai tout simplement pas tout saisi (les graphes c'est vraiment trop abstrait pour moi !).

Deux chemins sont disjoints s'il n'ont en commun aucun point (sauf le point de départ et le point d'arrivée bien sur).

Citation:

---

Envoyé par mchk0123

Deux chemins sont disjoints s'il n'ont en commun aucun point (sauf le point de départ et le point d'arrivée bien sur).

---

Dans ce cas mon exemple était mauvais, les chemims multiples ne sont pas forcément disjoints.

Si tu notes M[i,j] ta matrice d'adjacence (qui vaut 1 en i,j si tu as une arrête i-->j, 0 sinon), alors le nombre de chemins de longueur p de i à j est donné par le coefficient (M^p)[i,j].

Pour rappel, (M^p)[i,j] est la somme des (M^(p-1))[i,k] * M[k,j] sur k.

Ci-joint un lien sympa qui te précise tout ça: http://www.dix.polytechnique.fr/IF/poly/main003.html

Citation:

---

Envoyé par Nemerle

Si tu notes M[i,j] ta matrice d'adjacence (qui vaut 1 en i,j si tu as une arrête i-->j, 0 sinon), alors le nombre de chemins de longueur p de i à j est donné par le coefficient (M^p)[i,j].

Pour rappel, (M^p)[i,j] est la somme des (M^(p-1))[i,k] * M[k,j] sur k.

Ci-joint un lien sympa qui te précise tout ça: http://www.dix.polytechnique.fr/IF/poly/main003.html

---

Ca commence à être intéressant en effet, mais deux bémols :
- je ne connais pas la longueur des éventuels chemins multiples
- dans mon application, les graphes sont implémentés en listes d'adjacence

J'ai vraiment l'impression que je trouverais jamais...:roll:

EDIT : J'ai également lu tout ce qui avait sur le lien, et bien qu'intéressant, j'avais déjà vu la majorité du contenu par ailleurs et je n'ai rien vu qui puisse m'aider :cry:

[QUOTE=cashp]Ca commence à être intéressant en effet, mais deux bémols :
- je ne connais pas la longueur des éventuels chemins multiples
- dans mon application, les graphes sont implémentés en listes d'adjacence
/QUOTE]

1. la longueur? C'est le plus petit p tel que M^p[i,j]=0 ! Donc tu programmes en récursif ou avec un tant que M^p[i,j]<>0...

2. C'est vraiment simple de construire M à partir de listes d'adjacences!! Si a et b sont adjacents, alors M[a,b]=1 et (M[b,a]=1 si tes fleches sont dans les 2 sens)!!!!

A partir de là, je pense que tu as toutes les billes, creuse-toi un peu la tête, cela n'est vraiment pas très dur... ;)

[QUOTE=Nemerle]

Citation:

---

Envoyé par cashp

Ca commence à être intéressant en effet, mais deux bémols :
- je ne connais pas la longueur des éventuels chemins multiples
- dans mon application, les graphes sont implémentés en listes d'adjacence
/QUOTE]

1. la longueur? C'est le plus petit p tel que M^p[i,j]=0 ! Donc tu programmes en récursif ou avec un tant que M^p[i,j]<>0...

2. C'est vraiment simple de construire M à partir de listes d'adjacences!! Si a et b sont adjacents, alors M[a,b]=1 et (M[b,a]=1 si tes fleches sont dans les 2 sens)!!!!

A partir de là, je pense que tu as toutes les billes, creuse-toi un peu la tête, cela n'est vraiment pas très dur... ;)

---

Pour transformer une liste d'adjacence en matrice, non ce n'est pas difficile, mais la matrice occupe beaucoup d'espace en mémoire.
Et de plus la méthode utilisée ensuite pour déterminer si chemin multiple ou non est sacrément gourmande en ressources...
Bref oui ça marcherait mais c'est utiliser un bulldozer pour planter une fleur :lol:

Donc si quelqu'un aurait une piste vers quelque chose de plus "léger", je prends !

Ceci dit je suis actuellement sur une piste, il faut aue je l'implémente pour voir si ça marche et je vous tiendrais au courant ;)

Après avoir implémenté et testé ma piste, ça a l'air de marcher !
J'ai juste un problème sur un pointeur quelconque quand je fais un test (alors que 7 autres tests similaires tournent sans problème), j'essaie de le corriger.

Je vous ferai part de ma solution une fois que tout sera opérationnel ;)

EDIT : finalement j'ai trouvé au moins un cas ou ma solution ne marche pas, donc c'est pas bon :(
Donc je suis toujours ouvert à une solution...

Pour connaître le nombre de chemins entre deux sommets de ton graphes tu calcul le flot maximal entre ces deux sommets en mettant des capacités égale à 1 sur les arcs. Si tu ne connais pas les flots max, regarde par exemple
http://lapoire.developpez.com/algorithmique/graphes/ (Chapitre 10)

NB: Le nombre de chemins ici est le nombre maximal de chemins qui n'ont pas deux arêtes en commun.

Je ne sait pas ça peut-être suffisant, mais le problème de la taille des matrices d'adjacence peut être réduit en utilisant des matrices éparses pour le stockage (typiquement remplies de beaucoup de 0).

Voilà voilou ...

Bon, j'ai une solution qui a l'air de marcher, en tous cas je ne l'ai pas encore prise en défaut :roll:

J'aurais donc un petit coup de pouce à vous demander concernant une autre question. Si on considère un graphe orienté dans lequel il n'y a pas de chemins multiples (mais il peut y avoir des cycles par contre), comment peut-on déterminer le chemin le plus long dans tout le graphe (aucun sommet source ou extrêmité n'est donné, ils sont quelconques) ?

Citation:

---

Envoyé par cashp

J'aurais donc un petit coup de pouce à vous demander concernant une autre question. Si on considère un graphe orienté dans lequel il n'y a pas de chemins multiples (mais il peut y avoir des cycles par contre), comment peut-on déterminer le chemin le plus long dans tout le graphe (aucun sommet source ou extrêmité n'est donné, ils sont quelconques) ?

---

Le problème du plus long chemin dans un graphe orienté est un problème NP-complet. Un cas particulier de ce problème est le problème du chemin hamiltonien.

S'il n'y a qu'un chemin entre deux paires de points, tu peux calculer la longueur de ce chemin pour les n² paires de chemin et retourner le plus long chemin trouvé.

On peut effectivement se passer de la matrice d'adjacence. Tu peux calculer (M^p)[i,j] directement à partir de tes listes.

Donne-moi le format de tes listes, je te donnerai un algo si tu veux ;)

Citation:

---

Envoyé par Nemerle

On peut effectivement se passer de la matrice d'adjacence. Tu peux calculer (M^p)[i,j] directement à partir de tes listes.

Donne-moi le format de tes listes, je te donnerai un algo si tu veux ;)

---

Donc si j'ai S sommets, j'ai un tableau de S éléments. Et dans chaque élément est représenté son nom (un entier), une liste vers ses sommets adjacents (tableau d'entier), le nom de son prédécesseur (lors d'un parcours), le temps de découverte (lors d'un parcours), le temps final (lors d'un parcours, une fois qu'il a parcouru tous ses adjacents).

En tous cas merci beaucoup, car la solution que j'avais trouvé n'était malheureusement toujours pas la bonne...
Par contre pour trouver la longueur du chemin le plus long présent dans le graphe ça a l'air de fonctionner !

Citation:

---

Envoyé par Nemerle

On peut effectivement se passer de la matrice d'adjacence. Tu peux calculer (M^p)[i,j] directement à partir de tes listes.

Donne-moi le format de tes listes, je te donnerai un algo si tu veux ;)

---

Tiens, tu m'as oublié ? ;)

suis à la bourre aujourd'hui, sorry. On verra demain...

Citation:

---

Envoyé par cashp

Donc si j'ai S sommets, j'ai un tableau de S éléments. Et dans chaque élément est représenté son nom (un entier), une liste vers ses sommets adjacents (tableau d'entier)...

---

Donc je pars du principe que pour tout i tu as une liste R(i) de ses voisins "successeurs" (i-->j) et une liste L(i) de ses "prédécesseurs" (j-->i). Si ton graphe n'est pas orienté, L(i)=R(i)=ta liste. Rappel:

(M^p)[i,j] = [somme sur k] (M^(p-1))[i,k] * M[k,j]

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

fonction entier: M(p,i,j){ entier c si p=1 alors si i est dans L(j) alors c=1 sinon c=0 fin si sinon pour tout l de L(j) c=c+M(p-1,i,l) fin pour fin si retourner c } fonction entier: CheminLePlusLong(i,j){ entier p=0 tant que M(p+1,i,j)<>0 p=p+1 fin tant que retourner p }

---

Tu peux accelérer le calcul en stockant tout M(p,i,j) que tu calcules la première fois, afin de le réutiliser directement...

Citation:

---

Envoyé par cashp

Tiens, tu m'as oublié ? ;)

---

et toi??