1// Copyright Michael Drexl 2005, 2006.
2// Distributed under the Boost Software License, Version 1.0.
3// (See accompanying file LICENSE_1_0.txt or copy at
4// http://boost.org/LICENSE_1_0.txt)
5
6#include <boost/config.hpp>
7
8#ifdef BOOST_MSVC
9#pragma warning(disable : 4267)
10#endif
11
12#include <boost/graph/adjacency_list.hpp>
13//#include <boost/graph/dijkstra_shortest_paths.hpp>
14
15#include <boost/graph/r_c_shortest_paths.hpp>
16#include <iostream>
17#include <boost/core/lightweight_test.hpp>
18
19using namespace boost;
20
21struct SPPRC_Example_Graph_Vert_Prop
22{
23 SPPRC_Example_Graph_Vert_Prop(int n = 0, int e = 0, int l = 0)
24 : num(n), eat(e), lat(l)
25 {
26 }
27 int num;
28 // earliest arrival time
29 int eat;
30 // latest arrival time
31 int lat;
32};
33
34struct SPPRC_Example_Graph_Arc_Prop
35{
36 SPPRC_Example_Graph_Arc_Prop(int n = 0, int c = 0, int t = 0)
37 : num(n), cost(c), time(t)
38 {
39 }
40 int num;
41 // traversal cost
42 int cost;
43 // traversal time
44 int time;
45};
46
47typedef adjacency_list< vecS, vecS, directedS, SPPRC_Example_Graph_Vert_Prop,
48 SPPRC_Example_Graph_Arc_Prop >
49 SPPRC_Example_Graph;
50
51// data structures for spp without resource constraints:
52// ResourceContainer model
53struct spp_no_rc_res_cont
54{
55 spp_no_rc_res_cont(int c = 0) : cost(c) {};
56 spp_no_rc_res_cont& operator=(const spp_no_rc_res_cont& other)
57 {
58 if (this == &other)
59 return *this;
60 this->~spp_no_rc_res_cont();
61 new (this) spp_no_rc_res_cont(other);
62 return *this;
63 }
64 int cost;
65};
66
67bool operator==(
68 const spp_no_rc_res_cont& res_cont_1, const spp_no_rc_res_cont& res_cont_2)
69{
70 return (res_cont_1.cost == res_cont_2.cost);
71}
72
73bool operator<(
74 const spp_no_rc_res_cont& res_cont_1, const spp_no_rc_res_cont& res_cont_2)
75{
76 return (res_cont_1.cost < res_cont_2.cost);
77}
78
79// ResourceExtensionFunction model
80class ref_no_res_cont
81{
82public:
83 inline bool operator()(const SPPRC_Example_Graph& g,
84 spp_no_rc_res_cont& new_cont, const spp_no_rc_res_cont& old_cont,
85 graph_traits< SPPRC_Example_Graph >::edge_descriptor ed) const
86 {
87 new_cont.cost = old_cont.cost + g[ed].cost;
88 return true;
89 }
90};
91
92// DominanceFunction model
93class dominance_no_res_cont
94{
95public:
96 inline bool operator()(const spp_no_rc_res_cont& res_cont_1,
97 const spp_no_rc_res_cont& res_cont_2) const
98 {
99 // must be "<=" here!!!
100 // must NOT be "<"!!!
101 return res_cont_1.cost <= res_cont_2.cost;
102 // this is not a contradiction to the documentation
103 // the documentation says:
104 // "A label $l_1$ dominates a label $l_2$ if and only if both are
105 // resident at the same vertex, and if, for each resource, the resource
106 // consumption of $l_1$ is less than or equal to the resource
107 // consumption of $l_2$, and if there is at least one resource where
108 // $l_1$ has a lower resource consumption than $l_2$." one can think of
109 // a new label with a resource consumption equal to that of an old label
110 // as being dominated by that old label, because the new one will have a
111 // higher number and is created at a later point in time, so one can
112 // implicitly use the number or the creation time as a resource for
113 // tie-breaking
114 }
115};
116// end data structures for spp without resource constraints:
117
118// data structures for shortest path problem with time windows (spptw)
119// ResourceContainer model
120struct spp_spptw_res_cont
121{
122 spp_spptw_res_cont(int c = 0, int t = 0) : cost(c), time(t) {}
123 spp_spptw_res_cont& operator=(const spp_spptw_res_cont& other)
124 {
125 if (this == &other)
126 return *this;
127 this->~spp_spptw_res_cont();
128 new (this) spp_spptw_res_cont(other);
129 return *this;
130 }
131 int cost;
132 int time;
133};
134
135bool operator==(
136 const spp_spptw_res_cont& res_cont_1, const spp_spptw_res_cont& res_cont_2)
137{
138 return (res_cont_1.cost == res_cont_2.cost
139 && res_cont_1.time == res_cont_2.time);
140}
141
142bool operator<(
143 const spp_spptw_res_cont& res_cont_1, const spp_spptw_res_cont& res_cont_2)
144{
145 if (res_cont_1.cost > res_cont_2.cost)
146 return false;
147 if (res_cont_1.cost == res_cont_2.cost)
148 return res_cont_1.time < res_cont_2.time;
149 return true;
150}
151
152// ResourceExtensionFunction model
153class ref_spptw
154{
155public:
156 inline bool operator()(const SPPRC_Example_Graph& g,
157 spp_spptw_res_cont& new_cont, const spp_spptw_res_cont& old_cont,
158 graph_traits< SPPRC_Example_Graph >::edge_descriptor ed) const
159 {
160 const SPPRC_Example_Graph_Arc_Prop& arc_prop = get(p: edge_bundle, g)[ed];
161 const SPPRC_Example_Graph_Vert_Prop& vert_prop
162 = get(p: vertex_bundle, g)[target(e: ed, g)];
163 new_cont.cost = old_cont.cost + arc_prop.cost;
164 int& i_time = new_cont.time;
165 i_time = old_cont.time + arc_prop.time;
166 i_time < vert_prop.eat ? i_time = vert_prop.eat : 0;
167 return i_time <= vert_prop.lat ? true : false;
168 }
169};
170
171// DominanceFunction model
172class dominance_spptw
173{
174public:
175 inline bool operator()(const spp_spptw_res_cont& res_cont_1,
176 const spp_spptw_res_cont& res_cont_2) const
177 {
178 // must be "<=" here!!!
179 // must NOT be "<"!!!
180 return res_cont_1.cost <= res_cont_2.cost
181 && res_cont_1.time <= res_cont_2.time;
182 // this is not a contradiction to the documentation
183 // the documentation says:
184 // "A label $l_1$ dominates a label $l_2$ if and only if both are
185 // resident at the same vertex, and if, for each resource, the resource
186 // consumption of $l_1$ is less than or equal to the resource
187 // consumption of $l_2$, and if there is at least one resource where
188 // $l_1$ has a lower resource consumption than $l_2$." one can think of
189 // a new label with a resource consumption equal to that of an old label
190 // as being dominated by that old label, because the new one will have a
191 // higher number and is created at a later point in time, so one can
192 // implicitly use the number or the creation time as a resource for
193 // tie-breaking
194 }
195};
196// end data structures for shortest path problem with time windows (spptw)
197
198struct spp_spptw_marked_res_cont
199{
200 spp_spptw_marked_res_cont(
201 SPPRC_Example_Graph::vertex_descriptor v, int c = 0, int t = 0)
202 : cost(c), time(t), marked()
203 {
204 marked.insert(x: v);
205 }
206 spp_spptw_marked_res_cont& operator=(const spp_spptw_marked_res_cont& other)
207 {
208 if (this == &other)
209 return *this;
210 this->~spp_spptw_marked_res_cont();
211 new (this) spp_spptw_marked_res_cont(other);
212 return *this;
213 }
214 int cost;
215 int time;
216 std::set< SPPRC_Example_Graph::vertex_descriptor > marked;
217};
218
219bool operator==(const spp_spptw_marked_res_cont& res_cont_1,
220 const spp_spptw_marked_res_cont& res_cont_2)
221{
222 return res_cont_1.cost == res_cont_2.cost
223 && res_cont_1.time == res_cont_2.time
224 && res_cont_1.marked == res_cont_2.marked;
225}
226
227bool operator<(const spp_spptw_marked_res_cont& res_cont_1,
228 const spp_spptw_marked_res_cont& res_cont_2)
229{
230 if (res_cont_1.cost > res_cont_2.cost || res_cont_1.time > res_cont_2.time)
231 {
232 return false;
233 }
234
235 if (!std::includes(first1: res_cont_2.marked.begin(), last1: res_cont_2.marked.end(),
236 first2: res_cont_1.marked.begin(), last2: res_cont_1.marked.end()))
237 {
238 return false;
239 }
240
241 if (res_cont_1.cost == res_cont_2.cost)
242 {
243 return res_cont_1.time < res_cont_2.time;
244 }
245 return true;
246}
247
248class ref_spptw_marked
249{
250public:
251 inline bool operator()(const SPPRC_Example_Graph& g,
252 spp_spptw_marked_res_cont& new_cont,
253 const spp_spptw_marked_res_cont& old_cont,
254 graph_traits< SPPRC_Example_Graph >::edge_descriptor ed) const
255 {
256 const graph_traits< SPPRC_Example_Graph >::vertex_descriptor dest
257 = target(e: ed, g);
258
259 if (old_cont.marked.find(x: dest) != old_cont.marked.end())
260 {
261 return false;
262 }
263
264 const SPPRC_Example_Graph_Arc_Prop& arc_prop = get(p: edge_bundle, g)[ed];
265 const SPPRC_Example_Graph_Vert_Prop& vert_prop
266 = get(p: vertex_bundle, g)[dest];
267 new_cont.cost = old_cont.cost + arc_prop.cost;
268 new_cont.marked = old_cont.marked;
269 new_cont.marked.insert(x: dest);
270 int& i_time = new_cont.time;
271 i_time = old_cont.time + arc_prop.time;
272 i_time < vert_prop.eat ? i_time = vert_prop.eat : 0;
273 return i_time <= vert_prop.lat;
274 }
275};
276
277class dominance_spptw_marked
278{
279public:
280 inline bool operator()(const spp_spptw_marked_res_cont& res_cont_1,
281 const spp_spptw_marked_res_cont& res_cont_2) const
282 {
283 return res_cont_1.time <= res_cont_2.time
284 && res_cont_1.cost <= res_cont_2.cost
285 && std::includes(first1: res_cont_1.marked.begin(), last1: res_cont_1.marked.end(),
286 first2: res_cont_2.marked.begin(), last2: res_cont_2.marked.end());
287 }
288};
289
290int main(int, char*[])
291{
292 SPPRC_Example_Graph g;
293 add_vertex(p: SPPRC_Example_Graph_Vert_Prop(0, 0, 1000000000), g_&: g);
294 add_vertex(p: SPPRC_Example_Graph_Vert_Prop(1, 56, 142), g_&: g);
295 add_vertex(p: SPPRC_Example_Graph_Vert_Prop(2, 0, 1000000000), g_&: g);
296 add_vertex(p: SPPRC_Example_Graph_Vert_Prop(3, 89, 178), g_&: g);
297 add_vertex(p: SPPRC_Example_Graph_Vert_Prop(4, 0, 1000000000), g_&: g);
298 add_vertex(p: SPPRC_Example_Graph_Vert_Prop(5, 49, 76), g_&: g);
299 add_vertex(p: SPPRC_Example_Graph_Vert_Prop(6, 0, 1000000000), g_&: g);
300 add_vertex(p: SPPRC_Example_Graph_Vert_Prop(7, 98, 160), g_&: g);
301 add_vertex(p: SPPRC_Example_Graph_Vert_Prop(8, 0, 1000000000), g_&: g);
302 add_vertex(p: SPPRC_Example_Graph_Vert_Prop(9, 90, 158), g_&: g);
303 add_edge(u: 0, v: 7, p: SPPRC_Example_Graph_Arc_Prop(6, 33, 2), g_&: g);
304 add_edge(u: 0, v: 6, p: SPPRC_Example_Graph_Arc_Prop(5, 31, 6), g_&: g);
305 add_edge(u: 0, v: 4, p: SPPRC_Example_Graph_Arc_Prop(3, 14, 4), g_&: g);
306 add_edge(u: 0, v: 1, p: SPPRC_Example_Graph_Arc_Prop(0, 43, 8), g_&: g);
307 add_edge(u: 0, v: 4, p: SPPRC_Example_Graph_Arc_Prop(4, 28, 10), g_&: g);
308 add_edge(u: 0, v: 3, p: SPPRC_Example_Graph_Arc_Prop(1, 31, 10), g_&: g);
309 add_edge(u: 0, v: 3, p: SPPRC_Example_Graph_Arc_Prop(2, 1, 7), g_&: g);
310 add_edge(u: 0, v: 9, p: SPPRC_Example_Graph_Arc_Prop(7, 25, 9), g_&: g);
311 add_edge(u: 1, v: 0, p: SPPRC_Example_Graph_Arc_Prop(8, 37, 4), g_&: g);
312 add_edge(u: 1, v: 6, p: SPPRC_Example_Graph_Arc_Prop(9, 7, 3), g_&: g);
313 add_edge(u: 2, v: 6, p: SPPRC_Example_Graph_Arc_Prop(12, 6, 7), g_&: g);
314 add_edge(u: 2, v: 3, p: SPPRC_Example_Graph_Arc_Prop(10, 13, 7), g_&: g);
315 add_edge(u: 2, v: 3, p: SPPRC_Example_Graph_Arc_Prop(11, 49, 9), g_&: g);
316 add_edge(u: 2, v: 8, p: SPPRC_Example_Graph_Arc_Prop(13, 47, 5), g_&: g);
317 add_edge(u: 3, v: 4, p: SPPRC_Example_Graph_Arc_Prop(17, 5, 10), g_&: g);
318 add_edge(u: 3, v: 1, p: SPPRC_Example_Graph_Arc_Prop(15, 47, 1), g_&: g);
319 add_edge(u: 3, v: 2, p: SPPRC_Example_Graph_Arc_Prop(16, 26, 9), g_&: g);
320 add_edge(u: 3, v: 9, p: SPPRC_Example_Graph_Arc_Prop(21, 24, 10), g_&: g);
321 add_edge(u: 3, v: 7, p: SPPRC_Example_Graph_Arc_Prop(20, 50, 10), g_&: g);
322 add_edge(u: 3, v: 0, p: SPPRC_Example_Graph_Arc_Prop(14, 41, 4), g_&: g);
323 add_edge(u: 3, v: 6, p: SPPRC_Example_Graph_Arc_Prop(19, 6, 1), g_&: g);
324 add_edge(u: 3, v: 4, p: SPPRC_Example_Graph_Arc_Prop(18, 8, 1), g_&: g);
325 add_edge(u: 4, v: 5, p: SPPRC_Example_Graph_Arc_Prop(26, 38, 4), g_&: g);
326 add_edge(u: 4, v: 9, p: SPPRC_Example_Graph_Arc_Prop(27, 32, 10), g_&: g);
327 add_edge(u: 4, v: 3, p: SPPRC_Example_Graph_Arc_Prop(24, 40, 3), g_&: g);
328 add_edge(u: 4, v: 0, p: SPPRC_Example_Graph_Arc_Prop(22, 7, 3), g_&: g);
329 add_edge(u: 4, v: 3, p: SPPRC_Example_Graph_Arc_Prop(25, 28, 9), g_&: g);
330 add_edge(u: 4, v: 2, p: SPPRC_Example_Graph_Arc_Prop(23, 39, 6), g_&: g);
331 add_edge(u: 5, v: 8, p: SPPRC_Example_Graph_Arc_Prop(32, 6, 2), g_&: g);
332 add_edge(u: 5, v: 2, p: SPPRC_Example_Graph_Arc_Prop(30, 26, 10), g_&: g);
333 add_edge(u: 5, v: 0, p: SPPRC_Example_Graph_Arc_Prop(28, 38, 9), g_&: g);
334 add_edge(u: 5, v: 2, p: SPPRC_Example_Graph_Arc_Prop(31, 48, 10), g_&: g);
335 add_edge(u: 5, v: 9, p: SPPRC_Example_Graph_Arc_Prop(33, 49, 2), g_&: g);
336 add_edge(u: 5, v: 1, p: SPPRC_Example_Graph_Arc_Prop(29, 22, 7), g_&: g);
337 add_edge(u: 6, v: 1, p: SPPRC_Example_Graph_Arc_Prop(34, 15, 7), g_&: g);
338 add_edge(u: 6, v: 7, p: SPPRC_Example_Graph_Arc_Prop(35, 20, 3), g_&: g);
339 add_edge(u: 7, v: 9, p: SPPRC_Example_Graph_Arc_Prop(40, 1, 3), g_&: g);
340 add_edge(u: 7, v: 0, p: SPPRC_Example_Graph_Arc_Prop(36, 23, 5), g_&: g);
341 add_edge(u: 7, v: 6, p: SPPRC_Example_Graph_Arc_Prop(38, 36, 2), g_&: g);
342 add_edge(u: 7, v: 6, p: SPPRC_Example_Graph_Arc_Prop(39, 18, 10), g_&: g);
343 add_edge(u: 7, v: 2, p: SPPRC_Example_Graph_Arc_Prop(37, 2, 1), g_&: g);
344 add_edge(u: 8, v: 5, p: SPPRC_Example_Graph_Arc_Prop(46, 36, 5), g_&: g);
345 add_edge(u: 8, v: 1, p: SPPRC_Example_Graph_Arc_Prop(42, 13, 10), g_&: g);
346 add_edge(u: 8, v: 0, p: SPPRC_Example_Graph_Arc_Prop(41, 40, 5), g_&: g);
347 add_edge(u: 8, v: 1, p: SPPRC_Example_Graph_Arc_Prop(43, 32, 8), g_&: g);
348 add_edge(u: 8, v: 6, p: SPPRC_Example_Graph_Arc_Prop(47, 25, 1), g_&: g);
349 add_edge(u: 8, v: 2, p: SPPRC_Example_Graph_Arc_Prop(44, 44, 3), g_&: g);
350 add_edge(u: 8, v: 3, p: SPPRC_Example_Graph_Arc_Prop(45, 11, 9), g_&: g);
351 add_edge(u: 9, v: 0, p: SPPRC_Example_Graph_Arc_Prop(48, 41, 5), g_&: g);
352 add_edge(u: 9, v: 1, p: SPPRC_Example_Graph_Arc_Prop(49, 44, 7), g_&: g);
353
354 // spp without resource constraints
355
356 std::vector<
357 std::vector< graph_traits< SPPRC_Example_Graph >::edge_descriptor > >
358 opt_solutions;
359 std::vector< spp_no_rc_res_cont > pareto_opt_rcs_no_rc;
360 std::vector< int > i_vec_opt_solutions_spp_no_rc;
361 // std::cout << "r_c_shortest_paths:" << std::endl;
362 for (int s = 0; s < 10; ++s)
363 {
364 for (int t = 0; t < 10; ++t)
365 {
366 r_c_shortest_paths(g, vertex_index_map: get(p: &SPPRC_Example_Graph_Vert_Prop::num, g),
367 edge_index_map: get(p: &SPPRC_Example_Graph_Arc_Prop::num, g), s, t, pareto_optimal_solutions&: opt_solutions,
368 pareto_optimal_resource_containers&: pareto_opt_rcs_no_rc, rc: spp_no_rc_res_cont(0), ref: ref_no_res_cont(),
369 dominance: dominance_no_res_cont(),
370 la: std::allocator< r_c_shortest_paths_label< SPPRC_Example_Graph,
371 spp_no_rc_res_cont > >(),
372 vis: default_r_c_shortest_paths_visitor());
373 i_vec_opt_solutions_spp_no_rc.push_back(
374 x: pareto_opt_rcs_no_rc[0].cost);
375 // std::cout << "From " << s << " to " << t << ": ";
376 // std::cout << pareto_opt_rcs_no_rc[0].cost << std::endl;
377 }
378 }
379
380 // std::vector<graph_traits<SPPRC_Example_Graph>::vertex_descriptor>
381 // p( num_vertices( g ) );
382 // std::vector<int> d( num_vertices( g ) );
383 // std::vector<int> i_vec_dijkstra_distances;
384 // std::cout << "Dijkstra:" << std::endl;
385 // for( int s = 0; s < 10; ++s )
386 //{
387 // dijkstra_shortest_paths( g,
388 // s,
389 // &p[0],
390 // &d[0],
391 // get( &SPPRC_Example_Graph_Arc_Prop::cost, g ),
392 // get( &SPPRC_Example_Graph_Vert_Prop::num, g ),
393 // std::less<int>(),
394 // closed_plus<int>(),
395 // (std::numeric_limits<int>::max)(),
396 // 0,
397 // default_dijkstra_visitor() );
398 // for( int t = 0; t < 10; ++t )
399 // {
400 // i_vec_dijkstra_distances.push_back( d[t] );
401 // std::cout << "From " << s << " to " << t << ": " << d[t] << std::endl;
402 // }
403 //}
404
405 std::vector< int > i_vec_correct_solutions;
406 i_vec_correct_solutions.push_back(x: 0);
407 i_vec_correct_solutions.push_back(x: 22);
408 i_vec_correct_solutions.push_back(x: 27);
409 i_vec_correct_solutions.push_back(x: 1);
410 i_vec_correct_solutions.push_back(x: 6);
411 i_vec_correct_solutions.push_back(x: 44);
412 i_vec_correct_solutions.push_back(x: 7);
413 i_vec_correct_solutions.push_back(x: 27);
414 i_vec_correct_solutions.push_back(x: 50);
415 i_vec_correct_solutions.push_back(x: 25);
416 i_vec_correct_solutions.push_back(x: 37);
417 i_vec_correct_solutions.push_back(x: 0);
418 i_vec_correct_solutions.push_back(x: 29);
419 i_vec_correct_solutions.push_back(x: 38);
420 i_vec_correct_solutions.push_back(x: 43);
421 i_vec_correct_solutions.push_back(x: 81);
422 i_vec_correct_solutions.push_back(x: 7);
423 i_vec_correct_solutions.push_back(x: 27);
424 i_vec_correct_solutions.push_back(x: 76);
425 i_vec_correct_solutions.push_back(x: 28);
426 i_vec_correct_solutions.push_back(x: 25);
427 i_vec_correct_solutions.push_back(x: 21);
428 i_vec_correct_solutions.push_back(x: 0);
429 i_vec_correct_solutions.push_back(x: 13);
430 i_vec_correct_solutions.push_back(x: 18);
431 i_vec_correct_solutions.push_back(x: 56);
432 i_vec_correct_solutions.push_back(x: 6);
433 i_vec_correct_solutions.push_back(x: 26);
434 i_vec_correct_solutions.push_back(x: 47);
435 i_vec_correct_solutions.push_back(x: 27);
436 i_vec_correct_solutions.push_back(x: 12);
437 i_vec_correct_solutions.push_back(x: 21);
438 i_vec_correct_solutions.push_back(x: 26);
439 i_vec_correct_solutions.push_back(x: 0);
440 i_vec_correct_solutions.push_back(x: 5);
441 i_vec_correct_solutions.push_back(x: 43);
442 i_vec_correct_solutions.push_back(x: 6);
443 i_vec_correct_solutions.push_back(x: 26);
444 i_vec_correct_solutions.push_back(x: 49);
445 i_vec_correct_solutions.push_back(x: 24);
446 i_vec_correct_solutions.push_back(x: 7);
447 i_vec_correct_solutions.push_back(x: 29);
448 i_vec_correct_solutions.push_back(x: 34);
449 i_vec_correct_solutions.push_back(x: 8);
450 i_vec_correct_solutions.push_back(x: 0);
451 i_vec_correct_solutions.push_back(x: 38);
452 i_vec_correct_solutions.push_back(x: 14);
453 i_vec_correct_solutions.push_back(x: 34);
454 i_vec_correct_solutions.push_back(x: 44);
455 i_vec_correct_solutions.push_back(x: 32);
456 i_vec_correct_solutions.push_back(x: 29);
457 i_vec_correct_solutions.push_back(x: 19);
458 i_vec_correct_solutions.push_back(x: 26);
459 i_vec_correct_solutions.push_back(x: 17);
460 i_vec_correct_solutions.push_back(x: 22);
461 i_vec_correct_solutions.push_back(x: 0);
462 i_vec_correct_solutions.push_back(x: 23);
463 i_vec_correct_solutions.push_back(x: 43);
464 i_vec_correct_solutions.push_back(x: 6);
465 i_vec_correct_solutions.push_back(x: 41);
466 i_vec_correct_solutions.push_back(x: 43);
467 i_vec_correct_solutions.push_back(x: 15);
468 i_vec_correct_solutions.push_back(x: 22);
469 i_vec_correct_solutions.push_back(x: 35);
470 i_vec_correct_solutions.push_back(x: 40);
471 i_vec_correct_solutions.push_back(x: 78);
472 i_vec_correct_solutions.push_back(x: 0);
473 i_vec_correct_solutions.push_back(x: 20);
474 i_vec_correct_solutions.push_back(x: 69);
475 i_vec_correct_solutions.push_back(x: 21);
476 i_vec_correct_solutions.push_back(x: 23);
477 i_vec_correct_solutions.push_back(x: 23);
478 i_vec_correct_solutions.push_back(x: 2);
479 i_vec_correct_solutions.push_back(x: 15);
480 i_vec_correct_solutions.push_back(x: 20);
481 i_vec_correct_solutions.push_back(x: 58);
482 i_vec_correct_solutions.push_back(x: 8);
483 i_vec_correct_solutions.push_back(x: 0);
484 i_vec_correct_solutions.push_back(x: 49);
485 i_vec_correct_solutions.push_back(x: 1);
486 i_vec_correct_solutions.push_back(x: 23);
487 i_vec_correct_solutions.push_back(x: 13);
488 i_vec_correct_solutions.push_back(x: 37);
489 i_vec_correct_solutions.push_back(x: 11);
490 i_vec_correct_solutions.push_back(x: 16);
491 i_vec_correct_solutions.push_back(x: 36);
492 i_vec_correct_solutions.push_back(x: 17);
493 i_vec_correct_solutions.push_back(x: 37);
494 i_vec_correct_solutions.push_back(x: 0);
495 i_vec_correct_solutions.push_back(x: 35);
496 i_vec_correct_solutions.push_back(x: 41);
497 i_vec_correct_solutions.push_back(x: 44);
498 i_vec_correct_solutions.push_back(x: 68);
499 i_vec_correct_solutions.push_back(x: 42);
500 i_vec_correct_solutions.push_back(x: 47);
501 i_vec_correct_solutions.push_back(x: 85);
502 i_vec_correct_solutions.push_back(x: 48);
503 i_vec_correct_solutions.push_back(x: 68);
504 i_vec_correct_solutions.push_back(x: 91);
505 i_vec_correct_solutions.push_back(x: 0);
506 BOOST_TEST(
507 i_vec_opt_solutions_spp_no_rc.size() == i_vec_correct_solutions.size());
508 for (int i = 0; i < static_cast< int >(i_vec_correct_solutions.size()); ++i)
509 BOOST_TEST(
510 i_vec_opt_solutions_spp_no_rc[i] == i_vec_correct_solutions[i]);
511
512 // spptw
513 std::vector<
514 std::vector< graph_traits< SPPRC_Example_Graph >::edge_descriptor > >
515 opt_solutions_spptw;
516 std::vector< spp_spptw_res_cont > pareto_opt_rcs_spptw;
517 std::vector< std::vector< std::vector< std::vector<
518 graph_traits< SPPRC_Example_Graph >::edge_descriptor > > > >
519 vec_vec_vec_vec_opt_solutions_spptw(10);
520
521 for (int s = 0; s < 10; ++s)
522 {
523 for (int t = 0; t < 10; ++t)
524 {
525 r_c_shortest_paths(g, vertex_index_map: get(p: &SPPRC_Example_Graph_Vert_Prop::num, g),
526 edge_index_map: get(p: &SPPRC_Example_Graph_Arc_Prop::num, g), s, t,
527 pareto_optimal_solutions&: opt_solutions_spptw, pareto_optimal_resource_containers&: pareto_opt_rcs_spptw,
528 // be careful, do not simply take 0 as initial value for time
529 rc: spp_spptw_res_cont(0, g[s].eat), ref: ref_spptw(), dominance: dominance_spptw(),
530 la: std::allocator< r_c_shortest_paths_label< SPPRC_Example_Graph,
531 spp_spptw_res_cont > >(),
532 vis: default_r_c_shortest_paths_visitor());
533 vec_vec_vec_vec_opt_solutions_spptw[s].push_back(
534 x: opt_solutions_spptw);
535 if (opt_solutions_spptw.size())
536 {
537 bool b_is_a_path_at_all = false;
538 bool b_feasible = false;
539 bool b_correctly_extended = false;
540 spp_spptw_res_cont actual_final_resource_levels(0, 0);
541 graph_traits< SPPRC_Example_Graph >::edge_descriptor
542 ed_last_extended_arc;
543 check_r_c_path(g, ed_vec_path: opt_solutions_spptw[0],
544 initial_resource_levels: spp_spptw_res_cont(0, g[s].eat), b_result_must_be_equal_to_desired_final_resource_levels: true,
545 desired_final_resource_levels: pareto_opt_rcs_spptw[0], actual_final_resource_levels,
546 ref: ref_spptw(), b_is_a_path_at_all, b_feasible,
547 b_correctly_extended, ed_last_extended_arc);
548 BOOST_TEST(
549 b_is_a_path_at_all && b_feasible && b_correctly_extended);
550 b_is_a_path_at_all = false;
551 b_feasible = false;
552 b_correctly_extended = false;
553 spp_spptw_res_cont actual_final_resource_levels2(0, 0);
554 graph_traits< SPPRC_Example_Graph >::edge_descriptor
555 ed_last_extended_arc2;
556 check_r_c_path(g, ed_vec_path: opt_solutions_spptw[0],
557 initial_resource_levels: spp_spptw_res_cont(0, g[s].eat), b_result_must_be_equal_to_desired_final_resource_levels: false,
558 desired_final_resource_levels: pareto_opt_rcs_spptw[0], actual_final_resource_levels&: actual_final_resource_levels2,
559 ref: ref_spptw(), b_is_a_path_at_all, b_feasible,
560 b_correctly_extended, ed_last_extended_arc&: ed_last_extended_arc2);
561 BOOST_TEST(
562 b_is_a_path_at_all && b_feasible && b_correctly_extended);
563 }
564 }
565 }
566
567 std::vector< int > i_vec_correct_num_solutions_spptw;
568 i_vec_correct_num_solutions_spptw.push_back(x: 1);
569 i_vec_correct_num_solutions_spptw.push_back(x: 2);
570 i_vec_correct_num_solutions_spptw.push_back(x: 3);
571 i_vec_correct_num_solutions_spptw.push_back(x: 1);
572 i_vec_correct_num_solutions_spptw.push_back(x: 3);
573 i_vec_correct_num_solutions_spptw.push_back(x: 1);
574 i_vec_correct_num_solutions_spptw.push_back(x: 2);
575 i_vec_correct_num_solutions_spptw.push_back(x: 1);
576 i_vec_correct_num_solutions_spptw.push_back(x: 2);
577 i_vec_correct_num_solutions_spptw.push_back(x: 1);
578 i_vec_correct_num_solutions_spptw.push_back(x: 1);
579 i_vec_correct_num_solutions_spptw.push_back(x: 1);
580 i_vec_correct_num_solutions_spptw.push_back(x: 4);
581 i_vec_correct_num_solutions_spptw.push_back(x: 1);
582 i_vec_correct_num_solutions_spptw.push_back(x: 3);
583 i_vec_correct_num_solutions_spptw.push_back(x: 1);
584 i_vec_correct_num_solutions_spptw.push_back(x: 1);
585 i_vec_correct_num_solutions_spptw.push_back(x: 1);
586 i_vec_correct_num_solutions_spptw.push_back(x: 2);
587 i_vec_correct_num_solutions_spptw.push_back(x: 2);
588 i_vec_correct_num_solutions_spptw.push_back(x: 4);
589 i_vec_correct_num_solutions_spptw.push_back(x: 1);
590 i_vec_correct_num_solutions_spptw.push_back(x: 1);
591 i_vec_correct_num_solutions_spptw.push_back(x: 1);
592 i_vec_correct_num_solutions_spptw.push_back(x: 4);
593 i_vec_correct_num_solutions_spptw.push_back(x: 1);
594 i_vec_correct_num_solutions_spptw.push_back(x: 2);
595 i_vec_correct_num_solutions_spptw.push_back(x: 1);
596 i_vec_correct_num_solutions_spptw.push_back(x: 1);
597 i_vec_correct_num_solutions_spptw.push_back(x: 3);
598 i_vec_correct_num_solutions_spptw.push_back(x: 2);
599 i_vec_correct_num_solutions_spptw.push_back(x: 2);
600 i_vec_correct_num_solutions_spptw.push_back(x: 2);
601 i_vec_correct_num_solutions_spptw.push_back(x: 1);
602 i_vec_correct_num_solutions_spptw.push_back(x: 2);
603 i_vec_correct_num_solutions_spptw.push_back(x: 0);
604 i_vec_correct_num_solutions_spptw.push_back(x: 1);
605 i_vec_correct_num_solutions_spptw.push_back(x: 1);
606 i_vec_correct_num_solutions_spptw.push_back(x: 2);
607 i_vec_correct_num_solutions_spptw.push_back(x: 1);
608 i_vec_correct_num_solutions_spptw.push_back(x: 1);
609 i_vec_correct_num_solutions_spptw.push_back(x: 2);
610 i_vec_correct_num_solutions_spptw.push_back(x: 2);
611 i_vec_correct_num_solutions_spptw.push_back(x: 1);
612 i_vec_correct_num_solutions_spptw.push_back(x: 1);
613 i_vec_correct_num_solutions_spptw.push_back(x: 1);
614 i_vec_correct_num_solutions_spptw.push_back(x: 2);
615 i_vec_correct_num_solutions_spptw.push_back(x: 1);
616 i_vec_correct_num_solutions_spptw.push_back(x: 2);
617 i_vec_correct_num_solutions_spptw.push_back(x: 1);
618 i_vec_correct_num_solutions_spptw.push_back(x: 4);
619 i_vec_correct_num_solutions_spptw.push_back(x: 2);
620 i_vec_correct_num_solutions_spptw.push_back(x: 2);
621 i_vec_correct_num_solutions_spptw.push_back(x: 1);
622 i_vec_correct_num_solutions_spptw.push_back(x: 4);
623 i_vec_correct_num_solutions_spptw.push_back(x: 1);
624 i_vec_correct_num_solutions_spptw.push_back(x: 4);
625 i_vec_correct_num_solutions_spptw.push_back(x: 1);
626 i_vec_correct_num_solutions_spptw.push_back(x: 1);
627 i_vec_correct_num_solutions_spptw.push_back(x: 2);
628 i_vec_correct_num_solutions_spptw.push_back(x: 2);
629 i_vec_correct_num_solutions_spptw.push_back(x: 1);
630 i_vec_correct_num_solutions_spptw.push_back(x: 4);
631 i_vec_correct_num_solutions_spptw.push_back(x: 2);
632 i_vec_correct_num_solutions_spptw.push_back(x: 5);
633 i_vec_correct_num_solutions_spptw.push_back(x: 1);
634 i_vec_correct_num_solutions_spptw.push_back(x: 1);
635 i_vec_correct_num_solutions_spptw.push_back(x: 1);
636 i_vec_correct_num_solutions_spptw.push_back(x: 2);
637 i_vec_correct_num_solutions_spptw.push_back(x: 2);
638 i_vec_correct_num_solutions_spptw.push_back(x: 1);
639 i_vec_correct_num_solutions_spptw.push_back(x: 3);
640 i_vec_correct_num_solutions_spptw.push_back(x: 1);
641 i_vec_correct_num_solutions_spptw.push_back(x: 1);
642 i_vec_correct_num_solutions_spptw.push_back(x: 2);
643 i_vec_correct_num_solutions_spptw.push_back(x: 0);
644 i_vec_correct_num_solutions_spptw.push_back(x: 2);
645 i_vec_correct_num_solutions_spptw.push_back(x: 1);
646 i_vec_correct_num_solutions_spptw.push_back(x: 1);
647 i_vec_correct_num_solutions_spptw.push_back(x: 1);
648 i_vec_correct_num_solutions_spptw.push_back(x: 3);
649 i_vec_correct_num_solutions_spptw.push_back(x: 1);
650 i_vec_correct_num_solutions_spptw.push_back(x: 2);
651 i_vec_correct_num_solutions_spptw.push_back(x: 1);
652 i_vec_correct_num_solutions_spptw.push_back(x: 3);
653 i_vec_correct_num_solutions_spptw.push_back(x: 1);
654 i_vec_correct_num_solutions_spptw.push_back(x: 3);
655 i_vec_correct_num_solutions_spptw.push_back(x: 1);
656 i_vec_correct_num_solutions_spptw.push_back(x: 1);
657 i_vec_correct_num_solutions_spptw.push_back(x: 2);
658 i_vec_correct_num_solutions_spptw.push_back(x: 1);
659 i_vec_correct_num_solutions_spptw.push_back(x: 1);
660 i_vec_correct_num_solutions_spptw.push_back(x: 4);
661 i_vec_correct_num_solutions_spptw.push_back(x: 1);
662 i_vec_correct_num_solutions_spptw.push_back(x: 3);
663 i_vec_correct_num_solutions_spptw.push_back(x: 0);
664 i_vec_correct_num_solutions_spptw.push_back(x: 2);
665 i_vec_correct_num_solutions_spptw.push_back(x: 3);
666 i_vec_correct_num_solutions_spptw.push_back(x: 4);
667 i_vec_correct_num_solutions_spptw.push_back(x: 1);
668 for (int s = 0; s < 10; ++s)
669 for (int t = 0; t < 10; ++t)
670 BOOST_TEST(static_cast< int >(
671 vec_vec_vec_vec_opt_solutions_spptw[s][t].size())
672 == i_vec_correct_num_solutions_spptw[10 * s + t]);
673
674 // one pareto-optimal solution
675 SPPRC_Example_Graph g2;
676 add_vertex(p: SPPRC_Example_Graph_Vert_Prop(0, 0, 1000000000), g_&: g2);
677 add_vertex(p: SPPRC_Example_Graph_Vert_Prop(1, 0, 1000000000), g_&: g2);
678 add_vertex(p: SPPRC_Example_Graph_Vert_Prop(2, 0, 1000000000), g_&: g2);
679 add_vertex(p: SPPRC_Example_Graph_Vert_Prop(3, 0, 1000000000), g_&: g2);
680 add_edge(u: 0, v: 1, p: SPPRC_Example_Graph_Arc_Prop(0, 1, 1), g_&: g2);
681 add_edge(u: 0, v: 2, p: SPPRC_Example_Graph_Arc_Prop(1, 2, 1), g_&: g2);
682 add_edge(u: 1, v: 3, p: SPPRC_Example_Graph_Arc_Prop(2, 3, 1), g_&: g2);
683 add_edge(u: 2, v: 3, p: SPPRC_Example_Graph_Arc_Prop(3, 1, 1), g_&: g2);
684 std::vector< graph_traits< SPPRC_Example_Graph >::edge_descriptor >
685 opt_solution;
686 spp_spptw_res_cont pareto_opt_rc;
687 r_c_shortest_paths(g: g2, vertex_index_map: get(p: &SPPRC_Example_Graph_Vert_Prop::num, g&: g2),
688 edge_index_map: get(p: &SPPRC_Example_Graph_Arc_Prop::num, g&: g2), s: 0, t: 3, pareto_optimal_solution&: opt_solution,
689 pareto_optimal_resource_container&: pareto_opt_rc, rc: spp_spptw_res_cont(0, 0), ref: ref_spptw(), dominance: dominance_spptw(),
690 la: std::allocator< r_c_shortest_paths_label< SPPRC_Example_Graph,
691 spp_spptw_res_cont > >(),
692 vis: default_r_c_shortest_paths_visitor());
693
694 BOOST_TEST(pareto_opt_rc.cost == 3);
695
696 SPPRC_Example_Graph g3;
697 add_vertex(p: SPPRC_Example_Graph_Vert_Prop(0, 0, 1000), g_&: g3);
698 add_vertex(p: SPPRC_Example_Graph_Vert_Prop(1, 0, 1000), g_&: g3);
699 add_vertex(p: SPPRC_Example_Graph_Vert_Prop(2, 0, 974), g_&: g3);
700 add_vertex(p: SPPRC_Example_Graph_Vert_Prop(3, 0, 972), g_&: g3);
701 add_vertex(p: SPPRC_Example_Graph_Vert_Prop(4, 0, 967), g_&: g3);
702 add_vertex(p: SPPRC_Example_Graph_Vert_Prop(5, 678, 801), g_&: g3);
703 add_edge(u: 0, v: 2, p: SPPRC_Example_Graph_Arc_Prop(0, 0, 16), g_&: g3);
704 add_edge(u: 0, v: 3, p: SPPRC_Example_Graph_Arc_Prop(1, 0, 18), g_&: g3);
705 add_edge(u: 0, v: 4, p: SPPRC_Example_Graph_Arc_Prop(2, 0, 23), g_&: g3);
706 add_edge(u: 0, v: 5, p: SPPRC_Example_Graph_Arc_Prop(3, 0, 25), g_&: g3);
707 add_edge(u: 2, v: 3, p: SPPRC_Example_Graph_Arc_Prop(4, 0, 33), g_&: g3);
708 add_edge(u: 2, v: 4, p: SPPRC_Example_Graph_Arc_Prop(5, 0, 15), g_&: g3);
709 add_edge(u: 2, v: 5, p: SPPRC_Example_Graph_Arc_Prop(6, 0, 33), g_&: g3);
710 add_edge(u: 2, v: 1, p: SPPRC_Example_Graph_Arc_Prop(7, 0, 16), g_&: g3);
711 add_edge(u: 3, v: 2, p: SPPRC_Example_Graph_Arc_Prop(8, 0, 33), g_&: g3);
712 add_edge(u: 3, v: 4, p: SPPRC_Example_Graph_Arc_Prop(9, 0, 35), g_&: g3);
713 add_edge(u: 3, v: 5, p: SPPRC_Example_Graph_Arc_Prop(10, 0, 21), g_&: g3);
714 add_edge(u: 3, v: 1, p: SPPRC_Example_Graph_Arc_Prop(11, 0, 18), g_&: g3);
715 add_edge(u: 4, v: 2, p: SPPRC_Example_Graph_Arc_Prop(12, 0, 15), g_&: g3);
716 add_edge(u: 4, v: 3, p: SPPRC_Example_Graph_Arc_Prop(13, 0, 35), g_&: g3);
717 add_edge(u: 4, v: 5, p: SPPRC_Example_Graph_Arc_Prop(14, 0, 25), g_&: g3);
718 add_edge(u: 4, v: 1, p: SPPRC_Example_Graph_Arc_Prop(15, 0, 23), g_&: g3);
719 add_edge(u: 5, v: 2, p: SPPRC_Example_Graph_Arc_Prop(16, 0, 33), g_&: g3);
720 add_edge(u: 5, v: 3, p: SPPRC_Example_Graph_Arc_Prop(17, 0, 21), g_&: g3);
721 add_edge(u: 5, v: 4, p: SPPRC_Example_Graph_Arc_Prop(18, 0, 25), g_&: g3);
722 add_edge(u: 5, v: 1, p: SPPRC_Example_Graph_Arc_Prop(19, 0, 25), g_&: g3);
723
724 std::vector<
725 std::vector< graph_traits< SPPRC_Example_Graph >::edge_descriptor > >
726 pareto_opt_marked_solutions;
727 std::vector< spp_spptw_marked_res_cont >
728 pareto_opt_marked_resource_containers;
729
730 graph_traits< SPPRC_Example_Graph >::vertex_descriptor g3_source = 0,
731 g3_target = 1;
732 r_c_shortest_paths(g: g3, vertex_index_map: get(p: &SPPRC_Example_Graph_Vert_Prop::num, g&: g3),
733 edge_index_map: get(p: &SPPRC_Example_Graph_Arc_Prop::num, g&: g3), s: g3_source, t: g3_target,
734 pareto_optimal_solutions&: pareto_opt_marked_solutions, pareto_optimal_resource_containers&: pareto_opt_marked_resource_containers,
735 rc: spp_spptw_marked_res_cont(0, 0, 0), ref: ref_spptw_marked(),
736 dominance: dominance_spptw_marked(),
737 la: std::allocator< r_c_shortest_paths_label< SPPRC_Example_Graph,
738 spp_spptw_marked_res_cont > >(),
739 vis: default_r_c_shortest_paths_visitor());
740
741 BOOST_TEST(!pareto_opt_marked_solutions.empty());
742 std::vector< std::vector<
743 graph_traits< SPPRC_Example_Graph >::edge_descriptor > >::const_iterator
744 path_it,
745 path_end_it;
746 for (path_it = pareto_opt_marked_solutions.begin(),
747 path_end_it = pareto_opt_marked_solutions.end();
748 path_it != path_end_it; ++path_it)
749 {
750 const std::vector<
751 graph_traits< SPPRC_Example_Graph >::edge_descriptor >& path
752 = *path_it;
753 BOOST_TEST(!path.empty());
754
755 const graph_traits< SPPRC_Example_Graph >::edge_descriptor front
756 = path.front();
757 BOOST_TEST(boost::target(front, g3) == g3_target);
758
759 std::vector< graph_traits< SPPRC_Example_Graph >::edge_descriptor >::
760 const_iterator edge_it,
761 edge_it_end;
762 graph_traits< SPPRC_Example_Graph >::edge_descriptor prev_edge = front;
763
764 for (edge_it = path.begin() + 1, edge_it_end = path.end();
765 edge_it != edge_it_end; ++edge_it)
766 {
767 graph_traits< SPPRC_Example_Graph >::edge_descriptor edge
768 = *edge_it;
769
770 graph_traits< SPPRC_Example_Graph >::vertex_descriptor prev_end,
771 current_end;
772 prev_end = boost::source(e: prev_edge, g3);
773 current_end = boost::target(e: edge, g3);
774 BOOST_TEST(prev_end == current_end);
775
776 prev_edge = edge;
777 }
778
779 const graph_traits< SPPRC_Example_Graph >::edge_descriptor back
780 = path.back();
781 BOOST_TEST(boost::source(back, g3) == g3_source);
782 }
783
784 return boost::report_errors();
785}
786

source code of boost/libs/graph/test/r_c_shortest_paths_test.cpp