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
19 using namespace boost;
20
21 struct SPPRC_Example_Graph_Vert_Prop
22 {
SPPRC_Example_Graph_Vert_PropSPPRC_Example_Graph_Vert_Prop23 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
34 struct SPPRC_Example_Graph_Arc_Prop
35 {
SPPRC_Example_Graph_Arc_PropSPPRC_Example_Graph_Arc_Prop36 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
47 typedef 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
53 struct spp_no_rc_res_cont
54 {
spp_no_rc_res_contspp_no_rc_res_cont55 spp_no_rc_res_cont(int c = 0) : cost(c) {};
operator =spp_no_rc_res_cont56 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
operator ==(const spp_no_rc_res_cont & res_cont_1,const spp_no_rc_res_cont & res_cont_2)67 bool 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
operator <(const spp_no_rc_res_cont & res_cont_1,const spp_no_rc_res_cont & res_cont_2)73 bool 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
80 class ref_no_res_cont
81 {
82 public:
operator ()(const SPPRC_Example_Graph & g,spp_no_rc_res_cont & new_cont,const spp_no_rc_res_cont & old_cont,graph_traits<SPPRC_Example_Graph>::edge_descriptor ed) const83 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
93 class dominance_no_res_cont
94 {
95 public:
operator ()(const spp_no_rc_res_cont & res_cont_1,const spp_no_rc_res_cont & res_cont_2) const96 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
120 struct spp_spptw_res_cont
121 {
spp_spptw_res_contspp_spptw_res_cont122 spp_spptw_res_cont(int c = 0, int t = 0) : cost(c), time(t) {}
operator =spp_spptw_res_cont123 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
operator ==(const spp_spptw_res_cont & res_cont_1,const spp_spptw_res_cont & res_cont_2)135 bool 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
operator <(const spp_spptw_res_cont & res_cont_1,const spp_spptw_res_cont & res_cont_2)142 bool 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
153 class ref_spptw
154 {
155 public:
operator ()(const SPPRC_Example_Graph & g,spp_spptw_res_cont & new_cont,const spp_spptw_res_cont & old_cont,graph_traits<SPPRC_Example_Graph>::edge_descriptor ed) const156 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(edge_bundle, g)[ed];
161 const SPPRC_Example_Graph_Vert_Prop& vert_prop
162 = get(vertex_bundle, g)[target(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
172 class dominance_spptw
173 {
174 public:
operator ()(const spp_spptw_res_cont & res_cont_1,const spp_spptw_res_cont & res_cont_2) const175 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
198 struct spp_spptw_marked_res_cont
199 {
spp_spptw_marked_res_contspp_spptw_marked_res_cont200 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(v);
205 }
operator =spp_spptw_marked_res_cont206 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
operator ==(const spp_spptw_marked_res_cont & res_cont_1,const spp_spptw_marked_res_cont & res_cont_2)219 bool 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
operator <(const spp_spptw_marked_res_cont & res_cont_1,const spp_spptw_marked_res_cont & res_cont_2)227 bool 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(res_cont_2.marked.begin(), res_cont_2.marked.end(),
236 res_cont_1.marked.begin(), 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
248 class ref_spptw_marked
249 {
250 public:
operator ()(const SPPRC_Example_Graph & g,spp_spptw_marked_res_cont & new_cont,const spp_spptw_marked_res_cont & old_cont,graph_traits<SPPRC_Example_Graph>::edge_descriptor ed) const251 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(ed, g);
258
259 if (old_cont.marked.find(dest) != old_cont.marked.end())
260 {
261 return false;
262 }
263
264 const SPPRC_Example_Graph_Arc_Prop& arc_prop = get(edge_bundle, g)[ed];
265 const SPPRC_Example_Graph_Vert_Prop& vert_prop
266 = get(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(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
277 class dominance_spptw_marked
278 {
279 public:
operator ()(const spp_spptw_marked_res_cont & res_cont_1,const spp_spptw_marked_res_cont & res_cont_2) const280 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(res_cont_1.marked.begin(), res_cont_1.marked.end(),
286 res_cont_2.marked.begin(), res_cont_2.marked.end());
287 }
288 };
289
main(int,char * [])290 int main(int, char*[])
291 {
292 SPPRC_Example_Graph g;
293 add_vertex(SPPRC_Example_Graph_Vert_Prop(0, 0, 1000000000), g);
294 add_vertex(SPPRC_Example_Graph_Vert_Prop(1, 56, 142), g);
295 add_vertex(SPPRC_Example_Graph_Vert_Prop(2, 0, 1000000000), g);
296 add_vertex(SPPRC_Example_Graph_Vert_Prop(3, 89, 178), g);
297 add_vertex(SPPRC_Example_Graph_Vert_Prop(4, 0, 1000000000), g);
298 add_vertex(SPPRC_Example_Graph_Vert_Prop(5, 49, 76), g);
299 add_vertex(SPPRC_Example_Graph_Vert_Prop(6, 0, 1000000000), g);
300 add_vertex(SPPRC_Example_Graph_Vert_Prop(7, 98, 160), g);
301 add_vertex(SPPRC_Example_Graph_Vert_Prop(8, 0, 1000000000), g);
302 add_vertex(SPPRC_Example_Graph_Vert_Prop(9, 90, 158), g);
303 add_edge(0, 7, SPPRC_Example_Graph_Arc_Prop(6, 33, 2), g);
304 add_edge(0, 6, SPPRC_Example_Graph_Arc_Prop(5, 31, 6), g);
305 add_edge(0, 4, SPPRC_Example_Graph_Arc_Prop(3, 14, 4), g);
306 add_edge(0, 1, SPPRC_Example_Graph_Arc_Prop(0, 43, 8), g);
307 add_edge(0, 4, SPPRC_Example_Graph_Arc_Prop(4, 28, 10), g);
308 add_edge(0, 3, SPPRC_Example_Graph_Arc_Prop(1, 31, 10), g);
309 add_edge(0, 3, SPPRC_Example_Graph_Arc_Prop(2, 1, 7), g);
310 add_edge(0, 9, SPPRC_Example_Graph_Arc_Prop(7, 25, 9), g);
311 add_edge(1, 0, SPPRC_Example_Graph_Arc_Prop(8, 37, 4), g);
312 add_edge(1, 6, SPPRC_Example_Graph_Arc_Prop(9, 7, 3), g);
313 add_edge(2, 6, SPPRC_Example_Graph_Arc_Prop(12, 6, 7), g);
314 add_edge(2, 3, SPPRC_Example_Graph_Arc_Prop(10, 13, 7), g);
315 add_edge(2, 3, SPPRC_Example_Graph_Arc_Prop(11, 49, 9), g);
316 add_edge(2, 8, SPPRC_Example_Graph_Arc_Prop(13, 47, 5), g);
317 add_edge(3, 4, SPPRC_Example_Graph_Arc_Prop(17, 5, 10), g);
318 add_edge(3, 1, SPPRC_Example_Graph_Arc_Prop(15, 47, 1), g);
319 add_edge(3, 2, SPPRC_Example_Graph_Arc_Prop(16, 26, 9), g);
320 add_edge(3, 9, SPPRC_Example_Graph_Arc_Prop(21, 24, 10), g);
321 add_edge(3, 7, SPPRC_Example_Graph_Arc_Prop(20, 50, 10), g);
322 add_edge(3, 0, SPPRC_Example_Graph_Arc_Prop(14, 41, 4), g);
323 add_edge(3, 6, SPPRC_Example_Graph_Arc_Prop(19, 6, 1), g);
324 add_edge(3, 4, SPPRC_Example_Graph_Arc_Prop(18, 8, 1), g);
325 add_edge(4, 5, SPPRC_Example_Graph_Arc_Prop(26, 38, 4), g);
326 add_edge(4, 9, SPPRC_Example_Graph_Arc_Prop(27, 32, 10), g);
327 add_edge(4, 3, SPPRC_Example_Graph_Arc_Prop(24, 40, 3), g);
328 add_edge(4, 0, SPPRC_Example_Graph_Arc_Prop(22, 7, 3), g);
329 add_edge(4, 3, SPPRC_Example_Graph_Arc_Prop(25, 28, 9), g);
330 add_edge(4, 2, SPPRC_Example_Graph_Arc_Prop(23, 39, 6), g);
331 add_edge(5, 8, SPPRC_Example_Graph_Arc_Prop(32, 6, 2), g);
332 add_edge(5, 2, SPPRC_Example_Graph_Arc_Prop(30, 26, 10), g);
333 add_edge(5, 0, SPPRC_Example_Graph_Arc_Prop(28, 38, 9), g);
334 add_edge(5, 2, SPPRC_Example_Graph_Arc_Prop(31, 48, 10), g);
335 add_edge(5, 9, SPPRC_Example_Graph_Arc_Prop(33, 49, 2), g);
336 add_edge(5, 1, SPPRC_Example_Graph_Arc_Prop(29, 22, 7), g);
337 add_edge(6, 1, SPPRC_Example_Graph_Arc_Prop(34, 15, 7), g);
338 add_edge(6, 7, SPPRC_Example_Graph_Arc_Prop(35, 20, 3), g);
339 add_edge(7, 9, SPPRC_Example_Graph_Arc_Prop(40, 1, 3), g);
340 add_edge(7, 0, SPPRC_Example_Graph_Arc_Prop(36, 23, 5), g);
341 add_edge(7, 6, SPPRC_Example_Graph_Arc_Prop(38, 36, 2), g);
342 add_edge(7, 6, SPPRC_Example_Graph_Arc_Prop(39, 18, 10), g);
343 add_edge(7, 2, SPPRC_Example_Graph_Arc_Prop(37, 2, 1), g);
344 add_edge(8, 5, SPPRC_Example_Graph_Arc_Prop(46, 36, 5), g);
345 add_edge(8, 1, SPPRC_Example_Graph_Arc_Prop(42, 13, 10), g);
346 add_edge(8, 0, SPPRC_Example_Graph_Arc_Prop(41, 40, 5), g);
347 add_edge(8, 1, SPPRC_Example_Graph_Arc_Prop(43, 32, 8), g);
348 add_edge(8, 6, SPPRC_Example_Graph_Arc_Prop(47, 25, 1), g);
349 add_edge(8, 2, SPPRC_Example_Graph_Arc_Prop(44, 44, 3), g);
350 add_edge(8, 3, SPPRC_Example_Graph_Arc_Prop(45, 11, 9), g);
351 add_edge(9, 0, SPPRC_Example_Graph_Arc_Prop(48, 41, 5), g);
352 add_edge(9, 1, SPPRC_Example_Graph_Arc_Prop(49, 44, 7), 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, get(&SPPRC_Example_Graph_Vert_Prop::num, g),
367 get(&SPPRC_Example_Graph_Arc_Prop::num, g), s, t, opt_solutions,
368 pareto_opt_rcs_no_rc, spp_no_rc_res_cont(0), ref_no_res_cont(),
369 dominance_no_res_cont(),
370 std::allocator< r_c_shortest_paths_label< SPPRC_Example_Graph,
371 spp_no_rc_res_cont > >(),
372 default_r_c_shortest_paths_visitor());
373 i_vec_opt_solutions_spp_no_rc.push_back(
374 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(0);
407 i_vec_correct_solutions.push_back(22);
408 i_vec_correct_solutions.push_back(27);
409 i_vec_correct_solutions.push_back(1);
410 i_vec_correct_solutions.push_back(6);
411 i_vec_correct_solutions.push_back(44);
412 i_vec_correct_solutions.push_back(7);
413 i_vec_correct_solutions.push_back(27);
414 i_vec_correct_solutions.push_back(50);
415 i_vec_correct_solutions.push_back(25);
416 i_vec_correct_solutions.push_back(37);
417 i_vec_correct_solutions.push_back(0);
418 i_vec_correct_solutions.push_back(29);
419 i_vec_correct_solutions.push_back(38);
420 i_vec_correct_solutions.push_back(43);
421 i_vec_correct_solutions.push_back(81);
422 i_vec_correct_solutions.push_back(7);
423 i_vec_correct_solutions.push_back(27);
424 i_vec_correct_solutions.push_back(76);
425 i_vec_correct_solutions.push_back(28);
426 i_vec_correct_solutions.push_back(25);
427 i_vec_correct_solutions.push_back(21);
428 i_vec_correct_solutions.push_back(0);
429 i_vec_correct_solutions.push_back(13);
430 i_vec_correct_solutions.push_back(18);
431 i_vec_correct_solutions.push_back(56);
432 i_vec_correct_solutions.push_back(6);
433 i_vec_correct_solutions.push_back(26);
434 i_vec_correct_solutions.push_back(47);
435 i_vec_correct_solutions.push_back(27);
436 i_vec_correct_solutions.push_back(12);
437 i_vec_correct_solutions.push_back(21);
438 i_vec_correct_solutions.push_back(26);
439 i_vec_correct_solutions.push_back(0);
440 i_vec_correct_solutions.push_back(5);
441 i_vec_correct_solutions.push_back(43);
442 i_vec_correct_solutions.push_back(6);
443 i_vec_correct_solutions.push_back(26);
444 i_vec_correct_solutions.push_back(49);
445 i_vec_correct_solutions.push_back(24);
446 i_vec_correct_solutions.push_back(7);
447 i_vec_correct_solutions.push_back(29);
448 i_vec_correct_solutions.push_back(34);
449 i_vec_correct_solutions.push_back(8);
450 i_vec_correct_solutions.push_back(0);
451 i_vec_correct_solutions.push_back(38);
452 i_vec_correct_solutions.push_back(14);
453 i_vec_correct_solutions.push_back(34);
454 i_vec_correct_solutions.push_back(44);
455 i_vec_correct_solutions.push_back(32);
456 i_vec_correct_solutions.push_back(29);
457 i_vec_correct_solutions.push_back(19);
458 i_vec_correct_solutions.push_back(26);
459 i_vec_correct_solutions.push_back(17);
460 i_vec_correct_solutions.push_back(22);
461 i_vec_correct_solutions.push_back(0);
462 i_vec_correct_solutions.push_back(23);
463 i_vec_correct_solutions.push_back(43);
464 i_vec_correct_solutions.push_back(6);
465 i_vec_correct_solutions.push_back(41);
466 i_vec_correct_solutions.push_back(43);
467 i_vec_correct_solutions.push_back(15);
468 i_vec_correct_solutions.push_back(22);
469 i_vec_correct_solutions.push_back(35);
470 i_vec_correct_solutions.push_back(40);
471 i_vec_correct_solutions.push_back(78);
472 i_vec_correct_solutions.push_back(0);
473 i_vec_correct_solutions.push_back(20);
474 i_vec_correct_solutions.push_back(69);
475 i_vec_correct_solutions.push_back(21);
476 i_vec_correct_solutions.push_back(23);
477 i_vec_correct_solutions.push_back(23);
478 i_vec_correct_solutions.push_back(2);
479 i_vec_correct_solutions.push_back(15);
480 i_vec_correct_solutions.push_back(20);
481 i_vec_correct_solutions.push_back(58);
482 i_vec_correct_solutions.push_back(8);
483 i_vec_correct_solutions.push_back(0);
484 i_vec_correct_solutions.push_back(49);
485 i_vec_correct_solutions.push_back(1);
486 i_vec_correct_solutions.push_back(23);
487 i_vec_correct_solutions.push_back(13);
488 i_vec_correct_solutions.push_back(37);
489 i_vec_correct_solutions.push_back(11);
490 i_vec_correct_solutions.push_back(16);
491 i_vec_correct_solutions.push_back(36);
492 i_vec_correct_solutions.push_back(17);
493 i_vec_correct_solutions.push_back(37);
494 i_vec_correct_solutions.push_back(0);
495 i_vec_correct_solutions.push_back(35);
496 i_vec_correct_solutions.push_back(41);
497 i_vec_correct_solutions.push_back(44);
498 i_vec_correct_solutions.push_back(68);
499 i_vec_correct_solutions.push_back(42);
500 i_vec_correct_solutions.push_back(47);
501 i_vec_correct_solutions.push_back(85);
502 i_vec_correct_solutions.push_back(48);
503 i_vec_correct_solutions.push_back(68);
504 i_vec_correct_solutions.push_back(91);
505 i_vec_correct_solutions.push_back(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, get(&SPPRC_Example_Graph_Vert_Prop::num, g),
526 get(&SPPRC_Example_Graph_Arc_Prop::num, g), s, t,
527 opt_solutions_spptw, pareto_opt_rcs_spptw,
528 // be careful, do not simply take 0 as initial value for time
529 spp_spptw_res_cont(0, g[s].eat), ref_spptw(), dominance_spptw(),
530 std::allocator< r_c_shortest_paths_label< SPPRC_Example_Graph,
531 spp_spptw_res_cont > >(),
532 default_r_c_shortest_paths_visitor());
533 vec_vec_vec_vec_opt_solutions_spptw[s].push_back(
534 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, opt_solutions_spptw[0],
544 spp_spptw_res_cont(0, g[s].eat), true,
545 pareto_opt_rcs_spptw[0], actual_final_resource_levels,
546 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, opt_solutions_spptw[0],
557 spp_spptw_res_cont(0, g[s].eat), false,
558 pareto_opt_rcs_spptw[0], actual_final_resource_levels2,
559 ref_spptw(), b_is_a_path_at_all, b_feasible,
560 b_correctly_extended, 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(1);
569 i_vec_correct_num_solutions_spptw.push_back(2);
570 i_vec_correct_num_solutions_spptw.push_back(3);
571 i_vec_correct_num_solutions_spptw.push_back(1);
572 i_vec_correct_num_solutions_spptw.push_back(3);
573 i_vec_correct_num_solutions_spptw.push_back(1);
574 i_vec_correct_num_solutions_spptw.push_back(2);
575 i_vec_correct_num_solutions_spptw.push_back(1);
576 i_vec_correct_num_solutions_spptw.push_back(2);
577 i_vec_correct_num_solutions_spptw.push_back(1);
578 i_vec_correct_num_solutions_spptw.push_back(1);
579 i_vec_correct_num_solutions_spptw.push_back(1);
580 i_vec_correct_num_solutions_spptw.push_back(4);
581 i_vec_correct_num_solutions_spptw.push_back(1);
582 i_vec_correct_num_solutions_spptw.push_back(3);
583 i_vec_correct_num_solutions_spptw.push_back(1);
584 i_vec_correct_num_solutions_spptw.push_back(1);
585 i_vec_correct_num_solutions_spptw.push_back(1);
586 i_vec_correct_num_solutions_spptw.push_back(2);
587 i_vec_correct_num_solutions_spptw.push_back(2);
588 i_vec_correct_num_solutions_spptw.push_back(4);
589 i_vec_correct_num_solutions_spptw.push_back(1);
590 i_vec_correct_num_solutions_spptw.push_back(1);
591 i_vec_correct_num_solutions_spptw.push_back(1);
592 i_vec_correct_num_solutions_spptw.push_back(4);
593 i_vec_correct_num_solutions_spptw.push_back(1);
594 i_vec_correct_num_solutions_spptw.push_back(2);
595 i_vec_correct_num_solutions_spptw.push_back(1);
596 i_vec_correct_num_solutions_spptw.push_back(1);
597 i_vec_correct_num_solutions_spptw.push_back(3);
598 i_vec_correct_num_solutions_spptw.push_back(2);
599 i_vec_correct_num_solutions_spptw.push_back(2);
600 i_vec_correct_num_solutions_spptw.push_back(2);
601 i_vec_correct_num_solutions_spptw.push_back(1);
602 i_vec_correct_num_solutions_spptw.push_back(2);
603 i_vec_correct_num_solutions_spptw.push_back(0);
604 i_vec_correct_num_solutions_spptw.push_back(1);
605 i_vec_correct_num_solutions_spptw.push_back(1);
606 i_vec_correct_num_solutions_spptw.push_back(2);
607 i_vec_correct_num_solutions_spptw.push_back(1);
608 i_vec_correct_num_solutions_spptw.push_back(1);
609 i_vec_correct_num_solutions_spptw.push_back(2);
610 i_vec_correct_num_solutions_spptw.push_back(2);
611 i_vec_correct_num_solutions_spptw.push_back(1);
612 i_vec_correct_num_solutions_spptw.push_back(1);
613 i_vec_correct_num_solutions_spptw.push_back(1);
614 i_vec_correct_num_solutions_spptw.push_back(2);
615 i_vec_correct_num_solutions_spptw.push_back(1);
616 i_vec_correct_num_solutions_spptw.push_back(2);
617 i_vec_correct_num_solutions_spptw.push_back(1);
618 i_vec_correct_num_solutions_spptw.push_back(4);
619 i_vec_correct_num_solutions_spptw.push_back(2);
620 i_vec_correct_num_solutions_spptw.push_back(2);
621 i_vec_correct_num_solutions_spptw.push_back(1);
622 i_vec_correct_num_solutions_spptw.push_back(4);
623 i_vec_correct_num_solutions_spptw.push_back(1);
624 i_vec_correct_num_solutions_spptw.push_back(4);
625 i_vec_correct_num_solutions_spptw.push_back(1);
626 i_vec_correct_num_solutions_spptw.push_back(1);
627 i_vec_correct_num_solutions_spptw.push_back(2);
628 i_vec_correct_num_solutions_spptw.push_back(2);
629 i_vec_correct_num_solutions_spptw.push_back(1);
630 i_vec_correct_num_solutions_spptw.push_back(4);
631 i_vec_correct_num_solutions_spptw.push_back(2);
632 i_vec_correct_num_solutions_spptw.push_back(5);
633 i_vec_correct_num_solutions_spptw.push_back(1);
634 i_vec_correct_num_solutions_spptw.push_back(1);
635 i_vec_correct_num_solutions_spptw.push_back(1);
636 i_vec_correct_num_solutions_spptw.push_back(2);
637 i_vec_correct_num_solutions_spptw.push_back(2);
638 i_vec_correct_num_solutions_spptw.push_back(1);
639 i_vec_correct_num_solutions_spptw.push_back(3);
640 i_vec_correct_num_solutions_spptw.push_back(1);
641 i_vec_correct_num_solutions_spptw.push_back(1);
642 i_vec_correct_num_solutions_spptw.push_back(2);
643 i_vec_correct_num_solutions_spptw.push_back(0);
644 i_vec_correct_num_solutions_spptw.push_back(2);
645 i_vec_correct_num_solutions_spptw.push_back(1);
646 i_vec_correct_num_solutions_spptw.push_back(1);
647 i_vec_correct_num_solutions_spptw.push_back(1);
648 i_vec_correct_num_solutions_spptw.push_back(3);
649 i_vec_correct_num_solutions_spptw.push_back(1);
650 i_vec_correct_num_solutions_spptw.push_back(2);
651 i_vec_correct_num_solutions_spptw.push_back(1);
652 i_vec_correct_num_solutions_spptw.push_back(3);
653 i_vec_correct_num_solutions_spptw.push_back(1);
654 i_vec_correct_num_solutions_spptw.push_back(3);
655 i_vec_correct_num_solutions_spptw.push_back(1);
656 i_vec_correct_num_solutions_spptw.push_back(1);
657 i_vec_correct_num_solutions_spptw.push_back(2);
658 i_vec_correct_num_solutions_spptw.push_back(1);
659 i_vec_correct_num_solutions_spptw.push_back(1);
660 i_vec_correct_num_solutions_spptw.push_back(4);
661 i_vec_correct_num_solutions_spptw.push_back(1);
662 i_vec_correct_num_solutions_spptw.push_back(3);
663 i_vec_correct_num_solutions_spptw.push_back(0);
664 i_vec_correct_num_solutions_spptw.push_back(2);
665 i_vec_correct_num_solutions_spptw.push_back(3);
666 i_vec_correct_num_solutions_spptw.push_back(4);
667 i_vec_correct_num_solutions_spptw.push_back(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(SPPRC_Example_Graph_Vert_Prop(0, 0, 1000000000), g2);
677 add_vertex(SPPRC_Example_Graph_Vert_Prop(1, 0, 1000000000), g2);
678 add_vertex(SPPRC_Example_Graph_Vert_Prop(2, 0, 1000000000), g2);
679 add_vertex(SPPRC_Example_Graph_Vert_Prop(3, 0, 1000000000), g2);
680 add_edge(0, 1, SPPRC_Example_Graph_Arc_Prop(0, 1, 1), g2);
681 add_edge(0, 2, SPPRC_Example_Graph_Arc_Prop(1, 2, 1), g2);
682 add_edge(1, 3, SPPRC_Example_Graph_Arc_Prop(2, 3, 1), g2);
683 add_edge(2, 3, SPPRC_Example_Graph_Arc_Prop(3, 1, 1), 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(g2, get(&SPPRC_Example_Graph_Vert_Prop::num, g2),
688 get(&SPPRC_Example_Graph_Arc_Prop::num, g2), 0, 3, opt_solution,
689 pareto_opt_rc, spp_spptw_res_cont(0, 0), ref_spptw(), dominance_spptw(),
690 std::allocator< r_c_shortest_paths_label< SPPRC_Example_Graph,
691 spp_spptw_res_cont > >(),
692 default_r_c_shortest_paths_visitor());
693
694 BOOST_TEST(pareto_opt_rc.cost == 3);
695
696 SPPRC_Example_Graph g3;
697 add_vertex(SPPRC_Example_Graph_Vert_Prop(0, 0, 1000), g3);
698 add_vertex(SPPRC_Example_Graph_Vert_Prop(1, 0, 1000), g3);
699 add_vertex(SPPRC_Example_Graph_Vert_Prop(2, 0, 974), g3);
700 add_vertex(SPPRC_Example_Graph_Vert_Prop(3, 0, 972), g3);
701 add_vertex(SPPRC_Example_Graph_Vert_Prop(4, 0, 967), g3);
702 add_vertex(SPPRC_Example_Graph_Vert_Prop(5, 678, 801), g3);
703 add_edge(0, 2, SPPRC_Example_Graph_Arc_Prop(0, 0, 16), g3);
704 add_edge(0, 3, SPPRC_Example_Graph_Arc_Prop(1, 0, 18), g3);
705 add_edge(0, 4, SPPRC_Example_Graph_Arc_Prop(2, 0, 23), g3);
706 add_edge(0, 5, SPPRC_Example_Graph_Arc_Prop(3, 0, 25), g3);
707 add_edge(2, 3, SPPRC_Example_Graph_Arc_Prop(4, 0, 33), g3);
708 add_edge(2, 4, SPPRC_Example_Graph_Arc_Prop(5, 0, 15), g3);
709 add_edge(2, 5, SPPRC_Example_Graph_Arc_Prop(6, 0, 33), g3);
710 add_edge(2, 1, SPPRC_Example_Graph_Arc_Prop(7, 0, 16), g3);
711 add_edge(3, 2, SPPRC_Example_Graph_Arc_Prop(8, 0, 33), g3);
712 add_edge(3, 4, SPPRC_Example_Graph_Arc_Prop(9, 0, 35), g3);
713 add_edge(3, 5, SPPRC_Example_Graph_Arc_Prop(10, 0, 21), g3);
714 add_edge(3, 1, SPPRC_Example_Graph_Arc_Prop(11, 0, 18), g3);
715 add_edge(4, 2, SPPRC_Example_Graph_Arc_Prop(12, 0, 15), g3);
716 add_edge(4, 3, SPPRC_Example_Graph_Arc_Prop(13, 0, 35), g3);
717 add_edge(4, 5, SPPRC_Example_Graph_Arc_Prop(14, 0, 25), g3);
718 add_edge(4, 1, SPPRC_Example_Graph_Arc_Prop(15, 0, 23), g3);
719 add_edge(5, 2, SPPRC_Example_Graph_Arc_Prop(16, 0, 33), g3);
720 add_edge(5, 3, SPPRC_Example_Graph_Arc_Prop(17, 0, 21), g3);
721 add_edge(5, 4, SPPRC_Example_Graph_Arc_Prop(18, 0, 25), g3);
722 add_edge(5, 1, SPPRC_Example_Graph_Arc_Prop(19, 0, 25), 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(g3, get(&SPPRC_Example_Graph_Vert_Prop::num, g3),
733 get(&SPPRC_Example_Graph_Arc_Prop::num, g3), g3_source, g3_target,
734 pareto_opt_marked_solutions, pareto_opt_marked_resource_containers,
735 spp_spptw_marked_res_cont(0, 0, 0), ref_spptw_marked(),
736 dominance_spptw_marked(),
737 std::allocator< r_c_shortest_paths_label< SPPRC_Example_Graph,
738 spp_spptw_marked_res_cont > >(),
739 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(prev_edge, g3);
773 current_end = boost::target(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