261 lines
6.9 KiB
C++
Executable File
261 lines
6.9 KiB
C++
Executable File
#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;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|