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/test/minimal.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 int num;
26 // earliest arrival time
27 int eat;
28 // latest arrival time
29 int lat;
30 };
31
32 struct SPPRC_Example_Graph_Arc_Prop
33 {
SPPRC_Example_Graph_Arc_PropSPPRC_Example_Graph_Arc_Prop34 SPPRC_Example_Graph_Arc_Prop( int n = 0, int c = 0, int t = 0 )
35 : num( n ), cost( c ), time( t ) {}
36 int num;
37 // traversal cost
38 int cost;
39 // traversal time
40 int time;
41 };
42
43 typedef adjacency_list<vecS,
44 vecS,
45 directedS,
46 SPPRC_Example_Graph_Vert_Prop,
47 SPPRC_Example_Graph_Arc_Prop>
48 SPPRC_Example_Graph;
49
50 // data structures for spp without resource constraints:
51 // ResourceContainer model
52 struct spp_no_rc_res_cont
53 {
spp_no_rc_res_contspp_no_rc_res_cont54 spp_no_rc_res_cont( int c = 0 ) : cost( c ) {};
operator =spp_no_rc_res_cont55 spp_no_rc_res_cont& operator=( const spp_no_rc_res_cont& other )
56 {
57 if( this == &other )
58 return *this;
59 this->~spp_no_rc_res_cont();
60 new( this ) spp_no_rc_res_cont( other );
61 return *this;
62 }
63 int cost;
64 };
65
operator ==(const spp_no_rc_res_cont & res_cont_1,const spp_no_rc_res_cont & res_cont_2)66 bool operator==( const spp_no_rc_res_cont& res_cont_1,
67 const spp_no_rc_res_cont& res_cont_2 )
68 {
69 return ( res_cont_1.cost == res_cont_2.cost );
70 }
71
operator <(const spp_no_rc_res_cont & res_cont_1,const spp_no_rc_res_cont & res_cont_2)72 bool operator<( const spp_no_rc_res_cont& res_cont_1,
73 const spp_no_rc_res_cont& res_cont_2 )
74 {
75 return ( res_cont_1.cost < res_cont_2.cost );
76 }
77
78 // ResourceExtensionFunction model
79 class ref_no_res_cont
80 {
81 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) const82 inline bool operator()( const SPPRC_Example_Graph& g,
83 spp_no_rc_res_cont& new_cont,
84 const spp_no_rc_res_cont& old_cont,
85 graph_traits
86 <SPPRC_Example_Graph>::edge_descriptor ed ) const
87 {
88 new_cont.cost = old_cont.cost + g[ed].cost;
89 return true;
90 }
91 };
92
93 // DominanceFunction model
94 class dominance_no_res_cont
95 {
96 public:
operator ()(const spp_no_rc_res_cont & res_cont_1,const spp_no_rc_res_cont & res_cont_2) const97 inline bool operator()( const spp_no_rc_res_cont& res_cont_1,
98 const spp_no_rc_res_cont& res_cont_2 ) const
99 {
100 // must be "<=" here!!!
101 // must NOT be "<"!!!
102 return res_cont_1.cost <= res_cont_2.cost;
103 // this is not a contradiction to the documentation
104 // the documentation says:
105 // "A label $l_1$ dominates a label $l_2$ if and only if both are resident
106 // at the same vertex, and if, for each resource, the resource consumption
107 // of $l_1$ is less than or equal to the resource consumption of $l_2$,
108 // and if there is at least one resource where $l_1$ has a lower resource
109 // consumption than $l_2$."
110 // one can think of a new label with a resource consumption equal to that
111 // of an old label as being dominated by that old label, because the new
112 // one will have a higher number and is created at a later point in time,
113 // so one can implicitly use the number or the creation time as a resource
114 // for tie-breaking
115 }
116 };
117 // end data structures for spp without resource constraints:
118
119 // data structures for shortest path problem with time windows (spptw)
120 // ResourceContainer model
121 struct spp_spptw_res_cont
122 {
spp_spptw_res_contspp_spptw_res_cont123 spp_spptw_res_cont( int c = 0, int t = 0 ) : cost( c ), time( t ) {}
operator =spp_spptw_res_cont124 spp_spptw_res_cont& operator=( const spp_spptw_res_cont& other )
125 {
126 if( this == &other )
127 return *this;
128 this->~spp_spptw_res_cont();
129 new( this ) spp_spptw_res_cont( other );
130 return *this;
131 }
132 int cost;
133 int time;
134 };
135
operator ==(const spp_spptw_res_cont & res_cont_1,const spp_spptw_res_cont & res_cont_2)136 bool operator==( const spp_spptw_res_cont& res_cont_1,
137 const spp_spptw_res_cont& res_cont_2 )
138 {
139 return ( res_cont_1.cost == res_cont_2.cost
140 && res_cont_1.time == res_cont_2.time );
141 }
142
operator <(const spp_spptw_res_cont & res_cont_1,const spp_spptw_res_cont & res_cont_2)143 bool operator<( const spp_spptw_res_cont& res_cont_1,
144 const spp_spptw_res_cont& res_cont_2 )
145 {
146 if( res_cont_1.cost > res_cont_2.cost )
147 return false;
148 if( res_cont_1.cost == res_cont_2.cost )
149 return res_cont_1.time < res_cont_2.time;
150 return true;
151 }
152
153 // ResourceExtensionFunction model
154 class ref_spptw
155 {
156 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) const157 inline bool operator()( const SPPRC_Example_Graph& g,
158 spp_spptw_res_cont& new_cont,
159 const spp_spptw_res_cont& old_cont,
160 graph_traits
161 <SPPRC_Example_Graph>::edge_descriptor ed ) const
162 {
163 const SPPRC_Example_Graph_Arc_Prop& arc_prop =
164 get( edge_bundle, g )[ed];
165 const SPPRC_Example_Graph_Vert_Prop& vert_prop =
166 get( vertex_bundle, g )[target( ed, g )];
167 new_cont.cost = old_cont.cost + arc_prop.cost;
168 int& i_time = new_cont.time;
169 i_time = old_cont.time + arc_prop.time;
170 i_time < vert_prop.eat ? i_time = vert_prop.eat : 0;
171 return i_time <= vert_prop.lat ? true : false;
172 }
173 };
174
175 // DominanceFunction model
176 class dominance_spptw
177 {
178 public:
operator ()(const spp_spptw_res_cont & res_cont_1,const spp_spptw_res_cont & res_cont_2) const179 inline bool operator()( const spp_spptw_res_cont& res_cont_1,
180 const spp_spptw_res_cont& res_cont_2 ) const
181 {
182 // must be "<=" here!!!
183 // must NOT be "<"!!!
184 return res_cont_1.cost <= res_cont_2.cost
185 && res_cont_1.time <= res_cont_2.time;
186 // this is not a contradiction to the documentation
187 // the documentation says:
188 // "A label $l_1$ dominates a label $l_2$ if and only if both are resident
189 // at the same vertex, and if, for each resource, the resource consumption
190 // of $l_1$ is less than or equal to the resource consumption of $l_2$,
191 // and if there is at least one resource where $l_1$ has a lower resource
192 // consumption than $l_2$."
193 // one can think of a new label with a resource consumption equal to that
194 // of an old label as being dominated by that old label, because the new
195 // one will have a higher number and is created at a later point in time,
196 // so one can implicitly use the number or the creation time as a resource
197 // for tie-breaking
198 }
199 };
200 // end data structures for shortest path problem with time windows (spptw)
201
test_main(int,char * [])202 int test_main(int, char*[])
203 {
204 SPPRC_Example_Graph g;
205 add_vertex( SPPRC_Example_Graph_Vert_Prop( 0, 0, 1000000000 ), g );
206 add_vertex( SPPRC_Example_Graph_Vert_Prop( 1, 56, 142 ), g );
207 add_vertex( SPPRC_Example_Graph_Vert_Prop( 2, 0, 1000000000 ), g );
208 add_vertex( SPPRC_Example_Graph_Vert_Prop( 3, 89, 178 ), g );
209 add_vertex( SPPRC_Example_Graph_Vert_Prop( 4, 0, 1000000000 ), g );
210 add_vertex( SPPRC_Example_Graph_Vert_Prop( 5, 49, 76 ), g );
211 add_vertex( SPPRC_Example_Graph_Vert_Prop( 6, 0, 1000000000 ), g );
212 add_vertex( SPPRC_Example_Graph_Vert_Prop( 7, 98, 160 ), g );
213 add_vertex( SPPRC_Example_Graph_Vert_Prop( 8, 0, 1000000000 ), g );
214 add_vertex( SPPRC_Example_Graph_Vert_Prop( 9, 90, 158 ), g );
215 add_edge( 0, 7, SPPRC_Example_Graph_Arc_Prop( 6, 33, 2 ), g );
216 add_edge( 0, 6, SPPRC_Example_Graph_Arc_Prop( 5, 31, 6 ), g );
217 add_edge( 0, 4, SPPRC_Example_Graph_Arc_Prop( 3, 14, 4 ), g );
218 add_edge( 0, 1, SPPRC_Example_Graph_Arc_Prop( 0, 43, 8 ), g );
219 add_edge( 0, 4, SPPRC_Example_Graph_Arc_Prop( 4, 28, 10 ), g );
220 add_edge( 0, 3, SPPRC_Example_Graph_Arc_Prop( 1, 31, 10 ), g );
221 add_edge( 0, 3, SPPRC_Example_Graph_Arc_Prop( 2, 1, 7 ), g );
222 add_edge( 0, 9, SPPRC_Example_Graph_Arc_Prop( 7, 25, 9 ), g );
223 add_edge( 1, 0, SPPRC_Example_Graph_Arc_Prop( 8, 37, 4 ), g );
224 add_edge( 1, 6, SPPRC_Example_Graph_Arc_Prop( 9, 7, 3 ), g );
225 add_edge( 2, 6, SPPRC_Example_Graph_Arc_Prop( 12, 6, 7 ), g );
226 add_edge( 2, 3, SPPRC_Example_Graph_Arc_Prop( 10, 13, 7 ), g );
227 add_edge( 2, 3, SPPRC_Example_Graph_Arc_Prop( 11, 49, 9 ), g );
228 add_edge( 2, 8, SPPRC_Example_Graph_Arc_Prop( 13, 47, 5 ), g );
229 add_edge( 3, 4, SPPRC_Example_Graph_Arc_Prop( 17, 5, 10 ), g );
230 add_edge( 3, 1, SPPRC_Example_Graph_Arc_Prop( 15, 47, 1 ), g );
231 add_edge( 3, 2, SPPRC_Example_Graph_Arc_Prop( 16, 26, 9 ), g );
232 add_edge( 3, 9, SPPRC_Example_Graph_Arc_Prop( 21, 24, 10 ), g );
233 add_edge( 3, 7, SPPRC_Example_Graph_Arc_Prop( 20, 50, 10 ), g );
234 add_edge( 3, 0, SPPRC_Example_Graph_Arc_Prop( 14, 41, 4 ), g );
235 add_edge( 3, 6, SPPRC_Example_Graph_Arc_Prop( 19, 6, 1 ), g );
236 add_edge( 3, 4, SPPRC_Example_Graph_Arc_Prop( 18, 8, 1 ), g );
237 add_edge( 4, 5, SPPRC_Example_Graph_Arc_Prop( 26, 38, 4 ), g );
238 add_edge( 4, 9, SPPRC_Example_Graph_Arc_Prop( 27, 32, 10 ), g );
239 add_edge( 4, 3, SPPRC_Example_Graph_Arc_Prop( 24, 40, 3 ), g );
240 add_edge( 4, 0, SPPRC_Example_Graph_Arc_Prop( 22, 7, 3 ), g );
241 add_edge( 4, 3, SPPRC_Example_Graph_Arc_Prop( 25, 28, 9 ), g );
242 add_edge( 4, 2, SPPRC_Example_Graph_Arc_Prop( 23, 39, 6 ), g );
243 add_edge( 5, 8, SPPRC_Example_Graph_Arc_Prop( 32, 6, 2 ), g );
244 add_edge( 5, 2, SPPRC_Example_Graph_Arc_Prop( 30, 26, 10 ), g );
245 add_edge( 5, 0, SPPRC_Example_Graph_Arc_Prop( 28, 38, 9 ), g );
246 add_edge( 5, 2, SPPRC_Example_Graph_Arc_Prop( 31, 48, 10 ), g );
247 add_edge( 5, 9, SPPRC_Example_Graph_Arc_Prop( 33, 49, 2 ), g );
248 add_edge( 5, 1, SPPRC_Example_Graph_Arc_Prop( 29, 22, 7 ), g );
249 add_edge( 6, 1, SPPRC_Example_Graph_Arc_Prop( 34, 15, 7 ), g );
250 add_edge( 6, 7, SPPRC_Example_Graph_Arc_Prop( 35, 20, 3 ), g );
251 add_edge( 7, 9, SPPRC_Example_Graph_Arc_Prop( 40, 1, 3 ), g );
252 add_edge( 7, 0, SPPRC_Example_Graph_Arc_Prop( 36, 23, 5 ), g );
253 add_edge( 7, 6, SPPRC_Example_Graph_Arc_Prop( 38, 36, 2 ), g );
254 add_edge( 7, 6, SPPRC_Example_Graph_Arc_Prop( 39, 18, 10 ), g );
255 add_edge( 7, 2, SPPRC_Example_Graph_Arc_Prop( 37, 2, 1 ), g );
256 add_edge( 8, 5, SPPRC_Example_Graph_Arc_Prop( 46, 36, 5 ), g );
257 add_edge( 8, 1, SPPRC_Example_Graph_Arc_Prop( 42, 13, 10 ), g );
258 add_edge( 8, 0, SPPRC_Example_Graph_Arc_Prop( 41, 40, 5 ), g );
259 add_edge( 8, 1, SPPRC_Example_Graph_Arc_Prop( 43, 32, 8 ), g );
260 add_edge( 8, 6, SPPRC_Example_Graph_Arc_Prop( 47, 25, 1 ), g );
261 add_edge( 8, 2, SPPRC_Example_Graph_Arc_Prop( 44, 44, 3 ), g );
262 add_edge( 8, 3, SPPRC_Example_Graph_Arc_Prop( 45, 11, 9 ), g );
263 add_edge( 9, 0, SPPRC_Example_Graph_Arc_Prop( 48, 41, 5 ), g );
264 add_edge( 9, 1, SPPRC_Example_Graph_Arc_Prop( 49, 44, 7 ), g );
265
266 // spp without resource constraints
267
268 std::vector
269 <std::vector
270 <graph_traits<SPPRC_Example_Graph>::edge_descriptor> >
271 opt_solutions;
272 std::vector<spp_no_rc_res_cont> pareto_opt_rcs_no_rc;
273 std::vector<int> i_vec_opt_solutions_spp_no_rc;
274 //std::cout << "r_c_shortest_paths:" << std::endl;
275 for( int s = 0; s < 10; ++s )
276 {
277 for( int t = 0; t < 10; ++t )
278 {
279 r_c_shortest_paths
280 ( g,
281 get( &SPPRC_Example_Graph_Vert_Prop::num, g ),
282 get( &SPPRC_Example_Graph_Arc_Prop::num, g ),
283 s,
284 t,
285 opt_solutions,
286 pareto_opt_rcs_no_rc,
287 spp_no_rc_res_cont( 0 ),
288 ref_no_res_cont(),
289 dominance_no_res_cont(),
290 std::allocator
291 <r_c_shortest_paths_label
292 <SPPRC_Example_Graph, spp_no_rc_res_cont> >(),
293 default_r_c_shortest_paths_visitor() );
294 i_vec_opt_solutions_spp_no_rc.push_back( pareto_opt_rcs_no_rc[0].cost );
295 //std::cout << "From " << s << " to " << t << ": ";
296 //std::cout << pareto_opt_rcs_no_rc[0].cost << std::endl;
297 }
298 }
299
300 //std::vector<graph_traits<SPPRC_Example_Graph>::vertex_descriptor>
301 // p( num_vertices( g ) );
302 //std::vector<int> d( num_vertices( g ) );
303 //std::vector<int> i_vec_dijkstra_distances;
304 //std::cout << "Dijkstra:" << std::endl;
305 //for( int s = 0; s < 10; ++s )
306 //{
307 // dijkstra_shortest_paths( g,
308 // s,
309 // &p[0],
310 // &d[0],
311 // get( &SPPRC_Example_Graph_Arc_Prop::cost, g ),
312 // get( &SPPRC_Example_Graph_Vert_Prop::num, g ),
313 // std::less<int>(),
314 // closed_plus<int>(),
315 // (std::numeric_limits<int>::max)(),
316 // 0,
317 // default_dijkstra_visitor() );
318 // for( int t = 0; t < 10; ++t )
319 // {
320 // i_vec_dijkstra_distances.push_back( d[t] );
321 // std::cout << "From " << s << " to " << t << ": " << d[t] << std::endl;
322 // }
323 //}
324
325 std::vector<int> i_vec_correct_solutions;
326 i_vec_correct_solutions.push_back( 0 );
327 i_vec_correct_solutions.push_back( 22 );
328 i_vec_correct_solutions.push_back( 27 );
329 i_vec_correct_solutions.push_back( 1 );
330 i_vec_correct_solutions.push_back( 6 );
331 i_vec_correct_solutions.push_back( 44 );
332 i_vec_correct_solutions.push_back( 7 );
333 i_vec_correct_solutions.push_back( 27 );
334 i_vec_correct_solutions.push_back( 50 );
335 i_vec_correct_solutions.push_back( 25 );
336 i_vec_correct_solutions.push_back( 37 );
337 i_vec_correct_solutions.push_back( 0 );
338 i_vec_correct_solutions.push_back( 29 );
339 i_vec_correct_solutions.push_back( 38 );
340 i_vec_correct_solutions.push_back( 43 );
341 i_vec_correct_solutions.push_back( 81 );
342 i_vec_correct_solutions.push_back( 7 );
343 i_vec_correct_solutions.push_back( 27 );
344 i_vec_correct_solutions.push_back( 76 );
345 i_vec_correct_solutions.push_back( 28 );
346 i_vec_correct_solutions.push_back( 25 );
347 i_vec_correct_solutions.push_back( 21 );
348 i_vec_correct_solutions.push_back( 0 );
349 i_vec_correct_solutions.push_back( 13 );
350 i_vec_correct_solutions.push_back( 18 );
351 i_vec_correct_solutions.push_back( 56 );
352 i_vec_correct_solutions.push_back( 6 );
353 i_vec_correct_solutions.push_back( 26 );
354 i_vec_correct_solutions.push_back( 47 );
355 i_vec_correct_solutions.push_back( 27 );
356 i_vec_correct_solutions.push_back( 12 );
357 i_vec_correct_solutions.push_back( 21 );
358 i_vec_correct_solutions.push_back( 26 );
359 i_vec_correct_solutions.push_back( 0 );
360 i_vec_correct_solutions.push_back( 5 );
361 i_vec_correct_solutions.push_back( 43 );
362 i_vec_correct_solutions.push_back( 6 );
363 i_vec_correct_solutions.push_back( 26 );
364 i_vec_correct_solutions.push_back( 49 );
365 i_vec_correct_solutions.push_back( 24 );
366 i_vec_correct_solutions.push_back( 7 );
367 i_vec_correct_solutions.push_back( 29 );
368 i_vec_correct_solutions.push_back( 34 );
369 i_vec_correct_solutions.push_back( 8 );
370 i_vec_correct_solutions.push_back( 0 );
371 i_vec_correct_solutions.push_back( 38 );
372 i_vec_correct_solutions.push_back( 14 );
373 i_vec_correct_solutions.push_back( 34 );
374 i_vec_correct_solutions.push_back( 44 );
375 i_vec_correct_solutions.push_back( 32 );
376 i_vec_correct_solutions.push_back( 29 );
377 i_vec_correct_solutions.push_back( 19 );
378 i_vec_correct_solutions.push_back( 26 );
379 i_vec_correct_solutions.push_back( 17 );
380 i_vec_correct_solutions.push_back( 22 );
381 i_vec_correct_solutions.push_back( 0 );
382 i_vec_correct_solutions.push_back( 23 );
383 i_vec_correct_solutions.push_back( 43 );
384 i_vec_correct_solutions.push_back( 6 );
385 i_vec_correct_solutions.push_back( 41 );
386 i_vec_correct_solutions.push_back( 43 );
387 i_vec_correct_solutions.push_back( 15 );
388 i_vec_correct_solutions.push_back( 22 );
389 i_vec_correct_solutions.push_back( 35 );
390 i_vec_correct_solutions.push_back( 40 );
391 i_vec_correct_solutions.push_back( 78 );
392 i_vec_correct_solutions.push_back( 0 );
393 i_vec_correct_solutions.push_back( 20 );
394 i_vec_correct_solutions.push_back( 69 );
395 i_vec_correct_solutions.push_back( 21 );
396 i_vec_correct_solutions.push_back( 23 );
397 i_vec_correct_solutions.push_back( 23 );
398 i_vec_correct_solutions.push_back( 2 );
399 i_vec_correct_solutions.push_back( 15 );
400 i_vec_correct_solutions.push_back( 20 );
401 i_vec_correct_solutions.push_back( 58 );
402 i_vec_correct_solutions.push_back( 8 );
403 i_vec_correct_solutions.push_back( 0 );
404 i_vec_correct_solutions.push_back( 49 );
405 i_vec_correct_solutions.push_back( 1 );
406 i_vec_correct_solutions.push_back( 23 );
407 i_vec_correct_solutions.push_back( 13 );
408 i_vec_correct_solutions.push_back( 37 );
409 i_vec_correct_solutions.push_back( 11 );
410 i_vec_correct_solutions.push_back( 16 );
411 i_vec_correct_solutions.push_back( 36 );
412 i_vec_correct_solutions.push_back( 17 );
413 i_vec_correct_solutions.push_back( 37 );
414 i_vec_correct_solutions.push_back( 0 );
415 i_vec_correct_solutions.push_back( 35 );
416 i_vec_correct_solutions.push_back( 41 );
417 i_vec_correct_solutions.push_back( 44 );
418 i_vec_correct_solutions.push_back( 68 );
419 i_vec_correct_solutions.push_back( 42 );
420 i_vec_correct_solutions.push_back( 47 );
421 i_vec_correct_solutions.push_back( 85 );
422 i_vec_correct_solutions.push_back( 48 );
423 i_vec_correct_solutions.push_back( 68 );
424 i_vec_correct_solutions.push_back( 91 );
425 i_vec_correct_solutions.push_back( 0 );
426 BOOST_CHECK(i_vec_opt_solutions_spp_no_rc.size() == i_vec_correct_solutions.size() );
427 for( int i = 0; i < static_cast<int>( i_vec_correct_solutions.size() ); ++i )
428 BOOST_CHECK( i_vec_opt_solutions_spp_no_rc[i] == i_vec_correct_solutions[i] );
429
430 // spptw
431 std::vector
432 <std::vector
433 <graph_traits<SPPRC_Example_Graph>::edge_descriptor> >
434 opt_solutions_spptw;
435 std::vector<spp_spptw_res_cont> pareto_opt_rcs_spptw;
436 std::vector
437 <std::vector
438 <std::vector
439 <std::vector
440 <graph_traits<SPPRC_Example_Graph>::edge_descriptor> > > >
441 vec_vec_vec_vec_opt_solutions_spptw( 10 );
442
443 for( int s = 0; s < 10; ++s )
444 {
445 for( int t = 0; t < 10; ++t )
446 {
447 r_c_shortest_paths
448 ( g,
449 get( &SPPRC_Example_Graph_Vert_Prop::num, g ),
450 get( &SPPRC_Example_Graph_Arc_Prop::num, g ),
451 s,
452 t,
453 opt_solutions_spptw,
454 pareto_opt_rcs_spptw,
455 // be careful, do not simply take 0 as initial value for time
456 spp_spptw_res_cont( 0, g[s].eat ),
457 ref_spptw(),
458 dominance_spptw(),
459 std::allocator
460 <r_c_shortest_paths_label
461 <SPPRC_Example_Graph, spp_spptw_res_cont> >(),
462 default_r_c_shortest_paths_visitor() );
463 vec_vec_vec_vec_opt_solutions_spptw[s].push_back( opt_solutions_spptw );
464 if( opt_solutions_spptw.size() )
465 {
466 bool b_is_a_path_at_all = false;
467 bool b_feasible = false;
468 bool b_correctly_extended = false;
469 spp_spptw_res_cont actual_final_resource_levels( 0, 0 );
470 graph_traits<SPPRC_Example_Graph>::edge_descriptor ed_last_extended_arc;
471 check_r_c_path( g,
472 opt_solutions_spptw[0],
473 spp_spptw_res_cont( 0, g[s].eat ),
474 true,
475 pareto_opt_rcs_spptw[0],
476 actual_final_resource_levels,
477 ref_spptw(),
478 b_is_a_path_at_all,
479 b_feasible,
480 b_correctly_extended,
481 ed_last_extended_arc );
482 BOOST_CHECK(b_is_a_path_at_all && b_feasible && b_correctly_extended);
483 b_is_a_path_at_all = false;
484 b_feasible = false;
485 b_correctly_extended = false;
486 spp_spptw_res_cont actual_final_resource_levels2( 0, 0 );
487 graph_traits<SPPRC_Example_Graph>::edge_descriptor ed_last_extended_arc2;
488 check_r_c_path( g,
489 opt_solutions_spptw[0],
490 spp_spptw_res_cont( 0, g[s].eat ),
491 false,
492 pareto_opt_rcs_spptw[0],
493 actual_final_resource_levels2,
494 ref_spptw(),
495 b_is_a_path_at_all,
496 b_feasible,
497 b_correctly_extended,
498 ed_last_extended_arc2 );
499 BOOST_CHECK(b_is_a_path_at_all && b_feasible && b_correctly_extended);
500 }
501 }
502 }
503
504 std::vector<int> i_vec_correct_num_solutions_spptw;
505 i_vec_correct_num_solutions_spptw.push_back( 1 );
506 i_vec_correct_num_solutions_spptw.push_back( 2 );
507 i_vec_correct_num_solutions_spptw.push_back( 3 );
508 i_vec_correct_num_solutions_spptw.push_back( 1 );
509 i_vec_correct_num_solutions_spptw.push_back( 3 );
510 i_vec_correct_num_solutions_spptw.push_back( 1 );
511 i_vec_correct_num_solutions_spptw.push_back( 2 );
512 i_vec_correct_num_solutions_spptw.push_back( 1 );
513 i_vec_correct_num_solutions_spptw.push_back( 2 );
514 i_vec_correct_num_solutions_spptw.push_back( 1 );
515 i_vec_correct_num_solutions_spptw.push_back( 1 );
516 i_vec_correct_num_solutions_spptw.push_back( 1 );
517 i_vec_correct_num_solutions_spptw.push_back( 4 );
518 i_vec_correct_num_solutions_spptw.push_back( 1 );
519 i_vec_correct_num_solutions_spptw.push_back( 3 );
520 i_vec_correct_num_solutions_spptw.push_back( 1 );
521 i_vec_correct_num_solutions_spptw.push_back( 1 );
522 i_vec_correct_num_solutions_spptw.push_back( 1 );
523 i_vec_correct_num_solutions_spptw.push_back( 2 );
524 i_vec_correct_num_solutions_spptw.push_back( 2 );
525 i_vec_correct_num_solutions_spptw.push_back( 4 );
526 i_vec_correct_num_solutions_spptw.push_back( 1 );
527 i_vec_correct_num_solutions_spptw.push_back( 1 );
528 i_vec_correct_num_solutions_spptw.push_back( 1 );
529 i_vec_correct_num_solutions_spptw.push_back( 4 );
530 i_vec_correct_num_solutions_spptw.push_back( 1 );
531 i_vec_correct_num_solutions_spptw.push_back( 2 );
532 i_vec_correct_num_solutions_spptw.push_back( 1 );
533 i_vec_correct_num_solutions_spptw.push_back( 1 );
534 i_vec_correct_num_solutions_spptw.push_back( 3 );
535 i_vec_correct_num_solutions_spptw.push_back( 2 );
536 i_vec_correct_num_solutions_spptw.push_back( 2 );
537 i_vec_correct_num_solutions_spptw.push_back( 2 );
538 i_vec_correct_num_solutions_spptw.push_back( 1 );
539 i_vec_correct_num_solutions_spptw.push_back( 2 );
540 i_vec_correct_num_solutions_spptw.push_back( 0 );
541 i_vec_correct_num_solutions_spptw.push_back( 1 );
542 i_vec_correct_num_solutions_spptw.push_back( 1 );
543 i_vec_correct_num_solutions_spptw.push_back( 2 );
544 i_vec_correct_num_solutions_spptw.push_back( 1 );
545 i_vec_correct_num_solutions_spptw.push_back( 1 );
546 i_vec_correct_num_solutions_spptw.push_back( 2 );
547 i_vec_correct_num_solutions_spptw.push_back( 2 );
548 i_vec_correct_num_solutions_spptw.push_back( 1 );
549 i_vec_correct_num_solutions_spptw.push_back( 1 );
550 i_vec_correct_num_solutions_spptw.push_back( 1 );
551 i_vec_correct_num_solutions_spptw.push_back( 2 );
552 i_vec_correct_num_solutions_spptw.push_back( 1 );
553 i_vec_correct_num_solutions_spptw.push_back( 2 );
554 i_vec_correct_num_solutions_spptw.push_back( 1 );
555 i_vec_correct_num_solutions_spptw.push_back( 4 );
556 i_vec_correct_num_solutions_spptw.push_back( 2 );
557 i_vec_correct_num_solutions_spptw.push_back( 2 );
558 i_vec_correct_num_solutions_spptw.push_back( 1 );
559 i_vec_correct_num_solutions_spptw.push_back( 4 );
560 i_vec_correct_num_solutions_spptw.push_back( 1 );
561 i_vec_correct_num_solutions_spptw.push_back( 4 );
562 i_vec_correct_num_solutions_spptw.push_back( 1 );
563 i_vec_correct_num_solutions_spptw.push_back( 1 );
564 i_vec_correct_num_solutions_spptw.push_back( 2 );
565 i_vec_correct_num_solutions_spptw.push_back( 2 );
566 i_vec_correct_num_solutions_spptw.push_back( 1 );
567 i_vec_correct_num_solutions_spptw.push_back( 4 );
568 i_vec_correct_num_solutions_spptw.push_back( 2 );
569 i_vec_correct_num_solutions_spptw.push_back( 5 );
570 i_vec_correct_num_solutions_spptw.push_back( 1 );
571 i_vec_correct_num_solutions_spptw.push_back( 1 );
572 i_vec_correct_num_solutions_spptw.push_back( 1 );
573 i_vec_correct_num_solutions_spptw.push_back( 2 );
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( 3 );
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( 2 );
580 i_vec_correct_num_solutions_spptw.push_back( 0 );
581 i_vec_correct_num_solutions_spptw.push_back( 2 );
582 i_vec_correct_num_solutions_spptw.push_back( 1 );
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( 3 );
586 i_vec_correct_num_solutions_spptw.push_back( 1 );
587 i_vec_correct_num_solutions_spptw.push_back( 2 );
588 i_vec_correct_num_solutions_spptw.push_back( 1 );
589 i_vec_correct_num_solutions_spptw.push_back( 3 );
590 i_vec_correct_num_solutions_spptw.push_back( 1 );
591 i_vec_correct_num_solutions_spptw.push_back( 3 );
592 i_vec_correct_num_solutions_spptw.push_back( 1 );
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( 4 );
598 i_vec_correct_num_solutions_spptw.push_back( 1 );
599 i_vec_correct_num_solutions_spptw.push_back( 3 );
600 i_vec_correct_num_solutions_spptw.push_back( 0 );
601 i_vec_correct_num_solutions_spptw.push_back( 2 );
602 i_vec_correct_num_solutions_spptw.push_back( 3 );
603 i_vec_correct_num_solutions_spptw.push_back( 4 );
604 i_vec_correct_num_solutions_spptw.push_back( 1 );
605 for( int s = 0; s < 10; ++s )
606 for( int t = 0; t < 10; ++t )
607 BOOST_CHECK( static_cast<int>
608 ( vec_vec_vec_vec_opt_solutions_spptw[s][t].size() ) ==
609 i_vec_correct_num_solutions_spptw[10 * s + t] );
610
611 // one pareto-optimal solution
612 SPPRC_Example_Graph g2;
613 add_vertex( SPPRC_Example_Graph_Vert_Prop( 0, 0, 1000000000 ), g2 );
614 add_vertex( SPPRC_Example_Graph_Vert_Prop( 1, 0, 1000000000 ), g2 );
615 add_vertex( SPPRC_Example_Graph_Vert_Prop( 2, 0, 1000000000 ), g2 );
616 add_vertex( SPPRC_Example_Graph_Vert_Prop( 3, 0, 1000000000 ), g2 );
617 add_edge( 0, 1, SPPRC_Example_Graph_Arc_Prop( 0, 1, 1 ), g2 );
618 add_edge( 0, 2, SPPRC_Example_Graph_Arc_Prop( 1, 2, 1 ), g2 );
619 add_edge( 1, 3, SPPRC_Example_Graph_Arc_Prop( 2, 3, 1 ), g2 );
620 add_edge( 2, 3, SPPRC_Example_Graph_Arc_Prop( 3, 1, 1 ), g2 );
621 std::vector<graph_traits<SPPRC_Example_Graph>::edge_descriptor> opt_solution;
622 spp_spptw_res_cont pareto_opt_rc;
623 r_c_shortest_paths( g2,
624 get( &SPPRC_Example_Graph_Vert_Prop::num, g2 ),
625 get( &SPPRC_Example_Graph_Arc_Prop::num, g2 ),
626 0,
627 3,
628 opt_solution,
629 pareto_opt_rc,
630 spp_spptw_res_cont( 0, 0 ),
631 ref_spptw(),
632 dominance_spptw(),
633 std::allocator
634 <r_c_shortest_paths_label
635 <SPPRC_Example_Graph, spp_spptw_res_cont> >(),
636 default_r_c_shortest_paths_visitor() );
637
638 BOOST_CHECK(pareto_opt_rc.cost == 3);
639
640 return 0;
641 }
642