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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
| #include <set>
#include <map>
#include <iostream>
#include <fstream>
#include <limits>
// Je te mets mes coms toutes les questions ne sont pas primordiales tt suite si tu n a pas trop le temps ne répond que aux trucs vitaux :p
// merci du coup de main !
/* class et struct sont quasiment équivalent, la seule grosse différence, c'est la privauté par défaut*/
//un type utilisé comme exception, par get_graph(...)
struct file_not_found{}; // je sais ce qu'est une exception mais en Java quand j'en utilisais la classe n'était pas vide, je ne comprends pas ce qui se passe
struct parse_error{}; // quand tu soulèves une de ces deux exceptions
namespace graph {
template <typename Index, typename Value> // Si je comprends bien, tu ne définis pas à l'avance le type de mes sommets et de mes poids de sorte que je pourrai
class graph { // utiliser des float comme des ints ou autre ?
//les typedef améliore l'écriture du code utilisateur
public:
typedef Index node_id_type;
typedef Value weight_type;
class edge {
private:
node_id_type from, to;
weight_type w;
public:
edge(node_id_type source, node_id_type target) : from(source), to(target), w(0) {}
edge(node_id_type source, node_id_type target, weight_type w) : from(source), to(target), w(weight) {}
weight_type weight() const {return w;}
weight_type& weight() {return w;} // Je ne vois pas pourquoi il y a deux méthodes ici, tu fais un get_poids avc une référence constante et une pas
// constante si j'ai bien compris, mais ça change quoi ici
node_id_type source() const {return from;}
node_id_type target() const {return to;}
};
private:
struct edge_comparator { // j'ai déjà utilisé ce objet_comparator mais je ne sais pas pk tu ne peux pas le déclarer comme une méthode
// normale et que tu dois mettre un struct
bool operator()(graph::edge const & a, graph::edge const & b) const {
return (a.from < b.from) or (a.from == b.from and a.to < b.to);
}
};
typedef std::set<edge, edge_comparator> edges_type;
edges_type my_edges;
typedef std::map<node_id_type> nodes_type; // là c'est carrément nébuleux, d'habitude je déclare une map comme ça std::map<Key, Value> éventuellement avec
// une fonction de comparaison pour les clés, std::map<Key, Value, KeyCompare>
nodes_type my_nodes;
public:
typedef typename edges_type::size_type edge_count_type; // les 6 typedef typename ici ne veulent malheureusement pas dire grand chose pour moi à l'heure
typedef typename nodes_type::size_type node_count_type; // où je t'écris ça
typedef typename edges_types::const_iterator edge_const_iterator;
typedef typename edges_types::iterator edge_iterator;
typedef typename nodes_type::const_iterator node_const_iterator;
typedef typename nodes_type::iterator node_iterator;
public:
node_count_type node_count() const {return my_nodes.size();}
edge_count_type edge_count() const {return my_edges.size();}
edge_const_iterator edges() const {return my_edges.begin();} // si j'ai bien compris compris ça renvoie un itérateur sur le set de edges
edge_const_iterator notAnEdge() const {return my_edges.end();} // Pourquoi deux fois les mêmes méthodes, quel est l'intérêt d'un iterator constant et d'un
// pas constant
edge_iterator edges() {return my_edges.begin();}
edge_iterator notAnEdge() {return my_edges.end();}
node_const_iterator nodes() const {return my_nodes.begin();}
node_const_iterator notANode() const {return my_nodes.end();}
node_iterator nodes() {return my_nodes.begin();}
node_iterator notANode() {return my_nodes.end();}
//je choisis le return *this pour te montrer la syntaxe permettant le chainage.
//on pourra écrire g.createEdge(1,2).remove(1,3);
//même si en pratique, pour ces fonctions, ce n'est pas utile. //merci c'est super classe j'avais déjà aperçu une fois ou deux
graph& createEdge()(node_id_type from, node_id_type to, weight_type w) {
my_nodes.insert(from);
my_nodes.insert(to);
my_edges.insert(edge(from, to, w));
return *this;
}
//L'opérateur suivant permet aussi le remplissage, mais c'est plus "fun" mais moins élégant.
//Je ne le mets que pour présenter un problème à connaitre
//Plus de détails dans parse
//accesseur par référence non constante
weight_type& operator()(node_id_type from, node_id_type to) {
my_nodes.insert(from);
my_nodes.insert(to);
return my_edges[edge(from, to)];
}
};//fin de la classe graph
template <typename NodeId, typename Weight>
graph<NodeId, Weight> parse(const char* filename) { // une raison pour laquelle tu n'utilises pas une string à la place de char* ?
graph<NodeId, Weight> graph;
std::string ligne;
std::ifstream fichier(filename, std::ios::in);
if (!fichier) throw file_not_found();
//le fichier contient une ligne de dimensionnement: nombre de sommets et d'aretes
if (!getline(fichier, ligne)) throw parse_error;
/*
en théorie, on aurait les trois lignes suivantes.
sauf qu'on va ignorer le nombre de noeud et d'arete dans cet exemple, car on ne vérifie pas le fichier.
int node_count, edge_count;
std::istringstream iss(ligne); //si je comprends bien ça met ligne dans iss qui est une sorte de liste où chaque élément est séparé par un espace dans ligne
iss >> node_count >> edge_count; // et ensuite ça mets les éléments de iss dans node_count et edge_count l'un après l'autre
*/
//puis des lignes d'arêtes: source, cible, poids
while (getline(fichier, ligne)) {
iss.str(ligne);
NodeId source, target;
iss >> source >> target;
//pas besoin d'une variable temporaire pour le poids, vu qu'on a l'opérateur () retournant une référence modifiable.
//mais il faut utiliser une seconde expression, à cause de l'ordre d'évaluation des sous-expressions qui n'est pas défini.
iss >> graph(source, target); // ici on dirait que tu fais appel au constructeur de graph mais je ne le trouve pas ?
/*
En dehors de cet exemple, j'aurai utilisé une temporaire, avec un code tel que:
NodeId source, target;
Weight weight;
iss >> source >> target >> weight;
graph.createEdge(source, target, weight);
*/
}
return graph;
}
}//fin du namespace graph
namespace algo {
//une classe d'exception pour le cas où le graphe contiendrait un cycle de poids négatif.
template <typename NodeId>
class NegativeCycleDetected {
private:
NodeId from, to;
public:
NegativeCycleDetected(NodeId source, NodeId target) :from(source), to(target) {}
NodeId source() const {return from;}
NodeId target() const {return to;}
};
template <typename NodeId>
std::ostream& operator<<(std::ostream& os, NegativeCycleDetected<NodeId> const& ncd) {
return os << "cycle de poids négatif détecté autour de l'arete ("<<ncd.source() <<','<<ncd.target<<')';
}
/*
Bellman-Ford établi pour chaque noeud quel est son prédecesseur depuis la source, et le prix total.
Il faut avoir une structure simple pour accéder à ces informations.
*/
template <typename NodeId, typename Weight>
class BFdata{
public:
typedef NodeId node_id_type;
typedef Weight weight_type;
private:
node_id_type predecessor;
weight_type weight_sum;
public:
BFdata(node_id_type source, weight_type cost) : predecessor(source), weight_sum(cost) {}
//grace à ce constructeur par défaut non explicite, l'initialisation de la map sera triviale.
BFdata() :
predecessor(-1),
weight_sum(numeric_limits<weight_type>::max()) // tu initilises en mettant que personne n'a de prédecesseurs au début et que le poids vaut le max
{} // du type que tu utilises pour le poids des arêtes donc ça pourrait être INT_MAX ou DOUBLE_MAX, balèze
// par contre c'est quoi {}
//opérateur de convénience, pour simplifier un peu l'écriture de BellmanFord(...)
BFdata& operator=(weight_type path_cost) { //désolé mais je ne vois pas en quoi ça simplifie, en fait je ne vois pas à quoi sert la méthode, enfin tu
// redéfinies l'opérateur = mais je ne comprends pas ce que le code signifie en terme d'égalité pour deux objets
//BFdata
weight_sum = path_cost;
return *this;
}
//à cause du précédent, je dois redéfinir l'opérateur de copie complet.
BFdata& operator=(BFdata const& other) {
predecessor = other.predecessor;
weight_sum = other.weight_sum;
return *this;
}
node_id_type source() const {return node_id_type;}
node_id_type& source() {return node_id_type;}
weight_type path_cost() const {return weight_sum;}
weight_type& path_cost() {return weight_sum;}
};
//using est un outil puissant, parce qu'il permet de créer un alias sur un type, même si c'est une template.
//ici, je déclare une template de type
template <typename NodeId, typename Weight>
using weight_matrix = std::map<NodeId, BFdata<NodeId, Weight>>; // en gros comme tu peux pas faire typedef sur un template tu fais using ?
/*
Je me suis référé à http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
Parce que je ne comprenais pas pourquoi tu utilise compute_min_edge, alors que ce n'est pas dans l'algo // dans la derniere version de mon code je l'ai corrigé
*/
template <typename NodeId, typename Weight>
weight_matrix<NodeId, Weight> //extrêmement bizarre, à quoi sert cette ligne ?
BellmanFord(graph::graph<NodeId, Weight> const& g, NodeId source) {
weight_matrix<NodeId, Weight> paths; //à la ligne 225 weight_marix c'est std::map<NodeId, BFdata<NodeId, Weight>> et maintenant
// je comprends plus ce que c'est
paths.emplace(source, 0);
//je fais la boucle à l'envers pour ne pas calculer tout le temps size(). // je ne vois pas pourquoi il te faudrait calculer size() ?
//ici, auto est pratique, car les noms complets sont effrayants:
//graph::graph<NodeId, Weight>::node_count_type
//graph::graph<NodeId, Weight>::edge_const_iterator
for (auto step = g.node_count(); step>0; --step) { // tant qu'il y a des noeuds ?
for (auto e = g.edges(); e!= g.notAnEdge(); ++e) { // tant qu'il y a des edges ?
Weight weight = paths[e->source()].path_cost() + e->weight(); // on crée un poids qui vaut la longueur du chemin pour aller de la source jusqu'à l'arête + le poids de l'arête
if (weight < paths[e->target()].path_cost()) {
paths[e->target()]=BFData<NodeId, Weight>(e.source(), weight); // cette ligne elle met à jour le plus cours chemin pour la target mais pourquoi
// tu dois écrire BFData<NodeId, Weight>(e.source(), weight)
}
}
}
for (auto e = g.edges(); e!= g.notAnEdge(); ++e) {
Weight weight = paths[e->source()].path_cost() + e->weight();
if (weight < paths[e->target()].path_cost()) {
throw NegativeCycleDetected(e.source, e.target);
}
}
return paths;
}
}//fin du namespace algo
typedef unsigned int node_id_type; // et donc là on finit par définir un type que le template va utiliser c'est ça ?
typedef int weight_type;
using Graph = graph::graph<node_id_type, weight_type>;
using Paths = algo::weight_matrix<node_id_type, weight_type>;
using namespace std;
int main(int argc, char* argv[]){
try {
Graph = graph::parse<node_id_type, weight_type>("g1.txt");
Paths paths = algo::compute(graph, 0); // je ne trouve pas compute dans le namespace algo
cout << "chemins depuis chaque noeuds: (noeud précédent, prix cumulé)" << endl;
for (auto node = g.nodes(); node != g.notANode(); ++node) {
cout << paths[*node].source() << "\t" << paths[*node].path_cost() << endl;
}
return 0;
} catch (NegativeCycleDetected<node_id_type> const& e) {
cerr << e << endl;
return 1;
} catch (parse_error const& e) {
cerr << "graph file is invalid." << endl;
return 2;
} catch (file_not_found const& e) {
cerr << "could not open file." << endl;
return 3;
}
} |
Bellman-Ford algorithm problème
, merci à tous.
Répondre avec citation
. Je connais aussi les vector mais on m'a appris que lorsque je connais à l'avance 
ou 
Envoyé par leternel
. Merci beaucoup pour ton code leternel mais il y a tellement de choses que je connais pas que ça va me prendre du temps de décrypter ! Néanmoins si tu pouvais m'expliquer à quoi sert un template en général ? Je pensais que c'était pour faire de la programmation générique comme en java (donc en gros on écrit des méthodes avec un type qu'on ne précise pas et puis ensuite le comportement de la méthode s'adapte en fonction du type utilisé). Oui je m'étais trompé avec le compute_min_edge, en fait il faut calculer le min de chemin de s -> w (un sommet intermédiaire) + wt (arête qui va de w jusquà la target). Par ailleurs à un moment tu dis que je dois avoir une structure efficace qui me permet de savoir quels sont les chemins empruntés, désolé j'aurai du te le dire mais dans mon exercice ce n'est pas demandé, je dois programmer l'algorithme de Johnson pour calculer les plus courts chemins de tous les sommets d'un graphe, sans pour autant savoir par où on passe. Je dois donc programmer Bellman-Ford puis redéfinir les poids des arêtes et enfin faire tourner dijkstra n fois.
Partager