Application graphes orientés

**cashp** · 29/03/2007, 02h31

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

Merci beaucoup !

**mchk0123** · 29/03/2007, 07h56

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

**cashp** · 29/03/2007, 09h30

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 !).

**mchk0123** · 29/03/2007, 09h51

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).

**cashp** · 29/03/2007, 10h30

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.

**Nemerle** · 29/03/2007, 10h54

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

**cashp** · 29/03/2007, 11h24

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...

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

**Nemerle** · 29/03/2007, 13h40

[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...

**cashp** · 29/03/2007, 15h04

[QUOTE=Nemerle]

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

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

**cashp** · 29/03/2007, 18h43

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...

**FrancisSourd** · 29/03/2007, 19h37

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.

**mchk0123** · 29/03/2007, 20h30

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 ...

**cashp** · 29/03/2007, 23h26

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

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) ?

**FrancisSourd** · 30/03/2007, 09h41

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é.

**Nemerle** · 30/03/2007, 17h27

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

**cashp** · 30/03/2007, 18h31

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 !

**cashp** · 01/04/2007, 23h49

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é ?

**Nemerle** · 02/04/2007, 11h16

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

**Nemerle** · 02/04/2007, 14h11

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 :

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
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...