code source graphe programation java ford_fulkerson



/**
 *  classe gérant les graphes

import java.util.LinkedList;
import java.util.Scanner;

public class Graphe{
    private int nbrSom;   // nombre sommet
    private int nbrArc;    // nombre des arêtes  
    private LinkedList sommetList ; // liste des sommets
    private LinkedList arcList ; // liste des aretes
    private String type;      // le type de graphe valué ou non   "Value"  or "NoValue"
    private static int matAdja [][];   // la matrice d'adjacence
   
    public Graphe(){
        sommetList = new LinkedList();
        arcList = new LinkedList();       
    }
   
    public Graphe(LinkedList sommetList, LinkedList arcList){
        this.sommetList = sommetList;
        this.arcList = arcList;
        nbrSom = (int) sommetList.size();
        nbrArc = (int)arcList.size();
        matAdja = new int[nbrSom][nbrSom];
    }
   
    public int getNbrSom(){
        return nbrSom;
    }
   
    public void setNbrSom(int nbrSom){
        this.nbrSom = nbrSom;
    }
   
    public String getType(){
        return type;
    }
   
    public int getNbrArc(){
        return nbrArc;
    }
   
    public void setNbrArc(int nbrArc){
        this.nbrArc = nbrArc;
    }
   
    public LinkedList getSommetList(){
        return sommetList;
    }
   
    public LinkedList getArcList(){
        return arcList;
    }
   
    public void setSommetList(LinkedList sommetList){
        this.sommetList = sommetList;
    }

    public void setArcList(LinkedList sommetArc){
        this.arcList = arcList;
    }
       
    public int [][] getMatriceAdjacente(){
        return matAdja;
    }
   
    public void constrGraphe(String type){
        this.type = type;
        int S1,S2;
        int cost;
        float infini = 0.0f;
        if(type.equals("Value")){
            infini = (float)Math.pow(10,10);
        }
        for(int i=0; i            for(int j=0; j                matAdja[i][j] = 0;
            }
        }
        Scanner scan = new Scanner( System.in );
        System.out.print("\n Entrer  le nombre des sommer NS=");
        nbrSom = scan.nextInt();
        for(int i=0;i            sommetList.add(new Sommet(i));
        }
        System.out.print("\n Entrer  le nombre des arcs NA=");
        nbrArc = scan.nextInt();
       
        matAdja = new int[nbrSom][nbrSom];
       
        if(type.equals("Value")){           
             System.out.print("\n Entrer  les deux sommet et les  Capacités de chaque arc \n " +
                     "attention les sommet commence a 0  jusqu'a nombre des sommet -1");
            for(int i=0; i               
                System.out.print("\n L'Arc: "+i);
            do{
                System.out.print("\n Entrer premiere Sommet =");           
                S1 = scan.nextInt();
                if((S1>=nbrSom)&&(S1<0 br="">                    System.out.print("Error il faut enter un sommet de 0 a ="+(nbrSom-1));
                }   
            while((S1>=nbrSom)&&(S1<0 br="">                System.out.print("\n Entrer deuxieme Sommet =");           
                S2 = scan.nextInt();
           
               
                System.out.print("\n Entrer la Capacité C=");           
                cost = scan.nextInt();
                Arc ar = new Arc((Sommet)sommetList.get(S1),(Sommet)sommetList.get(S2),cost);
                arcList.add(ar);
                matAdja[S1][S2] = cost;               
                } 
        }       
        else{
            System.out.print("\n Entrer  les deux sommets");
            for(int i=0; i                System.out.print("\n L'Arc: "+i);
                System.out.print("\n Entrer premiere Sommet =");           
                S1 = scan.nextInt();
                System.out.print("\n Entrer deuxieme Sommet =");           
                S2 = scan.nextInt();
                Arc ar = new Arc((Sommet)sommetList.get(S1),(Sommet)sommetList.get(S2));
                arcList.add(ar);               
                matAdja[S1][S2] = 0;               
            }
        }

    }

    public int[][] getmatAdja() {
       
        return matAdja;
    }
     public static void afficheMatrice(int matAdja [][]){
            System.out.println(" **** Notre matrice ****");
            for(int i=0; i               for(int j=0; j                   System.out.print(matAdja[i][j]+"\t\t");
               }
               System.out.println("\n\n");
           }
        }

    public static void main(String args[]){
        //System.out.print("\n Entre le type de graghe a construire :  'Value' ou 'NoValue' ");
        //Scanner scan = new Scanner(System.in);
        String typeGr = "Value";   //scan.next();
        Graphe gr = new Graphe();
        gr.constrGraphe(typeGr);
       
        afficheMatrice(matAdja);
         
       
       
    }
   
 /*  public void AfficheGraphe(){
        Sommet Som1;
        Sommet Som2;  
        Arc ar;
        int n1 ,n2;
        double cout;
        System.out.print("\n ************** Notre graphe ********************\n");
        System.out.println("Le nombre d'arc : "+arcList.size());
        for(int i=0; i            ar = (Arc)(arcList.get(i));
            Som1 = (Sommet)(ar.getBeginning());
            Som2 = (Sommet)ar.getEnd();
            System.out.print("\n ("+ Som1.getName()+","+Som2.getName()+")"+" val="+ar.getCost());
        }
        System.out.print("\n");
    }
   
    public static float [][]matriceAdjacente(Graphe gr){
        int nbrSom = gr.getNbrSom();
           float  matAdjaStati [][] = new float[nbrSom][nbrSom];
        String typeGr = gr.getType();
        float infini = 0;
        if(typeGr.equals("Value")){
            infini = (float)Math.pow(10,10);
        }
        for(int i=0; i            for(int j=0; j                matAdjaStati[i][j] = 0;
            }
        }
        LinkedList arcList = gr.getArcList();
        Arc ar;
        Sommet SB, SE;
        for(int i=0; i            ar = (Arc)arcList.get(i);
            SB = (Sommet)ar.getBeginning();
            SE = (Sommet)ar.getEnd();
            matAdjaStati[SB.getNumber()][SE.getNumber()] = ar.getCost();
        }

       
        return matAdjaStati;
    }
   
    public static void afficheMatricAdja(float matAdja [][]){
        System.out.println(" **** Notre matrice ****");
        for(int i=0; i           for(int j=0; j               System.out.print(matAdja[i][j]+"\t\t");
           }
           System.out.println("\n\n");
       }
    }
    private void messages(){
        System.out.println("Ces sommets n’appartiennent pas au graphe");        
    }
   
    private void message(){
        System.out.println("Ce sommet n’appartient pas au graphe");       
    }
   
    public boolean isAmpety (){
        return arcList.isEmpty();
    }
   
    public boolean isArc (int numS1 , int numS2){
        boolean is  = false;
        if (numS1 < 0 || numS1 > nbrSom || numS2 < 0 || numS2 > nbrSom){
            messages();
            is = false;
        }       
        if(matAdja[numS1][numS2] != 0.0f){
            is = true;
        }       
   
        return is;
    }
   
    public int degrePlus(int num){       
        int cmpP = 0;
        if (num < 0 || num > nbrSom){
            message();
            return -1;
        }
        for(int i=0; i            if (matAdja[num][i] != 0){
                cmpP++;
            }
        }
        return cmpP;       
    }
   
    public int degreMoins(int num){
        int cmpM = 0;
        if (num < 0 || num > nbrSom){
            message();
            return -1;
        }
        for(int i=0; i            if (matAdja[i][num] != 0){
                cmpM++;
            }
        }
        return cmpM;       
    }
   
    public void addArc(int numS1, int numS2, float cost){       
        if ((numS1 < 0) || (numS2 < 0)){
            messages();
        }       
        if ( isArc(numS1,numS2) == true){
            System.out.println("Cet arc existe ");
            return;
        }
        Arc ar = new Arc((Sommet)sommetList.get(numS1),(Sommet)sommetList.get(numS2),(int) cost);
        arcList.addLast(ar);   
        nbrArc++;           
        matAdja[numS1][numS2] = (int) cost;   
    }
   
    public void deleteArc(int numS1, int numS2){       
        if ((numS1 < 0) || (numS2 < 0)){
            messages();
        }       
        if ( isArc(numS1,numS2) == false){
            System.out.println("Cet arc n'existe pas");
            return;
        }
        for(int i=0; i            Arc ar = (Arc)arcList.get(i);
            if(((Sommet)ar.getBeginning()).equals(sommetList.get(numS1)) && ((Sommet)ar.getEnd()).equals(sommetList.get(numS2))){
                arcList.remove(i);
                nbrArc--;           
            }
        }
        //Arc ar = new Arc((Sommet)sommetList.get(numS1),(Sommet)sommetList.get(numS2));
        //boolean yes = arcList.remove(ar);   
        //nbrArc--;           
        matAdja[numS1][numS2] = 0;   
    }
   
    public int iemeSuccesseur(int num , int iemS){
        int cmpI = 0;       
        if (num < 0 || num > nbrSom){
            message();
            return -1;
        }
        for(int i=0; i            if ((matAdja[num][i] != 0.0f) && (cmpI == iemS)){
                return i;
            }
            if (matAdja[num][i] != 0.0f){
                cmpI++;
            }
        }
        return -1;   
    }
   
    public int iemePredecesseur(int num , int iemP){
        int cmpI = 0;       
        if (num < 0 || num > nbrSom){
            message();
            return -1;
        }
        for(int i=0; i            if ((matAdja[i][num] != 0) && (cmpI == iemP)){
                return i;
            }
            if (matAdja[i][num] != 0){
                cmpI++;
            }
        }
        return -1;   
    }

    public int premierSuccesseur(int num){
        if ((num < 0) || (num > nbrSom)){
            message();
            return -1;
        }
        for(int i=0; i            if ((matAdja[num][i] != 0)){
                return i;
            }
        }
        return -1;   
    }
   
    public int premierPuccesseur(int num){
        return (iemePredecesseur(num,0));
    }
   
    public int successeurSuivant(int numS1, int numS2){       
        if (numS1 < 0 || numS1 > nbrSom || numS2 < 0 || numS2 > nbrSom){
            messages();
        }
        for(int i=numS2+1; i            if(matAdja[numS1][i] != 0.0f){
                return i;
            }       
        }
        return -1;       
    }   
      
    /*public static void main(String args[]){
        int numS1, numS2;
        System.out.print("\n Entre le type de graghe a construire :  'Value' ou 'NoValue' ");
        Scanner scan = new Scanner(System.in);
        String typeGr = scan.next();
        Graphe gr = new Graphe();
        gr.constrGraphe(typeGr);
        float matAdja[][] = Graphe.matriceAdjacente(gr);
        Graphe.afficheMatricAdja(matAdja);
        System.out.println("Vous voulez chercher un arc : oui ou non");
        String yes = scan.next();
        while(yes.equals("oui")){
            System.out.println("Entrer l'arc a chercher : ");
            System.out.print("Numero du premier sommet  : ");
            numS1 = scan.nextInt();
            System.out.print("Numero du deuxieme sommet  : ");
            numS2 = scan.nextInt();
            System.out.println("Exixte : "+gr.isArc(numS1, numS2));
            System.out.println("Vous voulez continuez a chercher un arc : oui ou non");
            yes = scan.next();           
        }
        System.out.println("Vous voulez ajouter un arc: oui ou non");
        yes = scan.next();
        while(yes.equals("oui")){
            //System.out.println(" ajouter arc : ");
            System.out.print("Numero du premier sommet: ");
            numS1 = scan.nextInt();
            System.out.print("Numero du deuxieme sommet: ");
            numS2 = scan.nextInt();
            gr.addArc(numS1,numS2,1.0f);
            Graphe.afficheMatricAdja(gr.getMatriceAdjacente());
            gr.AfficheGraphe();
            System.out.println("Vous voulez continuez a ajouter un arc: oui ou non");
            yes = scan.next();
        }           
        System.out.println("Vous voulez supprimer un arc: oui ou non");
        yes = scan.next();
        while(yes.equals("oui")){
            //System.out.println(" ajouter arc : ");
            System.out.print("Numero du premier sommet: ");
            numS1 = scan.nextInt();
            System.out.print("Numero du deuxieme sommet: ");
            numS2 = scan.nextInt();
            gr.deleteArc(numS1,numS2);
            Graphe.afficheMatricAdja(gr.getMatriceAdjacente());
            gr.AfficheGraphe();
            System.out.println("Vous voulez continuez a supprimer un arc: oui ou non");
            yes = scan.next();
        }           
        System.out.println("Vous voulez chercher le degre plus d'un sommet: oui ou non");
        yes = scan.next();
        while(yes.equals("oui")){
            //System.out.println(" ajouter arc : ");
            System.out.print("Numero du sommet: ");
            numS1 = scan.nextInt();
            System.out.println("Le degre plus de ce sommet est : "+gr.degrePlus(numS1));
            System.out.println("Vous voulez continuez a chercher le degre plus: oui ou non");
            yes = scan.next();
        }           
        System.out.println("Vous voulez chercher le degre moins d'un sommet: oui ou non");
        yes = scan.next();
        while(yes.equals("oui")){
            //System.out.println(" ajouter arc : ");
            System.out.print("Numero du sommet: ");
            numS1 = scan.nextInt();
            System.out.println("Le degre moins de ce sommet est : "+gr.degreMoins(numS1));
            System.out.println("Vous voulez continuez a chercher le degre moins: oui ou non");
            yes = scan.next();
        }           
        System.out.println("Vous voulez chercher le ime successeur d'un sommet: oui ou non");
        yes = scan.next();
        while(yes.equals("oui")){
            //System.out.println(" ajouter arc : ");
            System.out.print("Numero du sommet: ");
            numS1 = scan.nextInt();
            System.out.print("Le iem successeur : ");
            int iem = scan.nextInt();
            System.out.println("Le ime successeur de ce sommet est : "+gr.iemeSuccesseur(numS1, iem));
            System.out.println("Vous voulez continuez a cherhcer le ime successeur d'un sommet: oui ou non");
            yes = scan.next();
        }           
        System.out.println("Vous voulez chercher le ime predesseur d'un sommet: oui ou non");
        yes = scan.next();
        while(yes.equals("oui")){
            //System.out.println(" ajouter arc : ");
            System.out.print("Numero du sommet: ");
            numS1 = scan.nextInt();
            System.out.print("Le iem predesseur : ");
            int iem = scan.nextInt();
            System.out.println("Le   ime predesseur de ce sommet est : "+gr.iemePredecesseur(numS1, iem));
            System.out.println("Vous voulez continuez a cherhcer le ime predesseur d'un sommet: oui ou non");
            yes = scan.next();
        }           
        System.out.println("Vous voulez chercher le successeur suivant: oui ou non");
        yes = scan.next();
        while(yes.equals("oui")){
            //System.out.println(" ajouter arc : ");
            System.out.print("Numero du sommet: ");
            numS1 = scan.nextInt();
            System.out.print("Numero du sommet: ");
            numS2 = scan.nextInt();
            System.out.println("Le successeur suivant est : "+gr.successeurSuivant(numS1, numS2));
            System.out.println("Vous voulez continuez a cherhcer le successeur suivant: oui ou non");
            yes = scan.next();
        }           
  }*/
  }