-
Notifications
You must be signed in to change notification settings - Fork 0
/
Graphe.h
170 lines (128 loc) · 4.22 KB
/
Graphe.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
/**
* \file Graphe.h
* \brief Gestion d'un graphe.
* \author IFT-2008
* \version 0.1
* \date Juin-Juillet 2018
*
* Travail pratique numéro 2
*
*/
#include <iostream>
#include <fstream>
#include <stdexcept>
#include <string>
#include <vector>
#include <list>
//Vous pouvez ajouter d'autres librairies de la STL
#ifndef _GRAPHE__H
#define _GRAPHE__H
namespace TP2
{
/**
* \struct Ponderations
*
* \brief Une struture utilisée pour stocker les pondérations utilisées sur les arcs
*/
struct Ponderations
{
float duree; // La durée du vol en heures (ex. 0.8 heures entre Québec et Montréal)
float cout; // Le cout du trajet en dollars (ex. 220.46 $ pour un vol entre Québec et Montréal)
int ns; // Un niveau de sécurité représentant un indice qui peut être négatif
Ponderations(float d, float c, int n) : duree(d), cout(c), ns(n) {}
};
/**
* \struct Coordonnees
*
* \brief Une structure utilisée pour stocker les coordonnées d'un sommet
*/
struct Coordonnees
{
float lt; // La latitude en décimale (ex. pour la ville de Québec : 46.80)
float lg; // La longitude en décimale (ex. pour la ville de Québec : -71.24)
Coordonnees(float t, float g) : lt(t), lg(g) {}
};
/**
* \class Graphe
*
* \brief Classe représentant un graphe oriente
*/
class Graphe
{
public:
Graphe(size_t p_nbSommets = 10);
~Graphe();
void resize(size_t p_nouvelleTaille);
void nommer(size_t p_sommet, const std::string& p_nom, float p_lt, float p_lg);
void ajouterArc(size_t p_source, size_t p_destination, float p_duree, float p_cout, int p_ns);
void enleverArc(size_t p_source, size_t p_destination);
bool arcExiste(size_t p_source, size_t p_destination) const;
std::vector<size_t> listerSommetsAdjacents(size_t p_sommet) const;
std::string getNomSommet(size_t p_sommet) const;
size_t getNumeroSommet(const std::string& p_nom) const;
int getNombreSommets() const;
int getNombreArcs() const;
Ponderations getPonderationsArc(size_t p_source, size_t p_destination) const;
Coordonnees getCoordonnesSommet(size_t p_sommet) const;
/**
* \fn friend std::ostream& operator<<(std::ostream& out, const Graphe& g)
*
* \brief Surcharge de l'operateur de sortie
*/
friend std::ostream& operator<<(std::ostream& out, const Graphe& g)
{
out << "Le graphe contient " << g.m_nbSommets << " sommet(s) et "
<< g.m_nbArcs << " arc(s)" << std::endl << std::endl;
for (size_t i = 0; i < g.m_nbSommets; ++i)
{
out << "Sommet: " << g.m_villes[i].m_nom << std::endl << "Voisin(s): ";
if (g.m_listesAdj[i].size() == 0)
out << "Rien";
else
{
for (auto it = g.m_listesAdj[i].begin(); it != g.m_listesAdj[i].end(); ++it)
if (it == --g.m_listesAdj[i].end())
out << g.m_villes[it->m_destination].m_nom;
else
out << g.m_villes[it->m_destination].m_nom << ", ";
}
out << std::endl;
}
return out;
}
void sommetsExistent(size_t p_source, size_t p_destination) const;
private:
/**
* \struct Sommet
*
* \brief Une struture utilisée pour stocker les informations d'un sommet : son nom, ses coordonnees et son etat
*/
struct Sommet
{
std::string m_nom; // Le nom de la ville
Coordonnees m_coord; // Les coordonnées géospatiales de la ville
bool m_etat; // Pour marquer une ville
Sommet() : m_nom(""), m_coord(Coordonnees(0,0)), m_etat(false) {}
Sommet(std::string nv, Coordonnees cv, bool ev) : m_nom(nv), m_coord(cv), m_etat(ev) {}
void setNom(std::string p_nom);
void setCoordonnees(Coordonnees p_coord);
};
std::vector<Sommet> m_villes; /*!< Le vecteur des sommets */
/**
* \struct Arc
*
* \brief Une struture utilisée pour stocker les informations d'un arc : sa destination et ses ponderations
*/
struct Arc
{
size_t m_destination;
Ponderations m_poids; // Les pondérations utilisées pour un trajet entre deux villes
Arc(size_t dest, Ponderations p) : m_destination(dest), m_poids(p) {}
};
std::vector<std::list<Arc> > m_listesAdj; /*!< les listes d'adjacence */
size_t m_nbSommets; // Le nombre de sommets dans le graphe
size_t m_nbArcs; // Le nombre des arcs dans le graphe
void sommetExiste(size_t p_sommet, std::string message) const;
};
}//Fin du namespace
#endif