Informatique, Programmation, Python, Enseignement...

Solutions

http://images.math.cnrs.fr/Au-feu-les-pompiers.html

L'algorithme de Ford-Fulkerson que nous nous proposons de programmer résout un problème d'optimisation qui consiste à maximiser le flot traversant un graphe. Nous allons travailler sur des graphes orientés valués, contenant un nœud d'entrée et un nœud de sortie. Les arêtes permettent de progresser de l'entrée vers la sortie. On peut assimiler la valeur de chaque arête au débit maximum du flot entre deux sommets.

Maximiser le flot consiste à rechercher quel sera le flot maximal à travers le graphe.

L'exemple suivant est tiré de Algorithmes en Langage C de Robert Sedgewick

Le graphe d'exemple a 6 nœuds, étiquetés A, B, C, D, E, et F et 8 arêtes (figure a) valuées par le flot maximal.

Le principe est de travailler par raffinements successifs. À partir du graphe de départ, nous construisons un nouveau graphe, dans lequel chaque arête est doublée (pointillés sur la figure a)). L'arête qui est dans le sens de l'arête d'origine (sens de circulation du flot) indique le flot encore disponible sur cette arête. L'arête fictive, en sens inverse, indique le flot utilisé. Ainsi, la somme des valeurs de deux arêtes associées doit toujours valoir exactement la valeur de l'arête de départ. Sur les images illustrant notre exemple, lorsque la valeur d'une arête est à 0, elle a été représentée en pointillés.

Le graphe initial est donc celui de la figure a), dans lequel les arêtes correspondant au flot disponible ont exactement pour valeurs celles des arêtes du graphe de départ. Inversement, les valeurs des arêtes correspondant au flot utilisé sont initialement nulles.

Nous procédons maintenant par raffinements successifs, pour améliorer cette situation de départ. Lorsque cette amélioration ne sera plus possible, nous aurons la solution optimale. Pour améliorer une solution partielle, il faut :

1. rechercher un chemin (orienté), qui va du nœud source au nœud sortie. S'il n'existe pas de tel chemin, l'algorithme est terminé. Un tel chemin est représenté en gras sur la figure b) (en haut).
2. rechercher l'arête de ce chemin qui porte la valeur minimale (c'est le flot qu'on pourra faire passer le long de ce chemin). Dans notre exemple, cette valeur, nommée fmin vaut 6.
3. modifier le graphe pour passer à l'étape suivante, pour cela, on retire la valeur fmin à chaque arête du chemin (et on l'ajoute à chaque arête inverse). On se retrouve ainsi dans la situation de la figure b) (en bas).

Cette solution correspond à une solution partielle, que nous pouvons analyser en regardant les flèches en sens inverse :

• un flot de 6 de A à B (c'est le maximum)
• un flot de 6 de B à D (c'est le maximum)
• un flot de 6 de D à F (il reste 2)

Cette solution peut à nouveau être améliorée en reprenant les trois étapes précédentes (figure c)) puis à nouveau (figure d)). Dans la situation du graphe d) (en bas), il n'existe plus de chemin qui relie A à F. Nous avons le flot optimal. On peut le représenter de manière plus lisible en reprenant les arêtes inverses. Cette solution est présentée sur la figure e) :

• flot de 6 de A vers B
• flot de 6 sur 8 de A vers C
• en B et C, le flot se divise en deux parties de 3
• deux flots de 3 arrivent en D et en E
• un flot de 6 (sur 8) de D à F et un flot de 6 de E à F

Le flot maximal qui peut traverser le graphe est donc 12.

Les seuls choix à faire concernent les choix d'un chemin de A à F, pour améliorer le graphe des flots. Ce choix ne conditionne pas la solution finale obtenue, qui est toujours la solution optimale. Il conditionne en revanche le nombre d'étapes nécessaires avant de parvenir à cette solution optimale.

Dans ce travail, nous ne nous préoccuperons pas de l'optimisation du nombre d'étapes et sélectionnerons donc n'importe quel chemin du nœud source au nœud destination.

Les applications envisageables d'un tel algorithme sont multiples :

• dimensionnement de tuyauterie au plus juste
• repérage des goulets d'étranglement
• optimisation de communications réseau
• trafic routier

Vous allez travailler à partir d'une base déjà existante. Vous disposerez d'une petite bibliothèque de gestion de graphes. Cette bibliothèque permet entre autre choses de lire la description d'un graphe valué orienté dans un fichier, de construire ce graphe (la représentation interne est faite sous forme de listes d'adjacences) puis d'interroger la valeur des différentes arêtes.

En ce qui concerne l'algorithme de Ford-Fulkerson lui même, la programmation est déjà entamée. Vous aurez à terminer et à tester ce que vous ajouterez sur des exemples simples et sur des exemples plus complexes à télécharger.

L'objectif est donc triple :

• programmer l'algorithme de Ford-Fulkerson
• comprendre et réutiliser des outils déjà réalisés
• utiliser le programme réalisé sur des exemples concrets

Les parties déjà rédigées sont données à la fin de ce sujet. Vous devez les enregistrer, et prendre connaissance de leur contenu :

• graphes.h et graphes.c constituent notre bibliothèque de gestion des graphes
• testgraphes.c est un programme d'exemple indiquant comment utiliser cette bibliothèque
• Pour tester, vous devez aussi avoir le fichier sample1.txt qui contient la description d'un graphe

Vérifiez que vous arrivez à faire fonctionner le programme testgraphes.c.

Le travail qui suit consiste en l'écriture du fichier ford.c, initialement vide. Vous allez le compléter peu à peu au fur et à mesure des indications qui suivent.

Bien que la bibliothèque de graphes utilise une représentation par listes d'adjacences, nous allons représenter les graphes intermédiaires à l'aide d'une matrice d'adjacence. Cette matrice devra être crée dynamiquement (malloc), et nous allons aussi écrire un setter et un getter, comme en programmation orientée objet, pour protéger les accès à cette matrice. Voici une partie du code de création et gestion de cette matrice, à intégrer dans ford.c

// ---------------------------------------------------------
/* Manipulations de la matrice des flots 
 
  getmflux renvoie un flot
  setmflux modifie la valeur d'un flot
  modifflux ajoute v à un flot et enlève v au flot inverse
     elle renvoie 1 si la modif a été faite, et 0 si la modif
     n'a pas été faite (la modif n'est pas faite si elle implique 
     qu'une arête soit valuée avec un nombre négatif)
*/
// ----------------------------------------------------------
float getmflux(float * m,int n,int s1,int s2)
{ 
  return *(m+s1*n+s2);
}
void setmflux(float * m,int n,int s1,int s2,int v)
{
    // COMPLÉTER ICI
}
int modifflux(float *m,int n, int s1, int s2,int v)
{
  float vdir, vindir;
  vdir=getmflux(m,n,s1,s2);
  vindir=getmflux(m,n,s2,s1);
  vdir+=v;
  vindir-=v;
  // COMPLÉTER ICI ...
}
// -------------------------------------
/* Affichage de la matrice des flots
   Faire un affichage très propre, facile à lire
 */
// -------------------------------------
void affichemat(float *m, int n)
{
  // COMPLÉTER ICI
}
 
// ---------------------------------------
/* Transforme un graphe en matrice de flot
 */
// ---------------------------------------
float * liste_to_mat(graphe *g)
{
  int i,j;
  float *m;
 
  m=(float*)malloc(g->n*g->n*sizeof(float));
  assert(m); // Utile au débuggage
  // Mise à 0 de la matrice
  for(i=0;i<g->n*g->n;i++) *(m+i)=0;
  for(i=0;i<g->n;i++)
  {
    for(j=0;j<g->n;j++)
    {
      // COMPLÉTER ICI
    }
  }
  return m;
}

Compléter ce code là où c'est indiqué, puis testez-le. Pour le tester, chargez le fichier d'exemple, obtenez la matrice qui représente le graphe et affichez là. Puis vérifiez que c'est correct. Modifiez quelques valeurs dans la matrice avec les deux setter. Affichez à chaque fois et vérifiez que c'est correct.

Voyez de quelle manière a été utilisée la fonction assert(). N'hésitez pas à vous en servir par la suite, elle peut vous aider à aller beaucoup plus vite dans la recherche des bugs.

Une des **grosses** fonctions à écrire est la recherche d'un chemin du nœud de départ vers le nœud d'arrivée. N'importe quel chemin fera l'affaire. Nous allons écrire une fonctions récursive qui fait ce travail. Voici son prototype :

// -------------------------------------------------
/* Recherche d'un chemin (n'importe lequel) dans la
	matrice des flots (m) de (n) sommets.
	On cherche à aller de s1 à s2, sachant qu'on 
	a déjà parcouru les sommets stockés dans liste.
*/
// -------------------------------------------------
cel * chemin(float *m,int n,int s1, int s2, cel * liste)

Initialement, la fonction sera appelée ainsi :

cel * l;
l=chemin(mat,g.n,0,g.n-1,0);

Ce qui correspond à recherche un chemin dans un graphe représenté par mat (nombre de nœuds dans g.n) allant du nœud 0 au dernier nœud. Le zéro final indique que la liste des sommets du chemin est initialement vide.

La construction du chemin utilise une structure de liste que nous définirons ainsi :

// Type de cellule pour la liste stockant les chemins
typedef struct _cel
{
  int sommet;
  float flot;
  struct _cel *suivant;
} cel;

Nous aurons aussi besoin des deux fonctions suivantes :

// ----------------------------------------------
/* Efface (récursivement) une liste
 */
// ----------------------------------------------
void effaceliste(cel * l)
{
  if (l)
  {
     // COMPLÉTER ICI
  }
}
// ----------------------------------------------
/* Ajoute un élément à une liste
 */
// ----------------------------------------------
cel * ajoute(cel * l, int i, float v)
{
   COMPLÉTER ICI
}

Complétez tout d'abord la structure de liste et testez là (vous aurez besoin d'une procédure d'affichage pour ça).

Lorsque vous serez sûrs de votre structure de liste, commencez à réfléchir à la fonction chemin. L'idée générale est :

// -------------------------------------------------
/* Recherche d'un chemin (n'importe lequel) dans la
	matrice des flots (m) de (n) sommets.
	On cherche à aller de s1 à s2, sachant qu'on 
	a déjà parcouru les sommets stockés dans liste.
*/
// -------------------------------------------------
cel * chemin(float *m,int n,int s1, int s2, cel * liste)
{
  // Fonction à COMPLÉTER entièrement :
 
  // Si s1==s2, on est arrivé, la liste est complète
  // sinon, il faut partir de s1, et pour chaque voisin i (atteignable) de s1, voir s'il existe
  // un chemin i->s2
  // Ce dernier point est réglé par un appel récursif.
  // S'il y a un chemin i->s2, on récupère la liste contenant ce chemin, 
  // et on y ajoute le sommet i. On peut alors sortir
  // S'il n'y a pas de chemin i->s2, il faut tester un autre voisin i
 
 
  // Attention, à "annuler" les arêtes s1->i avant de recherche le chemin i->s2 pour éviter les boucles infinies :
  //setmflux(m,n,s1,i,0.0);
  // de même, il faut rétablir cette arête si le passage par i n'a pas abouti.
}

Écrivez la fonction chemin et testez là.

La fonction qui réalise ce travail s'appelle flot_suivant. Voici son prototype :

// -------------------------------------------------
/* On donne la liste des noeux par lesquels passer (liste), 
	le noeud de départ (s) , le nombre de noeuds (n)
	et la matrice des flots (m).
	Provoque la modification de la matrice des flots
	Renvoie la modification du flot (i.e. la valeur minimum du
        flot sur le chemin sélectionné)
*/
// -------------------------------------------------
float flot_suivant(float *m,int n, int s, cel * liste)
{
  // COMPLÉTER ICI
}

Cette fonction va remplir sa tâche en deux temps.

1. Parcourir la liste et retrouver quelle est la valeur minimum du flot.
2. À nouveau parcourir la liste et modifier chaque arête du graphe (avec la fonction setter modifflux) de la valeur minimum trouvée précédemment.

Écrivez cette fonction et testez là. Pour cela, recherchez un chemin, modifiez la matrice des arêtes, vérifiez que tout est correct et recommencez (recherche de chemin, modification des arêtes).

Nous pouvons maintenant écrire le programme principal et tester sur un premier exemple

// -------------------------------------------------
/* Programme principal */
// -------------------------------------------------
int main(void)
{
  cel * l; // liste pour les chemins
  float flot;
  FILE *f;
  graphe g; // graphe
  float * mat; // matrice d'adjacence
 
  // Lecture du graphe dans un fichier 
  init(&g);
  f=fopen("sample1.txt","r");
  lecture(f,&g);
  fclose(f);
  affiche(g);
 
  // Construction de la matrice des flots
  // COMPLÉTER ICI 
 
  // Recherche un premier chemin :
  l=chemin(mat,g.n,0,g.n-1,0);
  while(l)   // Tant qu'un tel chemin existe
  {
    // Passer au flot suivant avec la fonction flot_suivant	  	
    // COMPLÉTER ICI
    // Effacer la liste l, maintenant inutile
    // COMPLÉTER ICI
    // Recherche un nouveau chemin
    l=chemin(mat,g.n,0,g.n-1,0);
  }
 
  // Affichage propre du flot maximum
  // On reprend chaque arête du graphe d'origine, et 
  // on indique son % d'occupation 
 
  // COMPLÉTER ICI
  return 0;
}

Complétez le programme principal et vérifiez sur l'exemple qu'il trouve les bonnes valeurs.

Voici quelques fichiers représentant d'autres graphes. Enregistrez-les et répondez aux questions suivantes.

FlotMax
NbAretesAuMax
0 4 3.2
0 5 1.1
...
95 101 3.0

Les deux fichiers suivants permettent de faire quelques manipulations sur les graphes.

graphes.h

#ifndef GRAPHES_H
#define GRAPHES_H
 
typedef struct _arc {
  int sommet;
  float valeur;
  struct _arc * suivant;
} arc;
 
typedef arc* listearc;
 
typedef struct {
  int n;
  listearc * s;
  int deb;
  int fin;
} graphe;
 
int existe_arc(graphe *g, int s1, int s2);
float valeur_arc(graphe *g, int s1, int s2);
void vider(graphe * g);
listearc  ajoute_arc(listearc l,int s, float v);
void lecture(FILE * f, graphe *g);
void affiche(graphe g);
void init(graphe * g);
#endif

graphes.c

Voici un fichier de test qui illustre l'utilisation des outils qui précèdent. Vous pouvez l'utiliser avec le graphe donné dans le fichier d'exemple qui suit aussi.

testgraphes.c

#include<stdio.h>
#include "graphes.h"
int main(void)
{
  FILE *f;
  graphe g;
  init(&g);
  affiche(g);
  f=fopen("sample1.txt","r");
  lecture(f,&g);
  fclose(f);
  affiche(g);
  printf("Existe 2,3 ? : %d\n",existe_arc(&g,2,3));
  printf("Valeur 1,3 ? : %f\n",valeur_arc(&g,1,3));
  return 0;
}

sample1.txt

6
0 1 6
0 2 8
1 3 6
1 4 3
2 3 3
2 4 3
3 5 8
4 5 6