commit 90651694fc95f8655ed2fafaffe3a4b5604b54f1
parent 1c700a3edba79b7eb580015ecdfa16841df1138a
Author: Yoann <yoann.b87@voila.fr>
Date: Fri, 3 Dec 2010 08:43:56 +0100
La question 5 est terminée.
Diffstat:
7 files changed, 539 insertions(+), 487 deletions(-)
diff --git a/complexite-Ex5/Arc.cpp b/complexite-Ex5/Arc.cpp
@@ -1,63 +1,73 @@
-#include "Arc.h"
-
-Arc::Arc(unsigned int a, unsigned int b, unsigned int c, unsigned int f)
-{
- this->a = a;
- this->b = b;
- this->capacite = c;
- this->flot = f;
-}
-
-Arc::Arc(const Arc *arc)
-{
- this->a = arc->a;
- this->b = arc->b;
- this->capacite = arc->capacite;
- this->flot = arc->flot;
-}
-
-void Arc::setS1(unsigned int val)
-{
- this->a = val;
-}
-
-unsigned int Arc::getS1() const
-{
- return this->a;
-}
-
-void Arc::setS2(unsigned int val)
-{
- this->b = val;
-}
-
-unsigned int Arc::getS2() const
-{
- return this->b;
-}
-
-void Arc::setFlot(unsigned int val)
-{
- this->flot = val;
-}
-
-unsigned int Arc::getFlot() const
-{
- return this->flot;
-}
-
-void Arc::setCapacite(unsigned int val)
-{
- this->capacite = val;
-}
-
-unsigned int Arc::getCapacite() const
-{
- return this->capacite;
-}
-
-void Arc::afficheArc()
-{
- cout << " " << this->a << " " << this->b << " c : " // Affichage des noms des sommets.
- << this->capacite << " f : " << this->flot << endl; // Affichage de la capacité et du flot.
-}
+#include "Arc.h"
+
+Arc::Arc(unsigned int a, unsigned int b, unsigned int c, unsigned int f)
+{
+ this->a = a;
+ this->b = b;
+ this->capacite = c;
+ this->flot = f;
+}
+
+Arc::Arc(const Arc *arc)
+{
+ this->a = arc->a;
+ this->b = arc->b;
+ this->capacite = arc->capacite;
+ this->flot = arc->flot;
+}
+
+void Arc::setS1(unsigned int val)
+{
+ this->a = val;
+}
+
+unsigned int Arc::getS1() const
+{
+ return this->a;
+}
+
+void Arc::setS2(unsigned int val)
+{
+ this->b = val;
+}
+
+unsigned int Arc::getS2() const
+{
+ return this->b;
+}
+
+void Arc::setFlot(unsigned int val)
+{
+ this->flot = val;
+}
+
+unsigned int Arc::getFlot() const
+{
+ return this->flot;
+}
+
+void Arc::setCapacite(unsigned int val)
+{
+ this->capacite = val;
+}
+
+unsigned int Arc::getCapacite() const
+{
+ return this->capacite;
+}
+
+bool Arc::getArcRetour()
+{
+ return this->arcRetour;
+}
+
+void Arc::setArcRetour(bool v)
+{
+ this->arcRetour = v;
+}
+
+void Arc::afficheArc()
+{
+ cout << " " << this->a << " " << this->b << " c : " // Affichage des noms des sommets.
+ << this->capacite << " f : " << this->flot << endl; // Affichage de la capacité et du flot.
+}
diff --git a/complexite-Ex5/Arc.h b/complexite-Ex5/Arc.h
@@ -1,36 +1,39 @@
-#ifndef ARC_H_INCLUDED
-#define ARC_H_INCLUDED
-
-#include <iostream>
-#include <vector>
-
-using namespace std;
-
-class Arc
-{
- private :
- unsigned int a; // Somment de départ
- unsigned int b; // Sommet d'arrivé.
- unsigned int capacite; // Capacité de l'arc.
- unsigned int flot; // Flot circulant dans l'arc.
-
- public :
- Arc(unsigned int a, unsigned int b, unsigned int c, unsigned int f);
- Arc(const Arc*);
- ~Arc();
- void setS1(unsigned int val);
- unsigned int getS1() const;
- void setS2(unsigned int val);
- unsigned int getS2() const;
- void setFlot(unsigned int val);
- unsigned int getFlot() const;
- void setCapacite(unsigned int val);
- unsigned int getCapacite() const;
- void afficheArc();
-
-};
-
-// Liste d'arcs sans classement par sommets.
-typedef vector<Arc*> listeArcs_t;
-
-#endif // ARC_H_INCLUDED
+#ifndef ARC_H_INCLUDED
+#define ARC_H_INCLUDED
+
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+class Arc
+{
+ private :
+ unsigned int a; // Somment de départ
+ unsigned int b; // Sommet d'arrivé.
+ unsigned int capacite; // Capacité de l'arc.
+ unsigned int flot; // Flot circulant dans l'arc.
+ bool arcRetour; // Vrai si arc retour, faux sinon
+
+ public :
+ Arc(unsigned int a, unsigned int b, unsigned int c, unsigned int f);
+ Arc(const Arc*);
+ ~Arc();
+ void setS1(unsigned int val);
+ unsigned int getS1() const;
+ void setS2(unsigned int val);
+ unsigned int getS2() const;
+ void setFlot(unsigned int val);
+ unsigned int getFlot() const;
+ void setCapacite(unsigned int val);
+ unsigned int getCapacite() const;
+ bool getArcRetour();
+ void setArcRetour(bool);
+ void afficheArc();
+
+};
+
+// Liste d'arcs sans classement par sommets.
+typedef vector<Arc*> listeArcs_t;
+
+#endif // ARC_H_INCLUDED
diff --git a/complexite-Ex5/Graphe.cpp b/complexite-Ex5/Graphe.cpp
@@ -1,230 +1,260 @@
-#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;
-}
-//================================//
-
-
-
-
-/* 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;
-}
-
-
-
-
-
-
-
-
+#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;
+}
+
+
+
+
+
+
+
+
diff --git a/complexite-Ex5/Graphe.h b/complexite-Ex5/Graphe.h
@@ -1,46 +1,48 @@
-#ifndef GRAPHE_H_INCLUDED
-#define GRAPHE_H_INCLUDED
-
-#include <iostream>
-
-#include "Arc.h"
-
-class GrapheEcart;
-
-// Définition du type de donnée : "liste de sommets et arcs".
-typedef vector<listeArcs_t> arcs_t;
-
-class Graphe
-{
- protected :
- unsigned int s; // La source.
- unsigned int p; // Le puit.
- arcs_t arcs; // Les sommets et arrêtes associées.
- string nom; // Nom du graphe.
-
-
- public :
- Graphe(string nom); // Constructeur par défaut.
- Graphe(string nom,const Graphe*); // Constructeur par copie.
- ~Graphe(); // Destructeur de l'objet.
-
- void chargeG1(); // Charge le graphe G1.
- bool ajouteArc(Arc*); // Ajoute un arc au graphe.
- bool contientArc(Arc*) const; // Appartenance de l'arc au graphe en terme de pointeurs.
- void afficheGraphe() const; // Affiche le graphe.
-
- // Accesseurs.
- arcs_t getArcs() const;
-
- // Fonctions répondants à l'énoncé.
- GrapheEcart* grapheEcartFlotNul() const; // Donne le graphe d'écart pour un flot nul.
- listeArcs_t PCCsp(unsigned int s, unsigned int p) const; // Le plus court chemin entre s et p.
- unsigned int capaciteMinDuChemin(listeArcs_t chemin) const; // La plus petite valuation du chemin.
-
- protected :
- bool estDansListe(Arc*, listeArcs_t) const;
- void unCheminSaP(unsigned int s, unsigned int p, listeArcs_t l, listeArcs_t &pcc) const;
- Arc* arcInverse(Arc*);
-};
-
-#endif // GRAPHE_H_INCLUDED
+#ifndef GRAPHE_H_INCLUDED
+#define GRAPHE_H_INCLUDED
+
+#include <iostream>
+
+#include "Arc.h"
+
+class GrapheEcart;
+
+// Définition du type de donnée : "liste de sommets et arcs".
+typedef vector<listeArcs_t> arcs_t;
+
+class Graphe
+{
+ protected :
+ unsigned int s; // La source.
+ unsigned int p; // Le puit.
+ arcs_t arcs; // Les sommets et arrêtes associées.
+ string nom; // Nom du graphe.
+
+
+ public :
+ Graphe(string nom); // Constructeur par défaut.
+ Graphe(string nom,const Graphe*); // Constructeur par copie.
+ ~Graphe(); // Destructeur de l'objet.
+
+ void chargeG1(); // Charge le graphe G1.
+ bool ajouteArc(Arc*); // Ajoute un arc au graphe.
+ bool contientArc(Arc*) const; // Appartenance de l'arc au graphe en terme de pointeurs.
+ void afficheGraphe() const; // Affiche le graphe.
+
+ // Accesseurs.
+ arcs_t getArcs() const;
+
+ // Fonctions répondants à l'énoncé.
+ GrapheEcart* grapheEcartFlotNul() const; // Donne le graphe d'écart pour un flot nul.
+ listeArcs_t PCCsp(unsigned int s, unsigned int p) const; // Le plus court chemin entre s et p.
+ unsigned int capaciteMinDuChemin(listeArcs_t chemin) const; // La plus petite valuation du chemin.
+ int miseAJour(GrapheEcart*);
+
+ protected :
+ bool estDansListe(Arc*, listeArcs_t) const;
+ void unCheminSaP(unsigned int s, unsigned int p, listeArcs_t l, listeArcs_t &pcc) const;
+ Arc* arcInverse(Arc*);
+ Arc* arcDansGraphe(Arc*); // Retourne l'arc du graphe correspondant (par rappert au sommets).
+};
+
+#endif // GRAPHE_H_INCLUDED
diff --git a/complexite-Ex5/GrapheEcart.cpp b/complexite-Ex5/GrapheEcart.cpp
@@ -1,50 +1,56 @@
-#include "GrapheEcart.h"
-
-GrapheEcart::GrapheEcart(string nom) : Graphe(nom)
-{
-
-}
-
- //------- 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.*/
-GrapheEcart::GrapheEcart(string nom, const Graphe *g) : Graphe(nom,g)
-{
- Arc *arcInv; // Arc inverse.
- Arc *arc; // Arc courrant.
-
- for(unsigned int i = 0; i < g->getArcs().size(); i++)
- for(unsigned int j = 0; j < g->getArcs()[i].size(); j++)
- this->arcs[i][j]->setFlot(0);
-
- for(unsigned int i = 0; i < g->getArcs().size(); i++)
- for(unsigned int j = 0; j < g->getArcs()[i].size(); j++)
- {
- arc = g->getArcs()[i][j];
-
- arcInv = new Arc(arc->getS2(),arc->getS1(),0,0);
-
- this->ajouteArc(arcInv);
- }
-}
-
-
-
-/* Q4 | Met à jour la chaine augmentante du graphe correspondant au chemin pour une augment de k du flot.
-*/
-// TODO A tester !!!
-void GrapheEcart::miseAJour(listeArcs_t l,int k)
-{
- Arc *arcInv;
-
- for(unsigned int i = 0; i < l.size(); i++)
- {
- l[i]->setCapacite(l[i]->getCapacite()-k);
- arcInv = this->arcInverse(l[i]);
- arcInv->setCapacite(arcInv->getCapacite()+k);
- }
-}
-
-//================================//
+#include "GrapheEcart.h"
+
+GrapheEcart::GrapheEcart(string nom) : Graphe(nom)
+{
+
+}
+
+ //------- 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.*/
+GrapheEcart::GrapheEcart(string nom, const Graphe *g) : Graphe(nom,g)
+{
+ Arc *arcInv; // Arc inverse.
+ Arc *arc; // Arc courrant.
+
+ for(unsigned int i = 0; i < g->getArcs().size(); i++)
+ for(unsigned int j = 0; j < g->getArcs()[i].size(); j++)
+ this->arcs[i][j]->setFlot(0);
+
+ for(unsigned int i = 0; i < g->getArcs().size(); i++)
+ for(unsigned int j = 0; j < g->getArcs()[i].size(); j++)
+ {
+ arc = g->getArcs()[i][j];
+
+ arcInv = new Arc(arc->getS2(),arc->getS1(),0,0);
+ arcInv->setArcRetour(true);
+
+ this->ajouteArc(arcInv);
+ }
+}
+
+
+
+/* Q4 | Met à jour la chaine augmentante du graphe correspondant au chemin pour une augment de k du flot.
+*/
+// TODO A tester !!!
+void GrapheEcart::miseAJour(listeArcs_t l,int k)
+{
+ Arc *arcInv;
+
+ for(unsigned int i = 0; i < l.size(); i++)
+ {
+ l[i]->setCapacite(l[i]->getCapacite()-k);
+ arcInv = this->arcInverse(l[i]);
+ arcInv->setCapacite(arcInv->getCapacite()+k);
+ }
+}
+
+//================================//
+
+arcs_t GrapheEcart::getListeArcs()
+{
+ return this->arcs;
+}
diff --git a/complexite-Ex5/GrapheEcart.h b/complexite-Ex5/GrapheEcart.h
@@ -1,19 +1,20 @@
-#ifndef GRAPHEECART_H_INCLUDED
-#define GRAPHEECART_H_INCLUDED
-
-#include "Graphe.h"
-
-class GrapheEcart : public Graphe
-{
- private :
-
-
- public :
- GrapheEcart(string nom);
- GrapheEcart(string,const Graphe*);
- ~GrapheEcart();
-
- void miseAJour(listeArcs_t chemin, int k);
-};
-
-#endif // GRAPHEECART_H_INCLUDED
+#ifndef GRAPHEECART_H_INCLUDED
+#define GRAPHEECART_H_INCLUDED
+
+#include "Graphe.h"
+
+class GrapheEcart : public Graphe
+{
+ private :
+
+
+ public :
+ GrapheEcart(string nom);
+ GrapheEcart(string,const Graphe*);
+ ~GrapheEcart();
+
+ void miseAJour(listeArcs_t chemin, int k);
+ arcs_t getListeArcs();
+};
+
+#endif // GRAPHEECART_H_INCLUDED
diff --git a/complexite-Ex5/main.cpp b/complexite-Ex5/main.cpp
@@ -1,43 +1,43 @@
-#include <iostream>
-#include <vector>
-#include "Graphe.h"
-#include "GrapheEcart.h"
-
-using namespace std;
-
-void afficheListeArcs(listeArcs_t l);
-
-int main()
-{
- Graphe *g1 = new Graphe("G1"); // Un graphe quelconque g1.
- GrapheEcart *gEcart; // Un graphe d'écart.
- listeArcs_t pcc; // Une liste d'arcs pour le plus court chemin.
-
-
- g1->chargeG1(); // Initialisation de g1.
- gEcart = g1->grapheEcartFlotNul(); // Calcule le graphe d'écart pour le graphe.
- pcc = g1->PCCsp(0,3); // Calcule le plus court chemin.
-
-
- g1->afficheGraphe(); // Affichage du graphe.
- cout << endl << endl;
- gEcart->afficheGraphe(); // Affichage du graphe d'écart.
- cout << endl << endl;
- afficheListeArcs(pcc); // Affichage du chemin.
-
- return 0;
-}
-
-void afficheListeArcs(listeArcs_t l)
-{
- for(unsigned int i = 0; i < l.size(); i++)
- l[i]->afficheArc();
-}
-
-
-
-
-
-
-
-
+#include <iostream>
+#include <vector>
+#include "Graphe.h"
+#include "GrapheEcart.h"
+
+using namespace std;
+
+void afficheListeArcs(listeArcs_t l);
+
+int main()
+{
+ Graphe *g1 = new Graphe("G1"); // Un graphe quelconque g1.
+ GrapheEcart *gEcart; // Un graphe d'écart.
+ listeArcs_t pcc; // Une liste d'arcs pour le plus court chemin.
+
+
+ g1->chargeG1(); // Initialisation de g1.
+ gEcart = g1->grapheEcartFlotNul(); // Calcule le graphe d'écart pour le graphe.
+ pcc = g1->PCCsp(0,3); // Calcule le plus court chemin.
+
+
+ g1->afficheGraphe(); // Affichage du graphe.
+ cout << endl << endl;
+ gEcart->afficheGraphe(); // Affichage du graphe d'écart.
+ cout << endl << endl;
+ afficheListeArcs(pcc); // Affichage du chemin.
+
+ return 0;
+}
+
+void afficheListeArcs(listeArcs_t l)
+{
+ for(unsigned int i = 0; i < l.size(); i++)
+ l[i]->afficheArc();
+}
+
+
+
+
+
+
+
+
