123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353 |
- // 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)
- // Example use of the resource-constrained shortest paths algorithm.
- #include <boost/config.hpp>
- #ifdef BOOST_MSVC
- # pragma warning(disable: 4267)
- #endif
- #include <boost/graph/adjacency_list.hpp>
- #include <boost/graph/r_c_shortest_paths.hpp>
- #include <iostream>
- 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)
- // example graph structure and cost from
- // http://www.boost.org/libs/graph/example/dijkstra-example.cpp
- enum nodes { A, B, C, D, E };
- char name[] = "ABCDE";
- int main()
- {
- SPPRC_Example_Graph g;
- add_vertex( SPPRC_Example_Graph_Vert_Prop( A, 0, 0 ), g );
- add_vertex( SPPRC_Example_Graph_Vert_Prop( B, 5, 20 ), g );
- add_vertex( SPPRC_Example_Graph_Vert_Prop( C, 6, 10 ), g );
- add_vertex( SPPRC_Example_Graph_Vert_Prop( D, 3, 12 ), g );
- add_vertex( SPPRC_Example_Graph_Vert_Prop( E, 0, 100 ), g );
- add_edge( A, C, SPPRC_Example_Graph_Arc_Prop( 0, 1, 5 ), g );
- add_edge( B, B, SPPRC_Example_Graph_Arc_Prop( 1, 2, 5 ), g );
- add_edge( B, D, SPPRC_Example_Graph_Arc_Prop( 2, 1, 2 ), g );
- add_edge( B, E, SPPRC_Example_Graph_Arc_Prop( 3, 2, 7 ), g );
- add_edge( C, B, SPPRC_Example_Graph_Arc_Prop( 4, 7, 3 ), g );
- add_edge( C, D, SPPRC_Example_Graph_Arc_Prop( 5, 3, 8 ), g );
- add_edge( D, E, SPPRC_Example_Graph_Arc_Prop( 6, 1, 3 ), g );
- add_edge( E, A, SPPRC_Example_Graph_Arc_Prop( 7, 1, 5 ), g );
- add_edge( E, B, SPPRC_Example_Graph_Arc_Prop( 8, 1, 4 ), g );
- // the unique shortest path from A to E in the dijkstra-example.cpp is
- // A -> C -> D -> E
- // its length is 5
- // the following code also yields this result
- // with the above time windows, this path is infeasible
- // now, there are two shortest paths that are also feasible with respect to
- // the vertex time windows:
- // A -> C -> B -> D -> E and
- // A -> C -> B -> E
- // however, the latter has a longer total travel time and is therefore not
- // pareto-optimal, i.e., it is dominated by the former path
- // therefore, the code below returns only the former path
- // spp without resource constraints
- graph_traits<SPPRC_Example_Graph>::vertex_descriptor s = A;
- graph_traits<SPPRC_Example_Graph>::vertex_descriptor t = E;
- 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;
- 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() );
- std::cout << "SPP without resource constraints:" << std::endl;
- std::cout << "Number of optimal solutions: ";
- std::cout << static_cast<int>( opt_solutions.size() ) << std::endl;
- for( int i = 0; i < static_cast<int>( opt_solutions.size() ); ++i )
- {
- std::cout << "The " << i << "th shortest path from A to E is: ";
- std::cout << std::endl;
- for( int j = static_cast<int>( opt_solutions[i].size() ) - 1; j >= 0; --j )
- std::cout << name[source( opt_solutions[i][j], g )] << std::endl;
- std::cout << "E" << std::endl;
- std::cout << "Length: " << pareto_opt_rcs_no_rc[i].cost << std::endl;
- }
- std::cout << std::endl;
- // 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;
- 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,
- 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() );
- std::cout << "SPP with time windows:" << std::endl;
- std::cout << "Number of optimal solutions: ";
- std::cout << static_cast<int>( opt_solutions.size() ) << std::endl;
- for( int i = 0; i < static_cast<int>( opt_solutions.size() ); ++i )
- {
- std::cout << "The " << i << "th shortest path from A to E is: ";
- std::cout << std::endl;
- for( int j = static_cast<int>( opt_solutions_spptw[i].size() ) - 1;
- j >= 0;
- --j )
- std::cout << name[source( opt_solutions_spptw[i][j], g )] << std::endl;
- std::cout << "E" << std::endl;
- std::cout << "Length: " << pareto_opt_rcs_spptw[i].cost << std::endl;
- std::cout << "Time: " << pareto_opt_rcs_spptw[i].time << std::endl;
- }
- // utility function check_r_c_path example
- std::cout << std::endl;
- 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, 0 ),
- 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 );
- if( !b_is_a_path_at_all )
- std::cout << "Not a path." << std::endl;
- if( !b_feasible )
- std::cout << "Not a feasible path." << std::endl;
- if( !b_correctly_extended )
- std::cout << "Not correctly extended." << std::endl;
- if( b_is_a_path_at_all && b_feasible && b_correctly_extended )
- {
- std::cout << "Actual final resource levels:" << std::endl;
- std::cout << "Length: " << actual_final_resource_levels.cost << std::endl;
- std::cout << "Time: " << actual_final_resource_levels.time << std::endl;
- std::cout << "OK." << std::endl;
- }
- return 0;
- }
|