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