www

Graphe.cpp (7082B)

---

 #include "Graphe.H"
 #include "GRapheEcart.h"
 
 /* Constructeur par défaut.
 */
 Graphe::Graphe(string nom)
 {
     this->nom = nom;
 }
 
 /* Constructeur par copie d'un graphe.
 */
 Graphe::Graphe(string nom, const Graphe *g)
 {
     this->s = g->s;
     this->p = g->p;
     listeArcs_t lArcs;
     this->nom = nom;
 
     arcs_t arcsTmp = g->arcs;
 
     for(unsigned int i = 0; i < arcsTmp.size(); i++)
     {
         lArcs.clear();
 
         for(unsigned int j = 0; j < arcsTmp[i].size(); j++)
             lArcs.push_back(new Arc(arcsTmp[i][j]));
 
         this->arcs.push_back(lArcs);
     }
 }
 
 Graphe::~Graphe()
 {
 
 }
 
 arcs_t Graphe::getArcs() const { return this->arcs; };
 
 
  //------- Fonctions du TP --------//
 //================================//
 
 /* Q1 | Retourne le graphe d'écart associé pour un flot nul.
 * Prerequis : le graphe doit être orienté et ne pas contenir d'ars retour. TODO revoir l'histoire de pas d'arcs retour.
 * Seconde partie de la fonction dans le constructeur de la classe GrapheEcart*/
 GrapheEcart* Graphe::grapheEcartFlotNul() const
 {
     string nom;                                                             // Nom du graphe.
 
     nom = "Graphe d'écart du graphe : " + this->nom;
     GrapheEcart *gEcart = new GrapheEcart(nom,this);
 
     return gEcart;
 }
 
 
 /* Q2 | Détermineur un plus court chemin entre les sommets s et p.
 * Prerequis : le graphe ne doit pas être vide.*/
 listeArcs_t Graphe::PCCsp(unsigned int s, unsigned int p) const
 {
     listeArcs_t pcc;
     listeArcs_t arcsParcourus;
     vector<unsigned int> file;
     vector<bool> sVu;                                                       // Sommets déjà vu.
     unsigned int sommet;
 
     if(s == p)
         return pcc;
 
     // Initialisation du vecteur de sommets déjà vus..
     for(unsigned int i = 0; i < this->arcs.size(); i++)
         sVu.push_back(false);
 
     // Mise dans la file du sommet de départ.
     file.push_back(s);
 
     while(file.size() > 0)
     {
         sommet = file[0];
 
         for(unsigned int i = 0; i < this->arcs[sommet].size(); i++)
             if(this->arcs[sommet][i]->getS2() == p)
             {
                 arcsParcourus.push_back(this->arcs[sommet][i]);
                 unCheminSaP(s,p,arcsParcourus,pcc);
                 return pcc;
             }
             else
                 if(sVu[this->arcs[sommet][i]->getS2()] == false)
                 {
                     file.push_back(this->arcs[sommet][i]->getS2());
                     arcsParcourus.push_back(this->arcs[sommet][i]);
                     sVu[this->arcs[sommet][i]->getS2()] = true;
                 }
 
         file.erase(file.begin());
     }
 
     return pcc;
 }
 
 
 /* Q3 | Donne la plus petite valuation (capacité) sur le chemin.
 * Prerequis : Le chemin doit contenir au moins un arc.*/
 unsigned int Graphe::capaciteMinDuChemin(listeArcs_t chemin) const
 {
     unsigned int c = chemin[0]->getCapacite();
 
     for(unsigned int i = 1; i < chemin.size(); i++)
         c = min(c,chemin[i]->getCapacite());
 
     return c;
 }
 
 
 /* Q5 | Met à jour à partir du graphe d'écart final le graphe et retourne le flot maximum.
 */
 int Graphe::miseAJour(GrapheEcart *ge)
 {
     arcs_t la = ge->getListeArcs();
     int flotMax = 0;
 
     for(unsigned int k = 0; k < la.size(); k++)
         for(unsigned int l = 0; l < la[k].size(); l++)
         {
             this->arcDansGraphe(la[k][l])->setFlot(la[k][l]->getFlot());
 
             if(la[k][l]->getS2() == this->p)
                 flotMax += la[k][l]->getFlot();
         }
 
     return flotMax;
 }
 
 //================================//
 
 
 
 
 /* Ajoute une arc au graphe
 * L'arc est palcée en fonction de son sommets de départ puis de celui d'arrivé
 */
 bool Graphe::ajouteArc(Arc *arc)
 {
     // Si les deux sommets de l'arc appartiennent au graphe.
     if(arc->getS1() <= (this->arcs.size() -1) && arc->getS2() <= (this->arcs.size() -1))
     {
         // On place l'arc dans la liste correspondante au sommet de départ
         // et on détermine la position da l'arc dans cette liste selon le sommet d'arrivé.
         for(unsigned int j = 0; j < this->arcs[arc->getS1()].size(); j++)
             if(this->arcs[arc->getS1()][j]->getS2() > arc->getS2())
             {
                 this->arcs[arc->getS1()].insert(this->arcs[arc->getS1()].begin()+j,arc);
                 return true;
             }
 
         this->arcs[arc->getS1()].push_back(arc);
     }
     else
         return false;                                                       // Le ne peut être ajouté.
 
     return true;
 }
 
 
 /* Charge un graphe fixe quelconque permettant de tester les différentes fonctions
 */
 void Graphe::chargeG1()
 {
     /* Un graphe constitué de 4 sommets et 3 arrêtes */
     // TODO Ajouter des sommets et des arrêtes afin de pouvoir tester les différents cas limite.
 
     listeArcs_t lArcs;                                                      // Liste d'arcs.
 
     // Création de la liste d'arcs sortants pour le sommet 0.
     Arc *arc = new Arc(0,1,1,0);
     lArcs.push_back(arc);
 
     Arc *arc2 = new Arc(0,2,5,0);
     lArcs.push_back(arc2);
 
     arcs.push_back(lArcs);
 
     // Création de la liste d'arcs sortants pour le sommet 1.
     lArcs.clear();
 
     Arc *arc3 = new Arc(1,3,3,2);
     lArcs.push_back(arc3);
 
     arcs.push_back(lArcs);
 
     // Création de la liste d'arcs sortants pour le sommet 2 et 3.
     lArcs.clear();
 
     arcs.push_back(lArcs);
     arcs.push_back(lArcs);
 }
 
 
 /* Affichage du graphe.
 */
 void Graphe::afficheGraphe() const
 {
     cout << " - " << nom << endl;
 
     for(unsigned int i = 0; i < arcs.size(); i++)                           // Pour chaques sommets.
         for(unsigned int j = 0; j < arcs[i].size(); j++)                    // Pour chaque arcs.
             this->arcs[i][j]->afficheArc();                                 // Dessin de l'arc.
 }
 
 bool Graphe::estDansListe(Arc *arc, listeArcs_t lArcs) const
 {
     for(unsigned int i = 0; i < lArcs.size(); i++)
         if(lArcs[i] == arc)
             return true;
 
     return false;
 }
 
 void Graphe::unCheminSaP(unsigned int s, unsigned int p, listeArcs_t l, listeArcs_t &pcc) const
 {
     // Condition d'arrêt de la récursion.
     if(s == p)
         return;
 
     for(unsigned int i = 0; i < l.size(); i++)
         if(l[i]->getS2() == p)
         {
             pcc.insert(pcc.begin(),l[i]);
             unCheminSaP(s,l[i]->getS1(),l,pcc);
             return;
         }
 }
 
 Arc* Graphe::arcInverse(Arc *arc)
 {
     for(unsigned int s = 0; s < this->arcs[arc->getS2()].size(); s++)
         if(this->arcs[arc->getS2()][s]->getS2() == arc->getS1())
             return this->arcs[arc->getS2()][s];
 
     return NULL;
 }
 
 Arc* Graphe::arcDansGraphe(Arc *a)
 {
     for(unsigned int s = 0; s < this->arcs[a->getS1()].size(); s++)
         if(this->arcs[a->getS1()][s]->getS2() == a->getS2())
             return this->arcs[a->getS1()][s];
 
     return NULL;
 }