commit 35f1f021eece42b58969797a8ad8e70a4b3c6377
parent 00d8254acb68f04bd60a3b017ec945f77818645c
Author: unknown <Administrateur@.(none)>
Date: Tue, 2 Nov 2010 18:58:33 +0100
Première version de l'exercice 5. Répond aux questions 1,2,3 et 4.
Diffstat:
7 files changed, 487 insertions(+), 0 deletions(-)
diff --git a/complexite-Ex5/Arc.cpp b/complexite-Ex5/Arc.cpp
@@ -0,0 +1,63 @@
+#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.
+}
diff --git a/complexite-Ex5/Arc.h b/complexite-Ex5/Arc.h
@@ -0,0 +1,36 @@
+#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
diff --git a/complexite-Ex5/Graphe.cpp b/complexite-Ex5/Graphe.cpp
@@ -0,0 +1,230 @@
+#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;
+}
+
+
+
+
+
+
+
+
diff --git a/complexite-Ex5/Graphe.h b/complexite-Ex5/Graphe.h
@@ -0,0 +1,46 @@
+#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
diff --git a/complexite-Ex5/GrapheEcart.cpp b/complexite-Ex5/GrapheEcart.cpp
@@ -0,0 +1,50 @@
+#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);
+ }
+}
+
+//================================//
diff --git a/complexite-Ex5/GrapheEcart.h b/complexite-Ex5/GrapheEcart.h
@@ -0,0 +1,19 @@
+#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
diff --git a/complexite-Ex5/main.cpp b/complexite-Ex5/main.cpp
@@ -0,0 +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();
+}
+
+
+
+
+
+
+
+
