Recherche du flux maximal Ford-Fulkerson programation Java + Algorithme







Recherche du flux maximal dans un réseau de transport par la méthode de  Ford-Fulkerson ( programmation java + code source )



but:
Le but est de créer un logiciel appliquant un algorithme de flot maximum.
L’algorithme devant être appliquée est l’algorithme de Ford-Fulkerson.
On comprendra donc facilement que le langage qui a été choisi pour
coder est le Java. Les performances du logiciel ne sont pas le but premier
du projet, mais plutôt son ergonomie et son aspect pédagogique.


Méthode de détermination d’un flot maximal 
par la  procédure de marquage
 
 
(I)     Marquer l'entrée s par *.
(II)   Soit i un sommet marqué non examiné.
              Considérer tous les successeurs j de i :

(III)   Si p est marqué, aller en (IV)
     S'il reste des sommets marqués non  examinés,  aller en (II).         
     Sinon le flot est optimal, FIN.
(IV)    Améliorer le flot à l'aide de la chaîne améliorante ayant permis   
           de marquer p                                                                                                                                          
     Effacer les marques, sauf celle de s, et aller  en (I).


Corollaires et théorèmes :

Théorème de Ford – Fulkerson : La capacité minimale d'une coupe         
                                                        est égale au flot maximal.

Corollaire 1 : Une C.N.S pour qu'un flot soit maximal est qu'il
                       n'existe pas de chaîne améliorante.
     
Corollaire 2 : L'algorithme de Ford-Fulkerson construit un flot  maximal.


Algorithme de Ford-Fulkerson(1956)


Entrées: G = (X,U) un graphe.
Sorties: Flot maximal.
Début
      Initialisation par un flot initial réalisable (φ = 0)
      Tant que le flot n'est pas maximal
           Marquage de la source S
            Tant qu'on marque des sommets
                   Pour tout sommet marqué i
                     Marquer les sommets j non marqués tq
                     φ (i ; j) < c(i ; j) ou φ(j ; i ) > 0
                  Fin pour
            Fin Tant que
            Si la sortie E n'est pas marquée alors le flot est
                                               Maximal
           Sinon amélioration du flot
      Fin Tant que
 Fin




Remarque :
Avant d’exécuter la class ford_fulkerson on fera appel aux trois class (Sommet, Arc, Graphe)


CODE JAVA :
class ford_fulkerson{
     static //Les capacités des arcs
                    Graphe gr;
                    
      int Capacité[][];
     
     //le Flux initial
       int Flux[][];
                   //matrice pour nous aider (noeud visite)
        int aide[][];
     //la Chaine ameliorante
        int chaine[];
       static int j = 0;
       static boolean existence_de_la_chaine = true;
                  
       public static void Ford_Fulkerson(int[][]C, int[][] F, int[] ch, int[][] aide){
             
         System.out.println("Capacité: ");
         affichrer_matrice(C);
                             System.out.println("Flux : ");
                             affichrer_matrice(F);
                             System.out.println();     
                             while(existence_de_la_chaine == true){  //une chaine ameliorante existe
        
            chaine(C,ch,aide);  //rechercher une chaine a ameliore
            if (existence_de_la_chaine == true)
            System.out.println("il existe une chaine a améliorer  ");
            else
                   System.out.println("il n'existe pas une chaine a améliorer  ");
            if (existence_de_la_chaine == true)
            { System.out.println("la chaine a améliorer est : ");
                                      affichage(ch);}
                                      System.out.println();
            if (existence_de_la_chaine == false){int ff=0;
                   for(int k = 0; k < ch.length; k++){
                    ff =ff+F[k][ch.length-1];         
                 }
                   System.out.println("le Flot maximum est  = "+ff);
            }
            else{
                   augmentation_du_flux(C,F,ch);   //augmentation du flux
               for(int k = 0; k < ch.length; k++){
                  ch[k] = 0;         
               }
               for(int x = 0; x < aide.length; x++){
                  for(int y = 0; y < aide.length;y++){
                     aide[x][y]=0; 
                  }
               }
             
               System.out.println("Flux aprés l'amélioration :");
               affichrer_matrice(F);
            }
         }
      }
  
              //augmentation du flux
       public static void augmentation_du_flux(int[][] C, int[][] F, int[] ch){
         int min = minimum(C,ch);   //trouver le flux minimum a ajouter
         System.out.println("le minimum a ajouter  dans la chaine est: "+min);
         int c = 0;
         while(ch[c] != (ch.length-1)){
            int d = c+1;
            C[ch[c]][ch[d]] -= min;  
            C[ch[d]][ch[c]] += min;
            F[ch[c]][ch[d]] += min;   //modification du flux
            F[ch[d]][ch[c]] = -F[ch[c]][ch[c+1]];
            c++;
         }
      }
  
       // Méthode pour trouver le flux minimal
       // en tenant compte de la chaine a ameliore
       public static int minimum(int[][]C, int[] ch){
         int c=0;
         int hhh = 0;
         int min = 1000000;
         while(ch[c] != (ch.length-1)){
            hhh = C[ch[c]][ch[c+1]];
            if (hhh < min){
               min = hhh;
            }
            c++;
         }
         return min;
      }
     
       // Méthode pour trouver une chaine ameliorente
      
       public static void chaine(int[][] C, int[] ch, int[][] aide){
         int c = 0; 
         int j = 1;
         existence_de_la_chaine = false;
         int compteur = 0;
         while(valider(C[c],ch,aide,c) != -1 && compteur == 0 ){//Bien qu'il y ait un noeud
            ch[j] = valider(C[c],ch,aide,c);               //valider
            if (ch[j] == (ch.length-1)){ // si on arrive a la sortie
                   compteur = 1;
               existence_de_la_chaine = true;
            }
            else{
               c = ch[j];
            }       
            j++;
         }
         if(possible(C[0],aide) == -1 || existence_de_la_chaine == true){
                              //si existe un arc passant par un noeud déja compter dans la chaine
         }
         else if(!rechercher((ch.length-1),ch)){  //s'il existe une chaine
            j--;
            aide[ch[j-1]][ch[j]] = 1;
            for(int k = 0; k < ch.length; k++){
               ch[k] = 0;
            }
            chaine(C,ch,aide);
         }
      }
  
       // Méthode pour déterminer si un nœud est valide en fonction
       // en se basant sur la matrice 
       // de nœuds déjà visités ( aide)
       public static int valider(int[] r, int[] cam,int[][] aide,int i){//Arc, chaine, matrice
         int c = 0;                                                      
         while(rechercher(c,cam) || aide[i][c] == 1){
            c = suivant(r,c);
            if (c == -1){
               return -1;
            }
         }
         return c;
      }
      
       // Méthode pour déterminer si un nœud est deja visité
       public static int possible(int[] r, int[][] aide){
         int c = 0;
         while(r[c] == 0 || aide[0][c] == 1){
            c = suivant(r,c);
            if(c == -1){
               return -1;
            }
         }
         return c;
      }
         
       // Méthode pour obtenir le nœud suivant (ne pas visite par la chaine)
       public static int suivant(int[] r, int j){
         j++;
         while(j < r.length){
            if(r[j] != 0){
               return j;
            }
            else{
               j++;
            }
         }
         return -1;
      }
         
       // Méthode pour trouver un nœud dans la chaine
       public static boolean rechercher(int j, int[] ch){
         for(int k = 0;k < ch.length;k++){
            if(ch[k] == j)
               return true;
         }
         return false;
      }
                  
       // Méthode pour afficher la matrice
       public static void affichrer_matrice(int [][]a){
         for(int i = 0;i
            for(int j = 0;j
               System.out.print("\t"+a[i][j]+"\t");
            }
            System.out.println();
         }
         System.out.println();
      }
  
            //methode pour afficher une chaine
       public static void affichage(int []a){
        
         for(int j = 0; j
           
            System.out.print(+a[j]);
            if(a[j]==a.length-1)
                   break;
            System.out.print(" ---------->");
         }
         System.out.println();
      }
  
       public static void main(String []args){
             String typeGr = "Value";   //scan.next();
           Graphe gr = new Graphe();
           gr.constrGraphe(typeGr);
           int Capacité[][] =gr.getmatAdja();
           int Flux[][]= new int[gr.getNbrSom()][gr.getNbrSom()];
           int aide[][]=new int[gr.getNbrSom()][gr.getNbrSom()];
           int chaine[] = new int[gr.getNbrSom()];
          
                   //l'application de l'algorithme */
         Ford_Fulkerson(Capacité,Flux,chaine,aide);
                            
      }
           }
On retrouve après la matrice



Exemple

Apres avoir entrer les valeurs des capacités des arcs on retrouve :
Capacité:
      0           30          0           0           0           0           0    
      0           0           10          15          0           0           0    
      0           0           0           0           16          0           0    
      0           0           4           0           0           10          0    
      0           0           0           0           0           10          8    
      0           0           0           0           6           0           20   
      0           0           0           0           0           0           0    

Flux :
      0           0           0           0           0           0           0    
      0           0           0           0           0           0           0    
      0           0           0           0           0           0           0    
      0           0           0           0           0           0           0    
      0           0           0           0           0           0           0    
      0           0           0           0           0           0           0    
      0           0           0           0           0           0           0    


il existe une chaine a améliorer 
la chaine a améliorer est :
0 ---------->1 ---------->2 ---------->4 ---------->5 ---------->6

le minimum a ajouter  dans la chaine est: 10
Flux aprés l'amélioration :
      0           10          0           0           0           0           0    
      -10         0           10          0           0           0           0    
      0           -10         0           0           10          0           0    
      0           0           0           0           0           0           0    
      0           0           -10         0           0           10          0    
      0           0           0           0           -10         0           10   
      0           0           0           0           0           -10         0    

il existe une chaine a améliorer 
la chaine a améliorer est :
0 ---------->1 ---------->3 ---------->2 ---------->4 ---------->6

le minimum a ajouter  dans la chaine est: 4
Flux aprés l'amélioration :
      0           14          0           0           0           0           0    
      -14         0           10          4           0           0           0    
      0           -10         0           -4          14          0           0    
      0           -4          4           0           0           0           0    
      0           0           -14         0           0           10          4    
      0           0           0           0           -10         0           10   
      0           0           0           0           -4          -10         0    

il existe une chaine a améliorer 
la chaine a améliorer est :
0 ---------->1 ---------->3 ---------->5 ---------->4 ---------->6

le minimum a ajouter  dans la chaine est: 4
Flux aprés l'amélioration :
      0           18          0           0           0           0           0    
      -18         0           10          8           0           0           0    
      0           -10         0           -4          14          0           0    
      0           -8          4           0           0           4           0    
      0           0           -14         0           0           6           8    
      0           0           0           -4          -6          0           10   
      0           0           0           0           -8          -10         0    

il existe une chaine a améliorer 
la chaine a améliorer est :
0 ---------->1 ---------->3 ---------->5 ---------->6

le minimum a ajouter  dans la chaine est: 6
Flux aprés l'amélioration :
      0           24          0           0           0           0           0    
      -24         0           10          14          0           0           0    
      0           -10         0           -4          14          0           0    
      0           -14         4           0           0           10          0    
      0           0           -14         0           0           6           8    
      0           0           0           -10         -6          0           16   
      0           0           0           0           -8          -16         0    

il n'existe pas une chaine a améliorer 

le Flot maximum est  = 24




 Conclusion :
      Le bilan est que nous avons atteint les objectifs fixés en début de projet.
     Pour conclure, on peut dire que ce projet a été particulièrement intéressant.
     D’un point de vue pédagogique, le fait de devoir créer un logiciel pédagogique nous a permis de comprendre encore mieux le fonctionnement de l’algorithme de  flot maximum.