Discussion :

[ternel]

Tu auras une réponse en deux parties, mais il faut que je les prépare:

• le code sans les templates
• les réponses à tes questions.

Concernant les exceptions:
Contrairement au java, en C++, toute valeur peut être lancée via throw. Il n'y a pas de throwable qu'il faille implémenter.
Par contre, il y a deux en-tête standards, <exception> qui contient la classe std::exception, équivalente à celle de java, <stdexcept> qui propose quelques exceptions standard, telles que std::invalid_argument ou std::out_of_range.
Ce sont des utilitaires que l'on peux utiliser, mais on n'est pas forcé.

Plus d'informations techniques sur cppreference.com

Il est parfaitement possible de définir des types vides, qui sont finalement comparables à une interface vide en java (Serializable?)
Une telle variable a techniquement une taille non nulle, pour contraindre chaque variable à avoir une adresse différente.

Comme le type de la classe suffit, je n'ai rien besoin de plus que savoir que mon exception est une file_not_found.
Au moment d'attraper l'exception, on a trois choix:

• la rattraper par copie (catch(int code_erreur))
• la rattraper par référence (catch(std::exception const& e)), ce qui permet de profiter des fonctions virtuelles
• rattraper n'importe quoi, sans distinction (catch(...))

Ce dernier choix n'est pas recommandé, en général.

[ImmoTPA]

Daccord merci infiniment leternel, en attendant je vois ce que je peux faire de mon côté. J'attends ta réponse avec impatience, merci beaucoup de tes efforts.

[ternel]

Premièrement, mea culpa, nodes_type aurait dû être un set, c'est juste que j'ai glissé...

Réponses aux questions simples, mais utiles

Seules les fonctions membre marquées const peuvent accéder à un objet constant.
En cas de surcharge, si l'objet n'est pas constant, c'est la fonction non const qui est appelée.
exemple avec et sans la surcharge:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Bidule{
public:
    char const* f() {return "Bidule modifiable";}
    char const* f() const {return "Bidule constant";}
    void rien() {}
};
 
int main() {
    Bidule b;
    Bidule const & ref = b;//référence vers un Bidule constant, telle qu'on en voit souvent dans les arguments de fonction.
    cout << b.f() << endl;//affiche "Bidule modifiable"
    cout << ref.f() << endl;//affiche "Bidule constant"
 
    b.rien(); //compile
    ref.rien(); // ne compile pas
}

En fait, le const ajouté au bout d'une fonction membre s'applique aussi à this. this est un pointeur vers le type dont la fonction est membre.
Si la fonction est const, this est un pointeur vers une constante. Si T est une classe, T::f() const utilise donc un T const* comme this

Là où ça devient sioux, c'est quand on combine avec les retours par référence non constante.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
class Bidule{
private:
    int v;
public:
    Bidule():v(0) {}
    int & valeur() {return v;}
    int valeur() const {return v;}
};
 
int main() {
    Bidule b;
    Bidule const & ref = b;//référence vers un Bidule constant, telle qu'on en voit souvent dans les arguments de fonction.
    cout << b.valeur() << endl;//affiche 0
    cout << ref.f() << endl;//affiche le meme 0
 
    b.valeur() = 2; //compile parfaitement car b est modifiable.
    cout << b.valeur() << endl;//affiche 2
 
    ref.valeur() = 5; // je ne sais plus si ca compile, mais ca sera tordu si c'est le cas.
    /* Si ca compile, un int temporaire est créé, reçoit la valeur du v de ref (c'est à dire le 2), puis est modifié à 5.
        Par contre, je ne suis pas sur que ca compile vraiment, parce que je ne crois pas qu'on puisse affecter une temporaire.
    */
 
    cout << ref.f() << endl;//affiche le 2
}

Je peux maintenant répondre à la question sur les itérateurs:

Les itérateurs existent en deux variantes: l'un permettant de modifier le contenu itéré, et pas l'autre.
Les const_iterator retournent des références constantes, mais sont prenables sur des collections constantes

edge_comparator
il s'agit d'une struct utilisé pour définir le set des aretes, juste en dessous.
J'ai fais le choix du foncteur (c'est le nom technique d'une classe avec operator()) plutôt qu'une simple fonction pour ne pas introduire un ordre non totale en fonction simple.
Ca me permettrait d'ajouter un operator<(...) ordonnant les edges selon les longueurs, ou par destination.


parse(const char*) n'utilise pas std::string parce que fstream n'a pas de constructeur utilisant std::string.
Et ca donne plus de liberté, car on peut très bien utiliser le résultat de string.c_str() en argument de parse().
Au passage, ifstream n'a pas besoin qu'on lui précise std::ios::in, c'est déjà dit dans le i de ifstream (il existe aussi fstream et ofstream)

stringstream
un istringstream est un flux d'entrée (un istream) similaire à ifstream ou cin, si ce n'est que la donnée parcourue n'est pas un fichier ou la console, mais une chaine de caractère, celle donnée en argument, ou manipulée via str() const et str(std::string)
On le lit avec les operator>>
De même il existe ostringstream qui défini les operator <<

[B]Dans parse(), toujours.[B]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

iss >> graph(source, target);   // ici on dirait que tu fais appel au constructeur de graph mais je ne le trouve pas ?

En fait, la première ligne de parse est graph<NodeId, Weight> graph;, c'est à dire déclarer la variable graph.
Je n'ai pas été gentil, j'aurai du l'appeler g, la ligne aurai été iss >> g(source, target);Du coup, la ligne suivante est l'usage de l'opérateur () sur cette variable.
Techniquement, c'est un appel à weight_type& graph::operator()(node_id_type from, node_id_type to);La ligne qui te gêne est strictement équivalente à iss >> (graph.operator()(source, target));Si vraiment ça avait été un constructeur, comme graph est template, j'aurai dû préciser les types de la template

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

iss >> graph<NodeId, Weight>(source, target);

quoique dans certains cas, ca puisse être deviné par le compilateur, grace aux arguments. Un cas classique est std::make_pair()


la syntaxe du constructeur

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
	BFdata() :
		predecessor(-1),
		weight_sum(std::numeric_limits<weight_type>::max())           // tu initialises en mettant que personne n'a de prédécesseurs 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 {}

Ton analyse est bonne.

En fait la syntaxe de déclaration du constructeur de la classe BFData serait BFdata().
Ici il s'agit de la définition de cette même fonction. Le constructeur possède une syntaxe particulière: Type(arguments) : initialisations {corps du constructeur}Chaque initialisation est séparée par une virgule, et correspond à:

• soit une initialisation d'une classe dont on hérite (en java, c'est super(...), auquel cas, la syntaxe est TypeParent(arguments d'un de ses constructeurs)
• soit l'initialisation d'un membre de la classe, auquel cas, la syntaxe est nom_du_membre(arguments d'un des constructeurs de son type)

Toutes les initialisations qui ne sont pas écrites sont faites avec le constructeur par défaut (0 pour les primitifs);
Et cela, même si dans le corps du constructeur, on leur affecte une nouvelle valeur.
C'est pour éviter cette construction par défaut, qui peut être coûteuse, voire impossible, qu'il faut toujours préférer les initialisations pour les membres qui sont des classes.

Donc le {} c'est juste le corps du constructeur, que j'ai mis en dessous pour qu'on le voit bien, et qui ne fait rien.
La plupart des classes sont dans ce cas.


Concernant ce fragment:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
	//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;
	}

supposons map<NodeId, BFData<NodeId, Weight>> paths;.
J'avais décidé d'écrire cet opérateur d'affectation (partielle) pour permettre d'écrire
paths[12]=8; plutôt que paths[12].path_cost()=8; qui me paraissait beaucoup moins chouette.
Ou que paths[12].path_cost(8); ou paths[12].set_path_cost(8);.

Mais finalement, si tu regardes bien cette fonction n'est meme pas utilisée


fonction BellmanFord

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
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
...
}

Ceci est la définition d'une template de fonction, dont la syntaxe générale est : template <sur quoi> type de retour nom (arguments...) { /*corps */ }En gros je déclare "pour toutes les combinaisons de type NodeId et Weigth, soit la fonction suivante:"
Ici, je déclare la fonction BellmanFord qui retourne une weight_matrix<NodeId, Weight>, c'est à dire un objet de la classe weight_matrix générée à partir du template correspondant, pour les types NodeId et Weight, ceux du patron de la fonction.
Elle prend en argument une référence constante (cf plus haut) sur un objet de type graph::graph<NodeId, Weight>, c'est à dire de la classe graph du namespace graph, générée pour les types NodeId et Weight.
Elle prend aussi un NodeId en second argument

En fait, il y a deux phénomènes: l'usage d'une instance spécifique du modèle graph (et de meme pour weight_matrix), et la template de fonction.
Voici un exemple plus simple de template de fonction: template <typename T> T addition(T a, T b) {return a+b;}Cette template-ci déclare "Cher compilateur, en cas de besoin, tu peux créer pour chaque type (que j'appelle T) que tu veux une fonction addition qui prend deux T, a et b, et retourne l'expression a+b, quoi que ca veuille dire." et aussi "NB, prions pour que ca ne soit pas un type pour lequel + n'est pas défini"

Plus d'information dans pas longtemps, avec le pavé sur les templates.

La quatrième ligne, qui semble te perturber, n'est autre que la déclaration de la variable paths, avec le type weight_matrix<NodeId, Weight>, vu que weight_matrix est un (alias de) template de type.
C'est bien le type que tu crois qui est utilisé.
Même si à chaque fois, NodeId et Weight sont des noms de type arbitraire (différents) liés à la template dans laquelle on est.


La double boucle

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
    //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) 
			}
		}
	}

En fait, avec for (auto step = 0; step< g.node_count(); ++step) il y a deux problèmes. D'abord node_count() serait appelé à chaque itération, et auto ne marcherai pas correctement (ce serait int et non graph::node_count_type).

La première boucle est "répéter autant de fois qu'il y a de nœuds dans g", la seconde est "pour chaque arete, en utilisant l'itérateur qu'on a défini dans la class graph.
Pourquoi BFData<NodeId, Weight>(e.source(), weight)? parce que je remplace le BFData correspondant à la cible de l'arete dans paths par un nouveau BFData, et que je dois préciser son type complet, en plus des arguments de son constructeur.

Et enfin, dernière question:
// et donc là on finit par définir un type que le template va utiliser c'est ça ?
Presque. C'est un type que l'on nomme pour la suite du code.

La fixation des templates est faite deux lignes plus loin, avec:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
using Graph = graph::graph<node_id_type, weight_type>;
using Paths = algo::weight_matrix<node_id_type, weight_type>;

Concernant les templates et typename

La template permet effectivement de déclarer plusieurs classes d'un coup.

Prenons un exemple (inutile pour l'instant)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
template <typename T> class Capsule {
     private:
          T content;
     public:
          Capsule(T const& that) : content(that) {}
          T get() const {return content;}
};

Ce code déclare un patron de classe, nommé Capsule.
Quand on l'utilisera, le compilateur saura ainsi déclarer les classes réelles.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
int main() {
    Capsule<int> entier = 2
    Capsule<double> nombre = 2.5;
 
    //je suis pervers:
    Capsule< Capsule< Capsule< int > > > Bidule(4);
    return 0;
}

En ligne 2, le compilateur rencontre le type Capsule<int>, comme il ne le connait pas il cherche une template de ce nom.
Il trouve une correspondance exacte avec Capsule<T>. Il compile donc la classe pour le type T=int.
En ligne 3, il fait de même avec Capsule<double>

En ligne 6, il va réutiliser Capsule<int>, qu'il a compilé, mais créer les deux autres classes Capsule<Capsule<int>> et Capsule<Capsule<Capsule<int>>>Il faut bien comprendre que tu as donc au final quatre classes distinctes, sans aucun lien entre elle, si ce n'est d'avoir été générée par le compilateur à partir de la même template.
C'est très différent de java, qui après compilation en bytecode, n'utiliserait qu'une seule classe, Capsule<Object>, en glissant partout des conversions, rendues possibles par l'héritage de tout objet à Object.
C'est pour ça qu'en Java, tu ne peux pas avoir de List<int>, et qu'en C++, si.
d'ailleurs, si tu regardes du coté du "valhalla project", ils essayent de modifier le langage de bytecode pour permettre les génériques à la C++, et donc ArrayList<int>

Les templates marchent aussi sur les fonctions, comme je l'ai un peu montré dans mon code.

Fait amusant, on peut spécialiser les templates. Pour une classe, c'est tout ou rien.
Décidons d'être un peu malin, et gérons la Capsule de Capsule de n'importe quoi

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
template<typename T> class Capsule<Capsule<T>> {
     private:
          Capsule<T> mine;
     public:
          Capsule(T const& that) : mine(that){}
          Capsule<T> get() const {return mine;}
};

Un outil qui devient très pratique avec les classes et surtout les templates, ce sont les alias de type.
Créé soit avec typedef, soit avec using, ils permettent de donner un autre nom à un type.
Ces nouveaux noms suivent les mêmes règles de portée de définition que les autres choses.
On peut les définir dans une classe, ils peuvent alors être privés, protégés ou publics, selon le besoin. J'adopte en général la convention de nommage STL: truc_type (confère vector<T>::size_type)

en lige 220 environ, je vois:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
//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 ?

C'est précisément ca.


Vient alors un petit soucis combinant ces deux choses.
Supposons les quatre templates suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template<Typename T> struct Valeur{
    //une variable static de type T
    static T inner;
};
 
template<Typename T> struct Type{
    //soit Type::inner un autre nom pour T, quel que soit ce dernier
    typedef T inner;
    //ou encore, avec la norme C+11, using inner = T;
};
 
template<typename T> struct Alpha{
    T mine;
    Gamma() : mine(T::inner) {}
};
 
template<typename T> struct Beta{
    T::inner mine;
};

Maintenant, jouons un peu.

1. Avec Alpha<Valeur<int>> bidule;, bidule.mine est une variable, initialisée avec la valeur de la variable statique inner de Valeur<int>, qui se trouve être un int.
2. Avec Alpha<Type<int>> bidule;, bidule.mine est une variable, initialisée avec la valeur du inner de Alpha<int>. qui se trouve être un type... ca ne compile pas
3. Avec Beta<Valeur<int>> bidule;, bidule.mine est une variable, dont le type est inner de Valeur<int>, qui se trouve être une variable (de type int)... ca ne compile pas, car ce n'est pas un type
4. Avec Beta<Type<int>> bidule;, bidule.mine est une variable, dont le type est inner de Alpha<int>, qui est int.

Sauf que voila. imagine qu'il y ait un petit malin qui spécialise Type<int> ainsi:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
template<> struct Type<int>{
    static int inner;
};

subitement, Type<int>::inner n'est plus un type.
Du coup, Beta<Type<int>> bidule; ne peut pas compiler.

Pour ce genre de raison, la norme prévoit qu'un type doit toujours être identifié comme tel.
En fait, Beta ne compile pas en l'état, et l'erreur est proche de "expected typename before identifier T::inner"
La réponse est "je n'ai pas dis que T::inner est un type.
La solution est de préciser avec le mot clé typename.
Le code valide de Beta est donc le suivant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
template<typename T> struct Beta{
    typename T::inner mine;
};

Je peux maintenant répondre à ta question sur

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

typedef typename std::set<node_id_type>::iterator edge_iterator;

.
Ceci déclare, "quoi que soit std::set<node_id_type>, il définit le nom iterator comme étant un type. Soit edge_iterator un autre nom de ce type."

[ImmoTPA]

Hey ! Merci beaucoup de ta réponse extrêmement complète, j'ai lu un peu rapidement tout, je relirai demain après une bonne nuit de sommeil en détails pour tout comprendre. Par ailleurs je fais ce que je peux pour faire compiler ton code, j'ai repéré quelques erreurs du style max au lieu de std::max. Au point où j'en suis ton code ressemble à ça (quasi pas bougé à part les std qui manquent ci et là).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
295
#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(std::numeric_limits<weight_type>::std::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;
	}
}

Je te mets aussi le rapport d'erreurs, la plupart se ressemblent.

solu.cpp:52:32: error: wrong number of template arguments (1, should be 4)
In file included from /usr/include/c++/4.7/map:61:0,
from solu.cpp:2:
/usr/include/c++/4.7/bits/stl_map.h:90:11: error: provided for ‘template<class _Key, class _Tp, class _Compare, class _Alloc> class std::map’
solu.cpp:58:20: error: ‘nodes_type’ is not a class or namespace
solu.cpp:60:20: error: ‘edges_types’ has not been declared
solu.cpp:61:20: error: ‘edges_types’ has not been declared
solu.cpp:63:20: error: ‘nodes_type’ is not a class or namespace
solu.cpp:64:20: error: ‘nodes_type’ is not a class or namespace
solu.cpp:89:72: error: ‘createEdge’ declared as function returning a function
solu.cpp: In member function ‘graph::graph<Index, Value>::node_count_type graph::graph<Index, Value>::node_count() const’:
solu.cpp:68:55: error: request for member ‘size’ in ‘((const graph::graph<Index, Value>*)this)->graph::graph<Index, Value>::my_nodes’, which is of non-class type ‘const nodes_type {aka const int}’
solu.cpp: In member function ‘graph::graph<Index, Value>::node_const_iterator graph::graph<Index, Value>::nodes() const’:
solu.cpp:79:54: error: request for member ‘begin’ in ‘((const graph::graph<Index, Value>*)this)->graph::graph<Index, Value>::my_nodes’, which is of non-class type ‘const nodes_type {aka const int}’
solu.cpp: In member function ‘graph::graph<Index, Value>::node_const_iterator graph::graph<Index, Value>::notANode() const’:
solu.cpp:80:57: error: request for member ‘end’ in ‘((const graph::graph<Index, Value>*)this)->graph::graph<Index, Value>::my_nodes’, which is of non-class type ‘const nodes_type {aka const int}’
solu.cpp: In member function ‘graph::graph<Index, Value>::node_iterator graph::graph<Index, Value>::nodes()’:
solu.cpp:82:42: error: request for member ‘begin’ in ‘((graph::graph<Index, Value>*)this)->graph::graph<Index, Value>::my_nodes’, which is of non-class type ‘graph::graph<Index, Value>::nodes_type {aka int}’
solu.cpp: In member function ‘graph::graph<Index, Value>::node_iterator graph::graph<Index, Value>::notANode()’:
solu.cpp:83:45: error: request for member ‘end’ in ‘((graph::graph<Index, Value>*)this)->graph::graph<Index, Value>::my_nodes’, which is of non-class type ‘graph::graph<Index, Value>::nodes_type {aka int}’
solu.cpp: In member function ‘graph::graph<Index, Value>::weight_type& graph::graph<Index, Value>::operator()(graph::graph<Index, Value>::node_id_type, graph::graph<Index, Value>::node_id_type)’:
solu.cpp:102:13: error: request for member ‘insert’ in ‘((graph::graph<Index, Value>*)this)->graph::graph<Index, Value>::my_nodes’, which is of non-class type ‘graph::graph<Index, Value>::nodes_type {aka int}’
solu.cpp:103:13: error: request for member ‘insert’ in ‘((graph::graph<Index, Value>*)this)->graph::graph<Index, Value>::my_nodes’, which is of non-class type ‘graph::graph<Index, Value>::nodes_type {aka int}’
solu.cpp: In function ‘graph::graph<NodeId, Weight> graph::parse(const char*)’:
solu.cpp:118:49: error: expected primary-expression before ‘;’ token
solu.cpp:132:3: error: ‘iss’ was not declared in this scope
solu.cpp: In member function ‘algo::BFdata<NodeId, Weight>::node_id_type algo::BFdata<NodeId, Weight>::source() const’:
solu.cpp:215:50: error: expected primary-expression before ‘;’ token
solu.cpp: In member function ‘algo::BFdata<NodeId, Weight>::node_id_type& algo::BFdata<NodeId, Weight>::source()’:
solu.cpp:216:45: error: expected primary-expression before ‘;’ token
solu.cpp: At global scope:
solu.cpp:225:1: error: expected unqualified-id before ‘using’
solu.cpp:233:1: error: ‘weight_matrix’ does not name a type
solu.cpp:270:7: error: expected nested-name-specifier before ‘Graph’
solu.cpp:270:7: error: ‘Graph’ has not been declared
solu.cpp:270:13: error: expected ‘;’ before ‘=’ token
solu.cpp:270:13: error: expected unqualified-id before ‘=’ token
solu.cpp:271:7: error: expected nested-name-specifier before ‘Paths’
solu.cpp:271:7: error: ‘Paths’ has not been declared
solu.cpp:271:13: error: expected ‘;’ before ‘=’ token
solu.cpp:271:13: error: expected unqualified-id before ‘=’ token

Si je comprends bien les "request for member" c'est des fonctions dont il attend quelles soient définies et qui ne le sont pas : ce qui est bizarre vu que tu appliques juste des méthodes de la classe std::map à ... une map

Et la plupart des autres erreurs c'est des erreurs de portée nan (notamment lignes 58 à 64) ?

Je regarderai demain si je peux trouver comment les gérer. Bonne nuit et merci infiniment de ton implication.

[ternel]

J'ai corrigé le code pour le rendre compilable.

J'estime m'en être pas trop mal sorti, avec seulement une dizaine d'erreur dans ce fatras, alors que je fais du java au boulot, et que je n'ai codé que dans un éditeur de texte...

Bonne lecture!

[ImmoTPA]

Merci beaucoup ! Euh ouai bien sûr tu as géré merci ! Allez jgo lire ! Tu peux copier le code ou le mettre en pièce jointe ?

[ternel]

En fait, j'ai édité le message originel, pour ne pas laisser un code qui ne compile pas.

[ImmoTPA]

Hey leternel ! J'ai enfin compris ton code à une ou deux ptites exceptions près. Ton algo::BellmanFord il prend en paramètres un graph::graph<NodeId, Weight> const& et un NodeId source

Par ailleurs tu fixes ensuite tes templates comme ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
using Graph = graph::graph<node_id_type, weight_type>;             // fixation des templates
using Paths = algo::weight_matrix<node_id_type, weight_type>;

Donc ici tu dis Graph c'est le type que tu obtiens en utilisant un node_id_type et weight_type pour le template qui génère la classe graph (j'espère que c'est ça).

Et un peu plus loin tu fais l'appel de la fonction BellmanFord comme ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Paths paths = algo::BellmanFord(g, 0u);

donc ton BellmanFord il prend le graph g ok et puis le deuxième c'est censé être un NodeId source, et tu as donné 0u mais elle est de quel type cette variable ? et comment il sait quel type c'est ? Est ce que c'est pendant la compilation qu'il a dit ok tu m'as donné 0u je construis BellmanFord en me servant du template ?

Par ailleurs il semblerait qu'il ne stock que deux nodes dans le graph, je regarde la fonction parse voir ce qui a pu se passer.

Merci encore pour tout le travail que tu as réalisé pour m'aider.

Dans la fonction parse si je fais :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
while (std::getline(fichier, ligne)) {
		iss.str(ligne);
 
		NodeId source, target;
		Weight weight;
 
 		iss >> source >> target >> weight;    
 		std::cout << source << " - " << target << " - " << weight << std::endl;            
		graph.createEdge(source, target, weight);
	}

Il m'affiche 1 - 14 - 6 (c'est la première edge de mon fichier) à chaque fois du coup je n'ai que une seule edge dans mon graphe.

Pourtant si je fais un std::cout << iss.str() << std::endl; juste après iss.str(ligne) là il y a bien chaque ligne de mon fichier

Voici ce que j'ai trouvé sur wikipédia :

La classe istringstream dérivée de istream permet de lire à partir d'une chaîne de caractères, et possède deux constructeurs :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
istringstream ( openmode mode = in );
istringstream ( const string & str, openmode mode = in );

Je me suis dis que peut-être une fois que tu avais mis quelque chose dans ton istringstream tu pouvais plus le changer d'où le fait que j'ai toujours la même arête. Alors j'ai déplacé la déclaration

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

std::istringstream iss;

dans la boucle while et il semblerait que ça marche ! Je sais que tu m'avais dit que si on fait ça il fait l'allocation à chaque fois donc il y a peut-être mieux à faire en évitant ça néanmoins ton programme tourne en quelques secondes donc merci infiniment de ton aide, je n'ai plus qu'à terminer mon Johnson's Algorithm que je vais essayer de coder en suivant ton exemple.

[ternel]

Pour le 0u, c'est la constante 0, auquel j'ai ajouté un suffixe pour son type.
Sans suffixe, un littéral d'entier est de type int, qui est signé.
Il existe plusieurs suffixes:

• U, qui permet de définir des entiers dont le type est unsigned ...
• L, qui permet de définir des entiers dont le type est long (int)
• LL, qui permet de définir des entiers dont le type est long long (int)

On peut combiner U avec les longueurs, pour obtenir une constante de type unsigned long, par exemple.

Plus de précisions sont disponibles sur cppreference.com

Pour la boucle qui ne marche pas, tu as trouvé une bonne solution.
Un petit peu mieux, il faut combiner la déclaration et le remplissage du stream.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
while(std::getline(fichier, ligne)) {
    std::istreamstring iss(ligne);
    //...
}

[ImmoTPA]

Super merci ! C'est quasiment bon, plus qu'à comprendre pourquoi à la fin le shortest path de chaque sommet vaut à peu près LONG_MIN...Ta fonction parse a correctement rempli le graph donc je regarde du côté de l'initialisation.

Ici on fait une comparaison pour mettre à jour ou non :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
Weight weight = paths[e->source()].path_cost() + e->weight();
 			if (weight < paths[e->target()].path_cost()) {						
				paths[e->target()] = BFdata<NodeId, Weight>(e->source(), weight);

Mais en fait à moins que je n'ai pas bien vu on a pas initialisé les valeurs de paths[x].path_cost() pour les sommets x qui ne sont pas 0.

Du coup j'ai essayé ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
for(auto node = g.nodes(); node!= g.notANode() ; ++node)
 		paths.insert(std::make_pair(*node, BFdata<NodeId, Weight>()));

Malheureusement les résultats sont tjs aussi laids (très proches de LONG_MIN = -2147483647

Par ailleurs je me demandais dans ma boucle vu que 0 est un node j'ai du mettre paths[0] = std::numeric_limits<Weight>::max() et la ligne d'après ça dit :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

paths.insert(std::make_pair(source, BFdata<NodeId, Weight>(source, 0)));

Est ce que ces deux lignes fonctionnent bien toutes les deux ?

Au passage j'ai mis :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Paths paths = algo::BellmanFord(g, 1u);

car je n'ai pas de sommet 0 dans mon fichier

J'ai observé les choses suivantes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

paths[e->source()].path_cost()

contient bien la valeur numeric_limits<Weight>::max() jusqu'à l'arête 4-18 qui se trouve être l'arête numéro 156, ensuite la valeur passe à - numeric_limits<Weight>::max() d'où les paths qui sont proches de cette valeur à la fin du programme.


Problem solved !!