| // Copyright Michael Drexl 2005, 2006. |
| // Distributed under the Boost Software License, Version 1.0. |
| // (See accompanying file LICENSE_1_0.txt or copy at |
| // http://boost.org/LICENSE_1_0.txt) |
| |
| #include <boost/config.hpp> |
| |
| #ifdef BOOST_MSVC |
| # pragma warning(disable: 4267) |
| #endif |
| |
| #include <boost/graph/adjacency_list.hpp> |
| //#include <boost/graph/dijkstra_shortest_paths.hpp> |
| |
| #include <boost/graph/r_c_shortest_paths.hpp> |
| #include <iostream> |
| #include <boost/test/minimal.hpp> |
| |
| using namespace boost; |
| |
| struct SPPRC_Example_Graph_Vert_Prop |
| { |
| SPPRC_Example_Graph_Vert_Prop( int n = 0, int e = 0, int l = 0 ) |
| : num( n ), eat( e ), lat( l ) {} |
| int num; |
| // earliest arrival time |
| int eat; |
| // latest arrival time |
| int lat; |
| }; |
| |
| struct SPPRC_Example_Graph_Arc_Prop |
| { |
| SPPRC_Example_Graph_Arc_Prop( int n = 0, int c = 0, int t = 0 ) |
| : num( n ), cost( c ), time( t ) {} |
| int num; |
| // traversal cost |
| int cost; |
| // traversal time |
| int time; |
| }; |
| |
| typedef adjacency_list<vecS, |
| vecS, |
| directedS, |
| SPPRC_Example_Graph_Vert_Prop, |
| SPPRC_Example_Graph_Arc_Prop> |
| SPPRC_Example_Graph; |
| |
| // data structures for spp without resource constraints: |
| // ResourceContainer model |
| struct spp_no_rc_res_cont |
| { |
| spp_no_rc_res_cont( int c = 0 ) : cost( c ) {}; |
| spp_no_rc_res_cont& operator=( const spp_no_rc_res_cont& other ) |
| { |
| if( this == &other ) |
| return *this; |
| this->~spp_no_rc_res_cont(); |
| new( this ) spp_no_rc_res_cont( other ); |
| return *this; |
| } |
| int cost; |
| }; |
| |
| bool operator==( const spp_no_rc_res_cont& res_cont_1, |
| const spp_no_rc_res_cont& res_cont_2 ) |
| { |
| return ( res_cont_1.cost == res_cont_2.cost ); |
| } |
| |
| bool operator<( const spp_no_rc_res_cont& res_cont_1, |
| const spp_no_rc_res_cont& res_cont_2 ) |
| { |
| return ( res_cont_1.cost < res_cont_2.cost ); |
| } |
| |
| // ResourceExtensionFunction model |
| class ref_no_res_cont |
| { |
| public: |
| inline bool 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 ) const |
| { |
| new_cont.cost = old_cont.cost + g[ed].cost; |
| return true; |
| } |
| }; |
| |
| // DominanceFunction model |
| class dominance_no_res_cont |
| { |
| public: |
| inline bool operator()( const spp_no_rc_res_cont& res_cont_1, |
| const spp_no_rc_res_cont& res_cont_2 ) const |
| { |
| // must be "<=" here!!! |
| // must NOT be "<"!!! |
| return res_cont_1.cost <= res_cont_2.cost; |
| // this is not a contradiction to the documentation |
| // the documentation says: |
| // "A label $l_1$ dominates a label $l_2$ if and only if both are resident |
| // at the same vertex, and if, for each resource, the resource consumption |
| // of $l_1$ is less than or equal to the resource consumption of $l_2$, |
| // and if there is at least one resource where $l_1$ has a lower resource |
| // consumption than $l_2$." |
| // one can think of a new label with a resource consumption equal to that |
| // of an old label as being dominated by that old label, because the new |
| // one will have a higher number and is created at a later point in time, |
| // so one can implicitly use the number or the creation time as a resource |
| // for tie-breaking |
| } |
| }; |
| // end data structures for spp without resource constraints: |
| |
| // data structures for shortest path problem with time windows (spptw) |
| // ResourceContainer model |
| struct spp_spptw_res_cont |
| { |
| spp_spptw_res_cont( int c = 0, int t = 0 ) : cost( c ), time( t ) {} |
| spp_spptw_res_cont& operator=( const spp_spptw_res_cont& other ) |
| { |
| if( this == &other ) |
| return *this; |
| this->~spp_spptw_res_cont(); |
| new( this ) spp_spptw_res_cont( other ); |
| return *this; |
| } |
| int cost; |
| int time; |
| }; |
| |
| bool operator==( const spp_spptw_res_cont& res_cont_1, |
| const spp_spptw_res_cont& res_cont_2 ) |
| { |
| return ( res_cont_1.cost == res_cont_2.cost |
| && res_cont_1.time == res_cont_2.time ); |
| } |
| |
| bool operator<( const spp_spptw_res_cont& res_cont_1, |
| const spp_spptw_res_cont& res_cont_2 ) |
| { |
| if( res_cont_1.cost > res_cont_2.cost ) |
| return false; |
| if( res_cont_1.cost == res_cont_2.cost ) |
| return res_cont_1.time < res_cont_2.time; |
| return true; |
| } |
| |
| // ResourceExtensionFunction model |
| class ref_spptw |
| { |
| public: |
| inline bool 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 ) const |
| { |
| const SPPRC_Example_Graph_Arc_Prop& arc_prop = |
| get( edge_bundle, g )[ed]; |
| const SPPRC_Example_Graph_Vert_Prop& vert_prop = |
| get( vertex_bundle, g )[target( ed, g )]; |
| new_cont.cost = old_cont.cost + arc_prop.cost; |
| int& i_time = new_cont.time; |
| i_time = old_cont.time + arc_prop.time; |
| i_time < vert_prop.eat ? i_time = vert_prop.eat : 0; |
| return i_time <= vert_prop.lat ? true : false; |
| } |
| }; |
| |
| // DominanceFunction model |
| class dominance_spptw |
| { |
| public: |
| inline bool operator()( const spp_spptw_res_cont& res_cont_1, |
| const spp_spptw_res_cont& res_cont_2 ) const |
| { |
| // must be "<=" here!!! |
| // must NOT be "<"!!! |
| return res_cont_1.cost <= res_cont_2.cost |
| && res_cont_1.time <= res_cont_2.time; |
| // this is not a contradiction to the documentation |
| // the documentation says: |
| // "A label $l_1$ dominates a label $l_2$ if and only if both are resident |
| // at the same vertex, and if, for each resource, the resource consumption |
| // of $l_1$ is less than or equal to the resource consumption of $l_2$, |
| // and if there is at least one resource where $l_1$ has a lower resource |
| // consumption than $l_2$." |
| // one can think of a new label with a resource consumption equal to that |
| // of an old label as being dominated by that old label, because the new |
| // one will have a higher number and is created at a later point in time, |
| // so one can implicitly use the number or the creation time as a resource |
| // for tie-breaking |
| } |
| }; |
| // end data structures for shortest path problem with time windows (spptw) |
| |
| int test_main(int, char*[]) |
| { |
| SPPRC_Example_Graph g; |
| add_vertex( SPPRC_Example_Graph_Vert_Prop( 0, 0, 1000000000 ), g ); |
| add_vertex( SPPRC_Example_Graph_Vert_Prop( 1, 56, 142 ), g ); |
| add_vertex( SPPRC_Example_Graph_Vert_Prop( 2, 0, 1000000000 ), g ); |
| add_vertex( SPPRC_Example_Graph_Vert_Prop( 3, 89, 178 ), g ); |
| add_vertex( SPPRC_Example_Graph_Vert_Prop( 4, 0, 1000000000 ), g ); |
| add_vertex( SPPRC_Example_Graph_Vert_Prop( 5, 49, 76 ), g ); |
| add_vertex( SPPRC_Example_Graph_Vert_Prop( 6, 0, 1000000000 ), g ); |
| add_vertex( SPPRC_Example_Graph_Vert_Prop( 7, 98, 160 ), g ); |
| add_vertex( SPPRC_Example_Graph_Vert_Prop( 8, 0, 1000000000 ), g ); |
| add_vertex( SPPRC_Example_Graph_Vert_Prop( 9, 90, 158 ), g ); |
| add_edge( 0, 7, SPPRC_Example_Graph_Arc_Prop( 6, 33, 2 ), g ); |
| add_edge( 0, 6, SPPRC_Example_Graph_Arc_Prop( 5, 31, 6 ), g ); |
| add_edge( 0, 4, SPPRC_Example_Graph_Arc_Prop( 3, 14, 4 ), g ); |
| add_edge( 0, 1, SPPRC_Example_Graph_Arc_Prop( 0, 43, 8 ), g ); |
| add_edge( 0, 4, SPPRC_Example_Graph_Arc_Prop( 4, 28, 10 ), g ); |
| add_edge( 0, 3, SPPRC_Example_Graph_Arc_Prop( 1, 31, 10 ), g ); |
| add_edge( 0, 3, SPPRC_Example_Graph_Arc_Prop( 2, 1, 7 ), g ); |
| add_edge( 0, 9, SPPRC_Example_Graph_Arc_Prop( 7, 25, 9 ), g ); |
| add_edge( 1, 0, SPPRC_Example_Graph_Arc_Prop( 8, 37, 4 ), g ); |
| add_edge( 1, 6, SPPRC_Example_Graph_Arc_Prop( 9, 7, 3 ), g ); |
| add_edge( 2, 6, SPPRC_Example_Graph_Arc_Prop( 12, 6, 7 ), g ); |
| add_edge( 2, 3, SPPRC_Example_Graph_Arc_Prop( 10, 13, 7 ), g ); |
| add_edge( 2, 3, SPPRC_Example_Graph_Arc_Prop( 11, 49, 9 ), g ); |
| add_edge( 2, 8, SPPRC_Example_Graph_Arc_Prop( 13, 47, 5 ), g ); |
| add_edge( 3, 4, SPPRC_Example_Graph_Arc_Prop( 17, 5, 10 ), g ); |
| add_edge( 3, 1, SPPRC_Example_Graph_Arc_Prop( 15, 47, 1 ), g ); |
| add_edge( 3, 2, SPPRC_Example_Graph_Arc_Prop( 16, 26, 9 ), g ); |
| add_edge( 3, 9, SPPRC_Example_Graph_Arc_Prop( 21, 24, 10 ), g ); |
| add_edge( 3, 7, SPPRC_Example_Graph_Arc_Prop( 20, 50, 10 ), g ); |
| add_edge( 3, 0, SPPRC_Example_Graph_Arc_Prop( 14, 41, 4 ), g ); |
| add_edge( 3, 6, SPPRC_Example_Graph_Arc_Prop( 19, 6, 1 ), g ); |
| add_edge( 3, 4, SPPRC_Example_Graph_Arc_Prop( 18, 8, 1 ), g ); |
| add_edge( 4, 5, SPPRC_Example_Graph_Arc_Prop( 26, 38, 4 ), g ); |
| add_edge( 4, 9, SPPRC_Example_Graph_Arc_Prop( 27, 32, 10 ), g ); |
| add_edge( 4, 3, SPPRC_Example_Graph_Arc_Prop( 24, 40, 3 ), g ); |
| add_edge( 4, 0, SPPRC_Example_Graph_Arc_Prop( 22, 7, 3 ), g ); |
| add_edge( 4, 3, SPPRC_Example_Graph_Arc_Prop( 25, 28, 9 ), g ); |
| add_edge( 4, 2, SPPRC_Example_Graph_Arc_Prop( 23, 39, 6 ), g ); |
| add_edge( 5, 8, SPPRC_Example_Graph_Arc_Prop( 32, 6, 2 ), g ); |
| add_edge( 5, 2, SPPRC_Example_Graph_Arc_Prop( 30, 26, 10 ), g ); |
| add_edge( 5, 0, SPPRC_Example_Graph_Arc_Prop( 28, 38, 9 ), g ); |
| add_edge( 5, 2, SPPRC_Example_Graph_Arc_Prop( 31, 48, 10 ), g ); |
| add_edge( 5, 9, SPPRC_Example_Graph_Arc_Prop( 33, 49, 2 ), g ); |
| add_edge( 5, 1, SPPRC_Example_Graph_Arc_Prop( 29, 22, 7 ), g ); |
| add_edge( 6, 1, SPPRC_Example_Graph_Arc_Prop( 34, 15, 7 ), g ); |
| add_edge( 6, 7, SPPRC_Example_Graph_Arc_Prop( 35, 20, 3 ), g ); |
| add_edge( 7, 9, SPPRC_Example_Graph_Arc_Prop( 40, 1, 3 ), g ); |
| add_edge( 7, 0, SPPRC_Example_Graph_Arc_Prop( 36, 23, 5 ), g ); |
| add_edge( 7, 6, SPPRC_Example_Graph_Arc_Prop( 38, 36, 2 ), g ); |
| add_edge( 7, 6, SPPRC_Example_Graph_Arc_Prop( 39, 18, 10 ), g ); |
| add_edge( 7, 2, SPPRC_Example_Graph_Arc_Prop( 37, 2, 1 ), g ); |
| add_edge( 8, 5, SPPRC_Example_Graph_Arc_Prop( 46, 36, 5 ), g ); |
| add_edge( 8, 1, SPPRC_Example_Graph_Arc_Prop( 42, 13, 10 ), g ); |
| add_edge( 8, 0, SPPRC_Example_Graph_Arc_Prop( 41, 40, 5 ), g ); |
| add_edge( 8, 1, SPPRC_Example_Graph_Arc_Prop( 43, 32, 8 ), g ); |
| add_edge( 8, 6, SPPRC_Example_Graph_Arc_Prop( 47, 25, 1 ), g ); |
| add_edge( 8, 2, SPPRC_Example_Graph_Arc_Prop( 44, 44, 3 ), g ); |
| add_edge( 8, 3, SPPRC_Example_Graph_Arc_Prop( 45, 11, 9 ), g ); |
| add_edge( 9, 0, SPPRC_Example_Graph_Arc_Prop( 48, 41, 5 ), g ); |
| add_edge( 9, 1, SPPRC_Example_Graph_Arc_Prop( 49, 44, 7 ), g ); |
| |
| // spp without resource constraints |
| |
| std::vector |
| <std::vector |
| <graph_traits<SPPRC_Example_Graph>::edge_descriptor> > |
| opt_solutions; |
| std::vector<spp_no_rc_res_cont> pareto_opt_rcs_no_rc; |
| std::vector<int> i_vec_opt_solutions_spp_no_rc; |
| //std::cout << "r_c_shortest_paths:" << std::endl; |
| for( int s = 0; s < 10; ++s ) |
| { |
| for( int t = 0; t < 10; ++t ) |
| { |
| r_c_shortest_paths |
| ( g, |
| get( &SPPRC_Example_Graph_Vert_Prop::num, g ), |
| get( &SPPRC_Example_Graph_Arc_Prop::num, g ), |
| s, |
| t, |
| opt_solutions, |
| pareto_opt_rcs_no_rc, |
| spp_no_rc_res_cont( 0 ), |
| ref_no_res_cont(), |
| dominance_no_res_cont(), |
| std::allocator |
| <r_c_shortest_paths_label |
| <SPPRC_Example_Graph, spp_no_rc_res_cont> >(), |
| default_r_c_shortest_paths_visitor() ); |
| i_vec_opt_solutions_spp_no_rc.push_back( pareto_opt_rcs_no_rc[0].cost ); |
| //std::cout << "From " << s << " to " << t << ": "; |
| //std::cout << pareto_opt_rcs_no_rc[0].cost << std::endl; |
| } |
| } |
| |
| //std::vector<graph_traits<SPPRC_Example_Graph>::vertex_descriptor> |
| // p( num_vertices( g ) ); |
| //std::vector<int> d( num_vertices( g ) ); |
| //std::vector<int> i_vec_dijkstra_distances; |
| //std::cout << "Dijkstra:" << std::endl; |
| //for( int s = 0; s < 10; ++s ) |
| //{ |
| // dijkstra_shortest_paths( g, |
| // s, |
| // &p[0], |
| // &d[0], |
| // get( &SPPRC_Example_Graph_Arc_Prop::cost, g ), |
| // get( &SPPRC_Example_Graph_Vert_Prop::num, g ), |
| // std::less<int>(), |
| // closed_plus<int>(), |
| // (std::numeric_limits<int>::max)(), |
| // 0, |
| // default_dijkstra_visitor() ); |
| // for( int t = 0; t < 10; ++t ) |
| // { |
| // i_vec_dijkstra_distances.push_back( d[t] ); |
| // std::cout << "From " << s << " to " << t << ": " << d[t] << std::endl; |
| // } |
| //} |
| |
| std::vector<int> i_vec_correct_solutions; |
| i_vec_correct_solutions.push_back( 0 ); |
| i_vec_correct_solutions.push_back( 22 ); |
| i_vec_correct_solutions.push_back( 27 ); |
| i_vec_correct_solutions.push_back( 1 ); |
| i_vec_correct_solutions.push_back( 6 ); |
| i_vec_correct_solutions.push_back( 44 ); |
| i_vec_correct_solutions.push_back( 7 ); |
| i_vec_correct_solutions.push_back( 27 ); |
| i_vec_correct_solutions.push_back( 50 ); |
| i_vec_correct_solutions.push_back( 25 ); |
| i_vec_correct_solutions.push_back( 37 ); |
| i_vec_correct_solutions.push_back( 0 ); |
| i_vec_correct_solutions.push_back( 29 ); |
| i_vec_correct_solutions.push_back( 38 ); |
| i_vec_correct_solutions.push_back( 43 ); |
| i_vec_correct_solutions.push_back( 81 ); |
| i_vec_correct_solutions.push_back( 7 ); |
| i_vec_correct_solutions.push_back( 27 ); |
| i_vec_correct_solutions.push_back( 76 ); |
| i_vec_correct_solutions.push_back( 28 ); |
| i_vec_correct_solutions.push_back( 25 ); |
| i_vec_correct_solutions.push_back( 21 ); |
| i_vec_correct_solutions.push_back( 0 ); |
| i_vec_correct_solutions.push_back( 13 ); |
| i_vec_correct_solutions.push_back( 18 ); |
| i_vec_correct_solutions.push_back( 56 ); |
| i_vec_correct_solutions.push_back( 6 ); |
| i_vec_correct_solutions.push_back( 26 ); |
| i_vec_correct_solutions.push_back( 47 ); |
| i_vec_correct_solutions.push_back( 27 ); |
| i_vec_correct_solutions.push_back( 12 ); |
| i_vec_correct_solutions.push_back( 21 ); |
| i_vec_correct_solutions.push_back( 26 ); |
| i_vec_correct_solutions.push_back( 0 ); |
| i_vec_correct_solutions.push_back( 5 ); |
| i_vec_correct_solutions.push_back( 43 ); |
| i_vec_correct_solutions.push_back( 6 ); |
| i_vec_correct_solutions.push_back( 26 ); |
| i_vec_correct_solutions.push_back( 49 ); |
| i_vec_correct_solutions.push_back( 24 ); |
| i_vec_correct_solutions.push_back( 7 ); |
| i_vec_correct_solutions.push_back( 29 ); |
| i_vec_correct_solutions.push_back( 34 ); |
| i_vec_correct_solutions.push_back( 8 ); |
| i_vec_correct_solutions.push_back( 0 ); |
| i_vec_correct_solutions.push_back( 38 ); |
| i_vec_correct_solutions.push_back( 14 ); |
| i_vec_correct_solutions.push_back( 34 ); |
| i_vec_correct_solutions.push_back( 44 ); |
| i_vec_correct_solutions.push_back( 32 ); |
| i_vec_correct_solutions.push_back( 29 ); |
| i_vec_correct_solutions.push_back( 19 ); |
| i_vec_correct_solutions.push_back( 26 ); |
| i_vec_correct_solutions.push_back( 17 ); |
| i_vec_correct_solutions.push_back( 22 ); |
| i_vec_correct_solutions.push_back( 0 ); |
| i_vec_correct_solutions.push_back( 23 ); |
| i_vec_correct_solutions.push_back( 43 ); |
| i_vec_correct_solutions.push_back( 6 ); |
| i_vec_correct_solutions.push_back( 41 ); |
| i_vec_correct_solutions.push_back( 43 ); |
| i_vec_correct_solutions.push_back( 15 ); |
| i_vec_correct_solutions.push_back( 22 ); |
| i_vec_correct_solutions.push_back( 35 ); |
| i_vec_correct_solutions.push_back( 40 ); |
| i_vec_correct_solutions.push_back( 78 ); |
| i_vec_correct_solutions.push_back( 0 ); |
| i_vec_correct_solutions.push_back( 20 ); |
| i_vec_correct_solutions.push_back( 69 ); |
| i_vec_correct_solutions.push_back( 21 ); |
| i_vec_correct_solutions.push_back( 23 ); |
| i_vec_correct_solutions.push_back( 23 ); |
| i_vec_correct_solutions.push_back( 2 ); |
| i_vec_correct_solutions.push_back( 15 ); |
| i_vec_correct_solutions.push_back( 20 ); |
| i_vec_correct_solutions.push_back( 58 ); |
| i_vec_correct_solutions.push_back( 8 ); |
| i_vec_correct_solutions.push_back( 0 ); |
| i_vec_correct_solutions.push_back( 49 ); |
| i_vec_correct_solutions.push_back( 1 ); |
| i_vec_correct_solutions.push_back( 23 ); |
| i_vec_correct_solutions.push_back( 13 ); |
| i_vec_correct_solutions.push_back( 37 ); |
| i_vec_correct_solutions.push_back( 11 ); |
| i_vec_correct_solutions.push_back( 16 ); |
| i_vec_correct_solutions.push_back( 36 ); |
| i_vec_correct_solutions.push_back( 17 ); |
| i_vec_correct_solutions.push_back( 37 ); |
| i_vec_correct_solutions.push_back( 0 ); |
| i_vec_correct_solutions.push_back( 35 ); |
| i_vec_correct_solutions.push_back( 41 ); |
| i_vec_correct_solutions.push_back( 44 ); |
| i_vec_correct_solutions.push_back( 68 ); |
| i_vec_correct_solutions.push_back( 42 ); |
| i_vec_correct_solutions.push_back( 47 ); |
| i_vec_correct_solutions.push_back( 85 ); |
| i_vec_correct_solutions.push_back( 48 ); |
| i_vec_correct_solutions.push_back( 68 ); |
| i_vec_correct_solutions.push_back( 91 ); |
| i_vec_correct_solutions.push_back( 0 ); |
| BOOST_CHECK(i_vec_opt_solutions_spp_no_rc.size() == i_vec_correct_solutions.size() ); |
| for( int i = 0; i < static_cast<int>( i_vec_correct_solutions.size() ); ++i ) |
| BOOST_CHECK( i_vec_opt_solutions_spp_no_rc[i] == i_vec_correct_solutions[i] ); |
| |
| // spptw |
| std::vector |
| <std::vector |
| <graph_traits<SPPRC_Example_Graph>::edge_descriptor> > |
| opt_solutions_spptw; |
| std::vector<spp_spptw_res_cont> pareto_opt_rcs_spptw; |
| std::vector |
| <std::vector |
| <std::vector |
| <std::vector |
| <graph_traits<SPPRC_Example_Graph>::edge_descriptor> > > > |
| vec_vec_vec_vec_opt_solutions_spptw( 10 ); |
| |
| for( int s = 0; s < 10; ++s ) |
| { |
| for( int t = 0; t < 10; ++t ) |
| { |
| r_c_shortest_paths |
| ( g, |
| get( &SPPRC_Example_Graph_Vert_Prop::num, g ), |
| get( &SPPRC_Example_Graph_Arc_Prop::num, g ), |
| s, |
| t, |
| opt_solutions_spptw, |
| pareto_opt_rcs_spptw, |
| // be careful, do not simply take 0 as initial value for time |
| spp_spptw_res_cont( 0, g[s].eat ), |
| ref_spptw(), |
| dominance_spptw(), |
| std::allocator |
| <r_c_shortest_paths_label |
| <SPPRC_Example_Graph, spp_spptw_res_cont> >(), |
| default_r_c_shortest_paths_visitor() ); |
| vec_vec_vec_vec_opt_solutions_spptw[s].push_back( opt_solutions_spptw ); |
| if( opt_solutions_spptw.size() ) |
| { |
| bool b_is_a_path_at_all = false; |
| bool b_feasible = false; |
| bool b_correctly_extended = false; |
| spp_spptw_res_cont actual_final_resource_levels( 0, 0 ); |
| graph_traits<SPPRC_Example_Graph>::edge_descriptor ed_last_extended_arc; |
| check_r_c_path( g, |
| opt_solutions_spptw[0], |
| spp_spptw_res_cont( 0, g[s].eat ), |
| true, |
| pareto_opt_rcs_spptw[0], |
| actual_final_resource_levels, |
| ref_spptw(), |
| b_is_a_path_at_all, |
| b_feasible, |
| b_correctly_extended, |
| ed_last_extended_arc ); |
| BOOST_CHECK(b_is_a_path_at_all && b_feasible && b_correctly_extended); |
| b_is_a_path_at_all = false; |
| b_feasible = false; |
| b_correctly_extended = false; |
| spp_spptw_res_cont actual_final_resource_levels2( 0, 0 ); |
| graph_traits<SPPRC_Example_Graph>::edge_descriptor ed_last_extended_arc2; |
| check_r_c_path( g, |
| opt_solutions_spptw[0], |
| spp_spptw_res_cont( 0, g[s].eat ), |
| false, |
| pareto_opt_rcs_spptw[0], |
| actual_final_resource_levels2, |
| ref_spptw(), |
| b_is_a_path_at_all, |
| b_feasible, |
| b_correctly_extended, |
| ed_last_extended_arc2 ); |
| BOOST_CHECK(b_is_a_path_at_all && b_feasible && b_correctly_extended); |
| } |
| } |
| } |
| |
| std::vector<int> i_vec_correct_num_solutions_spptw; |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 3 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 3 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 4 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 3 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 4 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 4 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 3 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 0 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 4 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 4 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 4 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 4 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 5 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 3 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 0 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 3 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 3 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 3 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 4 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| i_vec_correct_num_solutions_spptw.push_back( 3 ); |
| i_vec_correct_num_solutions_spptw.push_back( 0 ); |
| i_vec_correct_num_solutions_spptw.push_back( 2 ); |
| i_vec_correct_num_solutions_spptw.push_back( 3 ); |
| i_vec_correct_num_solutions_spptw.push_back( 4 ); |
| i_vec_correct_num_solutions_spptw.push_back( 1 ); |
| for( int s = 0; s < 10; ++s ) |
| for( int t = 0; t < 10; ++t ) |
| BOOST_CHECK( static_cast<int> |
| ( vec_vec_vec_vec_opt_solutions_spptw[s][t].size() ) == |
| i_vec_correct_num_solutions_spptw[10 * s + t] ); |
| |
| // one pareto-optimal solution |
| SPPRC_Example_Graph g2; |
| add_vertex( SPPRC_Example_Graph_Vert_Prop( 0, 0, 1000000000 ), g2 ); |
| add_vertex( SPPRC_Example_Graph_Vert_Prop( 1, 0, 1000000000 ), g2 ); |
| add_vertex( SPPRC_Example_Graph_Vert_Prop( 2, 0, 1000000000 ), g2 ); |
| add_vertex( SPPRC_Example_Graph_Vert_Prop( 3, 0, 1000000000 ), g2 ); |
| add_edge( 0, 1, SPPRC_Example_Graph_Arc_Prop( 0, 1, 1 ), g2 ); |
| add_edge( 0, 2, SPPRC_Example_Graph_Arc_Prop( 1, 2, 1 ), g2 ); |
| add_edge( 1, 3, SPPRC_Example_Graph_Arc_Prop( 2, 3, 1 ), g2 ); |
| add_edge( 2, 3, SPPRC_Example_Graph_Arc_Prop( 3, 1, 1 ), g2 ); |
| std::vector<graph_traits<SPPRC_Example_Graph>::edge_descriptor> opt_solution; |
| spp_spptw_res_cont pareto_opt_rc; |
| r_c_shortest_paths( g2, |
| get( &SPPRC_Example_Graph_Vert_Prop::num, g2 ), |
| get( &SPPRC_Example_Graph_Arc_Prop::num, g2 ), |
| 0, |
| 3, |
| opt_solution, |
| pareto_opt_rc, |
| spp_spptw_res_cont( 0, 0 ), |
| ref_spptw(), |
| dominance_spptw(), |
| std::allocator |
| <r_c_shortest_paths_label |
| <SPPRC_Example_Graph, spp_spptw_res_cont> >(), |
| default_r_c_shortest_paths_visitor() ); |
| |
| BOOST_CHECK(pareto_opt_rc.cost == 3); |
| |
| return 0; |
| } |
