Graphe.h (2006B)
1 #ifndef GRAPHE_H_INCLUDED 2 #define GRAPHE_H_INCLUDED 3 4 #include <iostream> 5 6 #include "Arc.h" 7 8 class GrapheEcart; 9 10 // Définition du type de donnée : "liste de sommets et arcs". 11 typedef vector<listeArcs_t> arcs_t; 12 13 class Graphe 14 { 15 protected : 16 unsigned int s; // La source. 17 unsigned int p; // Le puit. 18 arcs_t arcs; // Les sommets et arrêtes associées. 19 string nom; // Nom du graphe. 20 21 22 public : 23 Graphe(string nom); // Constructeur par défaut. 24 Graphe(string nom,const Graphe*); // Constructeur par copie. 25 ~Graphe(); // Destructeur de l'objet. 26 27 void chargeG1(); // Charge le graphe G1. 28 bool ajouteArc(Arc*); // Ajoute un arc au graphe. 29 bool contientArc(Arc*) const; // Appartenance de l'arc au graphe en terme de pointeurs. 30 void afficheGraphe() const; // Affiche le graphe. 31 32 // Accesseurs. 33 arcs_t getArcs() const; 34 35 // Fonctions répondants à l'énoncé. 36 GrapheEcart* grapheEcartFlotNul() const; // Donne le graphe d'écart pour un flot nul. 37 listeArcs_t PCCsp(unsigned int s, unsigned int p) const; // Le plus court chemin entre s et p. 38 unsigned int capaciteMinDuChemin(listeArcs_t chemin) const; // La plus petite valuation du chemin. 39 int miseAJour(GrapheEcart*); 40 41 protected : 42 bool estDansListe(Arc*, listeArcs_t) const; 43 void unCheminSaP(unsigned int s, unsigned int p, listeArcs_t l, listeArcs_t &pcc) const; 44 Arc* arcInverse(Arc*); 45 Arc* arcDansGraphe(Arc*); // Retourne l'arc du graphe correspondant (par rappert au sommets). 46 }; 47 48 #endif // GRAPHE_H_INCLUDED