Flot Maximal Par L'algorithme d'Edmonds-Karp [PDF]

Zitiervorschau

Ecole nationale des sciences appliquées khouribga - Université Hassan 1er

Flot maximal par l'algorithme d'Edmonds-Karp 01 janvier 2012

Mohammed Cheddad

Imad Lamtouni

Yacine abdessalam Amkassou

Encadré par : Mr. Imad hafidi

Table des matières

INTRODUTION : CHAPITRE I : BIBLIOGRAPHIE DE L’ALGORITHME D’EDMONDS-KARP 1

Problème du Flot maximal :

1.1 1.2

Introduction au problème du flot maximale Algorithme d’Edmonds-Karp

1.2.1 Etapes de l’Algorithme 1.2.2 Pseudo code 1.2.3 Etude de complexité 1.2.4 Exemple d’application de l’algorithme d’Edmond-Karp CHAPITRE II : PROGRAMMATION DE L’ALGORITHME D’EDMONDS-KARP 1

Génération aléatoire du graphe : 1.1 1.2 1.3 1.4

2

Chemin Augmentant 2.1 2.2 2.3

3

Méthode de Marquage Fonction de Parcours Exemple de Parcours

L’algorithme d’augmentation de flot 3.1 3.2 3.3

4

Introduction Description du programme Les fonctions utilisées Fonction principal de création de graphe

Démarrage de l’Algorithme La recherche de la capacité minimale La mise à jour des capacités et des flots

Exemple d’exécution

CONCLUSION

INTRODUTION : Dans le cadre du module d’algorithme avancée, nous avons été amené à étudier l’algorithme d’ Edmonds-Karp. Ce même algorithme est devenu le sujet de notre projet dans ce module.

Nous présenterons dans un premier temps, l’algorithme d’ Edmonds-Karp plus en détails. Dans un deuxième temps nous passerons en revue les différentes phases de la réalisation de ce projet et pour terminer nous allons exécuter notre programme. Le but est de créer un programme appliquant un algorithme de flot maximum. L’algorithme devant être appliqué est l’algorithme d’ Edmonds-Karp.

CHAPITRE I : BIBLIOGRAPHIE DE L’ALGORITHME D’EDMONDS-KARP

1 Problème du Flot maximal : La théorie des graphes est née en 1736 quand Léonard Euler démontra de manière rigoureuse qu’il était impossible de traverser chacun des sept ponts de la ville de Konigsberg une fois exactement et de revenir à son point de départ.

Un graphe est un ensemble de points appelés sommets, reliés par des flèches ou des traits. C’est un outil qui sert à modéliser de nombreux problémes,

1.1 Introduction au problème du flot maximale Le problème de flot maximum consiste à trouver un flot réalisable depuis une source unique et vers un puits unique. Quelquefois le problème répond simplement à la question de trouver la valeur de ce flot. Le problème du flot maximum peut être vu comme un cas particulier de plusieurs autres problèmes de flots dans les réseaux. Le flot maximum (depuis la source s vers le puits t) est égal a la coupe minimale du graphe.1 Définition : Un flot est une fonction entière positive ou nulle f définie sur les arcs satisfaisant : Contrainte de capacité : ; Conservation du flot : pour tout sommet autre que s et t, la somme des flots sur les arcs entrants et la somme des flots sur les arcs sortants sont égales.

Figure 1 exemple de réseau du flot

1.2 Algorithme d’Edmonds-Karp Définition : Un réseau de transport

est un graphe orienté

sans circuit : Muni d’une source : un sommet s S tel que , Muni d’un puits : un sommet p S tel que Dont chaque arc u A est valué par une capacité : un nombre positif ou nul noté Et tel qu’il existe au moins un chemin de s vers p.

L'algorithme de Edmonds-Karp construit un flot maximal en partant d'un flot nul et en augmentant son débit le long de chemins de s à t acceptables, c'est à dire tels que et que le débit maximum soit strictement positif.

1

Wikipedia http://fr.wikipedia.org/wiki/Probl%C3%A8me_de_flot_maximum

La particularité de l'algorithme de Edmonds-Karp est de toujours choisir un chemin acceptable don’t la longueur (en nombre d'arêtes) est minimale. Dès qu'un nouveau chemin L acceptable de longueur minimale est trouvé, son débit est ajouté à et, parallélement, les capacités c de G sont mises à jour.2

Figure 2 exemple de réseaux de transport

Cette methode était crée par Jack Edmonds et Richard Karp en 1971 3 elle s’agit d’une modification de l’algorithime de Ford-Fulkerson , cette derniére consiste a calculer de debit maximal dans un réseau de transport . La différance entre les deux c’est que la premiére utilise le plus court chemin dans l’augmentation du flot .

1.2.1 Etapes de l’Algorithme L’algorithme repose sur 2 etape principeaux . Dabord il faut chercher un chemin de s vers p ,cette étape est fait par le parcours par Largeure ce qui garentie que le chemin suivant soit minimal en nombe de arêtes ( sans utiliser aucun methode de plus court chemin) . Arpes qu’on a trouvé ce chemin, l’etape suivante consiste à augmenter ce chemin en quantité de flot qui le traverse . Ceci nécessite de trouver le maximal flot qui peut traverser ce chemin , ce dernier est determine par l’équation suivante :

Donc le chemin C(s,p) est dit augmentant si . Alors on peut dire que l’algorithme d’Edmond-Karp est :    

initialiser le flot f avec la valeur 0 sur chaque arc tant qu’il existe un chemin augmentant s à p, augmenter le flot de e jusqu’à l’obtention d’un flot complet, tant qu’il existe une châıne augmentante de s à p, augmenter le flot de e jusqu’à l’obtention d’un flot maximal, retourner f

1.2.2 Pseudo code

2 3

Thomas H. Cormen, Cliôrd Stein, Ronald L. Rivest, and Charles E. Leiserson. Introduction à l'algorithmique. Dunod, 2nd edition, 2001. Puplier pour la premier fois dans Journal of the Association for Computing Machinery, Vol. 19, No. 2, Apri| 1972. pp. 248-264

[ ] [ ] [ ] [ ]

[ ] [ ]

[ ] [ ] [ ] [ ]

[ ] [ ] [ ]

1.2.3 Etude de complexité Le temps de fonctionnement de O(|S|.|A2|) est trouvé en prouvant que chaque chemin augmentant peut être trouvé dedans O(A) temps, celui chaque fois au moins un de A le bord devient saturé, ce la distance du bord saturé à la source le long du chemin augmentant doit être plus long que la fois passée qu'il a été saturé, et ce la distance est au plus S long. Remarque : la longueur du chemin augmentant le plus court augmente monotoniquement. Il y a une preuve accessible dedans4

1.2.4 Exemple d’application de l’algorithme d’Edmond-Karp Soit le graphe suivant tel que la source est l et le puits est 5 et

:

Le premier chemin augmentant est :

On va calculer e le minimal des

4

Thomas H. Cormen, Cliôrd Stein, Ronald L. Rivest, and Charles E. Leiserson. Introduction à l'algorithmique. Dunod, 2nd edition, 2001.

Donc on augmente tout les flots de e=9 L’arête 1

par

devient saturé

On cherche le chemin augmentant suivant tel que l’arête 1 est éliminé Alors on a:

On va calculer e le minimal des

Donc on augmente tout les flots de par e=5 . L’arête 3 est saturé

Quand il ne reste aucun chemin augmentant on calcule le flot maximal par une coupe minimal . Alors le flot maximal est

CHAPITRE II : PROGRAMMATION DE L’ALGORITHME D’EDMONDS-KARP

La première étape du projet fut la compréhension de l’algorithme. Cette étape est sans doute la plus importante du projet car elle permet de partir dans la bonne direction dès le début pour les étapes suivantes.

1

Génération aléatoire du graphe : 1.1

Introduction

C'est très important de savoir à la fin que le programme réalisé fonctionne correctement et atteint l'objectif, mais pour vérifier ça nous devons le tester pas seulement une fois ou deux mais plusieurs et sur des cas différents, pour éviter que notre programme marche pour certains cas et non pas pour tout. Alors nous devons créer un sous

programme qui génère des graphes juste et de manière aléatoire, pour pouvoir tester le programme principal sur différents cas. Donc on peut dire que le générateur aléatoire des graphes est la matière première de notre projet. Ce qui fait la création de ce générateur doit être avec vigilance et prudence pour ne pas se baser sur quelques choses de faux. On a adopté pour le graphe un structure de données particulières et intelligente qui nous permettra de travailler sur le graphe avec souplesse, cette structure utilise seulement les listes chainés pour leurs efficacité (mais difficile à coder) la structure de donnée adoptée est illustrée dans la figure suivante:

Figure: Structure de graphe

4 typedef struct graph graph ; 5 struct graph 6{ 7 int val ; 8 CHaine adj ; 9 graph * suiv ; 10 }; 11 12 typedef graph * GRaph ; Cette structure est composée de trois attributs ;  Valeur.  un pointeur de type chaine pointant vers la liste chainée contenant les adjacents de ce sommet.  un pointeur de type graph pointant vers le sommet suivant. Voici la structure de base pour la liste chainée : typedef struct chaine chaine; 5 struct chaine 6{ 7 int valeur; 8 int capacity; 9 int flot; 10 chaine *suivant; 11 };

12 typedef chaine* CHaine;

Figure 3 : chaine

Pendant la réalisation de ce sous programme on a rencontré tant de problèmes certains sont résolus (comme les problèmes de programmation) et d'autres non c'est du au complexité du problème.

1.2

Description du programme:

L'utilisateur nous fournit seulement le nombre des sommets et aussi le nombre des arrêts et le programme génère le graphe correspondant. Dans un réseau de transport deux sommets sont particuliers sont: la source et le puit, le puit ne doit pas avoir des successeurs et la source aussi ne doit pas posséder des prédécesseurs. On a utilisé les nombres entiers comme étiquettes des nœuds (1,2,..., S) et nous avons pris que toujours 1 est la source et S le puit car ça nous aidera un peu à simplifier les tâches. EXEMPLE Si S=6, on a: 1 et la source et 6 le puits. L'algorithme de génération des graphes aura recours à des fonctions supplémentaires, donc il est préférable de les détailler avant de passer pour détailler l'algorithme principal.

1.3

Les fonctions utilisées:

void repartirArrets(int S, int A, int t[]) Cette fonction sert à repartir le nombre d'arrêts que chaque nœud doit faire, cette répartition se fait aléatoirement en se servant de la fonction rand. void repartirArret(int S,int A,int t[]) { int som=0,i,a; srand(time(NULL)); for(i=0;icapacity=cap; nouv->suivant=NULL; nouv->flot=flot; if(C==NULL) { return nouv; } else { CHaine aux=C; while((aux->suivant)!=NULL) { aux=aux->suivant; }

aux->suivant=nouv; return C; }}

chaine* createChaine(int taille, int t[],int cap[],int flo) Cette fonction transforme un tableau donné de taille n en liste chainée, cette fonction à comme paramètres un tableau des capacités pour chaque nœud et une variable flo c'est le flot initial (0). chaine* createChaine(int taille, int t[],int cap[],int flo) { Chaine *ch=NULL; ch=ajouterFin(ch,t[0],cap[0],flo); int i=0; Chaine *aux=ch; for(i=1;ivaleur=t[i]; nouv->capacity=cap[i]; nouv->flot=flo; nouv->suivant=NULL; aux->suivant=nouv; aux=nouv; } return ch; }

graph* ajoute(graph *G, chaine *H, int k) Cette fonction ajoute un nouvel élément au graphe et lui affecte la valeur k et le chaines H qui contient les nœuds adjacents. graph *ajoute(graph *G, chaine *C, int n) { graph *nouv= malloc(sizeof(graph)); nouv->val=n; nouv->adj=C; nouv->suiv=NULL; if(G==NULL) { return nouv; } else { graph* aux=G; while(aux->suiv !=NULL) { aux=aux->suiv; } aux->suiv=nouv; return G; }}

1.4

Fonction principal de création de graphe:

graph* creeGraph(int S, int A); input=S,A. output= pointeur de graphe.

Demarche de la fonction:  Dans un premier temps cette fonction repartit fait la répartition des arrêts et stocke les résultats dans un tableau T.  Remplir un tableau par les étiquettes des nœuds (ce tableau ne doit pas contenir l'étiquette de la source cà-d 1 donc le tableau commence de 2 à S)  On boucle un compteur de 0 à S-1 et dans chaque itération Il y a : - création d'un tableau de taille n= T[i], ce tableau contiendra les adjacents après l'appellation de la fonction selectionerParmi. - Création de la liste chainée en transformant le tableau des adjacents en liste chainée H. - insérer dans le graphe un nouvel élément de valeur : i+1 (car le compteur commence par 0), adj=H.  à la fin on ajoute au graphe un nouvel élément (puit) de val=S,H=NULL. graph* creeGraphe(int S,int A) { graph *G=NULL; int T[S]; int i=0; repartirArret(S,A,T); int ta[S-1]; for(i=0;i0 && p[(H->valeur)-1]==-1) 193 { La condition H->capacity>0 détermine si l’arête est saturé ou non , p[(H->valeur)-1]==-1 il faut que v n’est pas encore visiter . 194 p[(H->valeur)-1]=GH->val; On marque v par u (sont prédécesseure). 195 Q=enfiler(Q,H->valeur); 200 if((H->valeur)==S) 201 { 202 return 0; 203 } Si on arrive à p la fonction retourner 0 , Notre chemin est trouvé ! 206 } 207 H=H->suivant; Incrémenter H pour passer à l’adjacents suivant 208 } 209 } 210 return 1; Retourner 1 si on ne peut pas arriver au puits 211 }

2.3

Exemple de Parcours

Soit le graph suivant : S={S,A,B,P} On n’a pour tout les arêtes c(u)>0 (le premier parcours) Et aussi p(u)=-1 (le premier parcours) La fonction recoit G un pointeur sur s s enfilé dans Q et on entre dans la 1er while, Puis s est defilé après avoir stocker dans u alors u=s Les adjacents de s sont enfilés dans Q Q= {A,B} P[A]=S

P[B]=S

U=A depiler Q Q= {A,B} Empilé P

Q= {B} P[P]=A

v=P alors retourne 1

Donc on obtient notre chemin depuis le tableau P[] Exemple de programme de parcours

3

L’algorithme d’augmentation de flot :

La particularité de l’algorithme d’augmentation de flot, est de toujours choisir un chemin acceptable déjà fournie par l’algorithme du parcours de graphe, dont la longueur (en nombre d'arêtes) est minimale, faire un retour en ariére depuis le puits jusqu’à la source et dés que la capacité minimale est trouvée, son débit est ajoutée à et parallèlement, les capacités c du graphe sont mises à jour. Dans cette algorithme on aura besoin de trois fonctions, qu’on a choisit les détaillés séparément.

La fonction GRaph search : GRaph search(GRaph G,int valeur) { GRaph aux=G; while(aux!=NULL) { if(aux->val==valeur) { return aux; } aux=aux->suiv; } return NULL; } La fonction GRaph search aura comme paramètres d’entrée la valeur recherchée int valeur et le pointeur initial de la liste chainée GRaph G. Cette fonction a pour but de chercher une valeur précise dans une liste chainée appelée GRaph composée de tous les sommets du graphe, elle parcoure toute la liste jusqu’à trouver la valeur recherché puis elle retourne son pointeur, sinon elle retourne la valeur NULL.

La fonction searchChaine : CHaine searchChaine(CHaine C, int n) { if(C==NULL) { return NULL; } CHaine aux=C; while(aux != NULL) { if(aux->valeur == n) { return aux; } aux=aux->suivant; } return NULL; }

La fonction searchChaine aura comme paramètres d’entrée la valeur recherchée int valeur et le pointeur de la liste chainée CHaine C. Cette fonction va nous permettre de trouver une valeur précise dans une liste chainée appelée CHaine composée de tous les sommets adjacents d’un sommet déjà déterminé. Elle parcoure toute la liste en commençant du pointeur initial C jusqu’à trouver la valeur recherché et retourne son pointeur, sinon elle retourne la valeur NULL.

La fonction Min : int Min(int m1,int m2) { if (m1val. La fonction searchChaine a pour but de chercher la position de U dans la liste des adjacents de GH . Après chaque itération on compare la valeur de la capacité d’un arc avec m à l’aide de la fonction min, on conserve la valeur la plus minimale et pour finir cette, étape on incrémente à U la valeur GH pour mettre à jour la boucle While().

while(U->val!=1) { GRaph GH=search(g,pre[U->val-1]); CHaine H=searchChaine(GH->adj,U->val); m=Min(m,H->capacity); U=GH; //Incrementation de sommet/graph H }

3.3

La mise à jour des capacités et des flots :

Maintenant qu’on a trouvé la capacité minimale d’un chemin, on doit l’ajouter à la valeur du flot des arcs qui composent ce chemin, et aussi trancher cette valeur de toutes les capacités. Pour faire cette étape on doit avant tout initialiser le nouveau pointeur Uaug sur le puits : GRaph Uaug=search(g,6);

Puis utiliser une boucle while() qui se répète tant qu’on a pas encore trouvé la valeur de la source qui égale à 1. La fonction GRaph search va nous permettre à chaque fois de trouver le prédécesseur GH du sommet Uaug->val. D’autre part, le pointeur H va être utilisé pour pointer sur la valeur Uaug dans la liste des adjacents de GH à l’aide de la fonction CHaine H. Maintenant qu’on a détecté le prédécesseur de Uaug, on va augmenter le flot et diminuer la capacité de l’arc qui relie GH avec Uaug dans un même temps : Cette boucle sera répétée tant de fois jusqu’à retrouver la source.

GRaph Uaug=search(g,6); while(Uaug->val!=1) { GRaph GH=search(g,pre[Uaug->val-1]); // pointer GH sur predecesseure de U CHaine H=searchChaine(GH->adj,Uaug->val); // pointer H sur le list des adjacents de GH H->flot+=m; H->capacity-=m; Uaug=GH; }

4

Exemple d’exécution

Conclusion Le bilan est que nous avons atteint présquement les objectifs fixés en début de projet. Pour conclure, on peut dire que ce projet à été particulièrement intéressant. D’un point de vue pédagogique, le fait de devoir créer un logiciel nous a permis de comprendre encore mieux le fonctionnement de l’algorithme de flot maximum. En ce qui concerne l’aspect programmation, même s’il ne s’agit pas du but principal, il s’avère que ce projet nous a permis de mettre en application un certain nombre de connaissances apprises dans des semestres précédentes y compris la programmation en langage C.