800 lines
33 KiB
C++
800 lines
33 KiB
C++
// 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)
|
|
|
|
struct spp_spptw_marked_res_cont {
|
|
spp_spptw_marked_res_cont(SPPRC_Example_Graph::vertex_descriptor v, int c = 0, int t = 0 ) : cost( c ), time( t ), marked() {
|
|
marked.insert(v);
|
|
}
|
|
spp_spptw_marked_res_cont& operator=( const spp_spptw_marked_res_cont& other )
|
|
{
|
|
if( this == &other )
|
|
return *this;
|
|
this->~spp_spptw_marked_res_cont();
|
|
new( this ) spp_spptw_marked_res_cont( other );
|
|
return *this;
|
|
}
|
|
int cost;
|
|
int time;
|
|
std::set<SPPRC_Example_Graph::vertex_descriptor> marked;
|
|
};
|
|
|
|
bool operator==( const spp_spptw_marked_res_cont& res_cont_1,
|
|
const spp_spptw_marked_res_cont& res_cont_2 )
|
|
{
|
|
return res_cont_1.cost == res_cont_2.cost
|
|
&& res_cont_1.time == res_cont_2.time
|
|
&& res_cont_1.marked == res_cont_2.marked;
|
|
}
|
|
|
|
bool operator<( const spp_spptw_marked_res_cont& res_cont_1,
|
|
const spp_spptw_marked_res_cont& res_cont_2 )
|
|
{
|
|
if( res_cont_1.cost > res_cont_2.cost || res_cont_1.time > res_cont_2.time) {
|
|
return false;
|
|
}
|
|
|
|
if( !std::includes( res_cont_2.marked.begin(),
|
|
res_cont_2.marked.end(),
|
|
res_cont_1.marked.begin(),
|
|
res_cont_1.marked.end() ) ) {
|
|
return false;
|
|
}
|
|
|
|
if( res_cont_1.cost == res_cont_2.cost ) {
|
|
return res_cont_1.time < res_cont_2.time;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
class ref_spptw_marked {
|
|
public:
|
|
inline bool operator()(const SPPRC_Example_Graph &g,
|
|
spp_spptw_marked_res_cont &new_cont,
|
|
const spp_spptw_marked_res_cont &old_cont,
|
|
graph_traits
|
|
<SPPRC_Example_Graph>::edge_descriptor ed) const {
|
|
const graph_traits <SPPRC_Example_Graph>::vertex_descriptor dest = target(ed, g);
|
|
|
|
if(old_cont.marked.find(dest) != old_cont.marked.end()) {
|
|
return false;
|
|
}
|
|
|
|
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 )[dest];
|
|
new_cont.cost = old_cont.cost + arc_prop.cost;
|
|
new_cont.marked = old_cont.marked;
|
|
new_cont.marked.insert(dest);
|
|
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;
|
|
}
|
|
};
|
|
|
|
class dominance_spptw_marked {
|
|
public:
|
|
inline bool operator()( const spp_spptw_marked_res_cont& res_cont_1,
|
|
const spp_spptw_marked_res_cont& res_cont_2 ) const {
|
|
return res_cont_1.time <= res_cont_2.time
|
|
&& res_cont_1.cost <= res_cont_2.cost
|
|
&& std::includes( res_cont_1.marked.begin(),
|
|
res_cont_1.marked.end(),
|
|
res_cont_2.marked.begin(),
|
|
res_cont_2.marked.end() );
|
|
}
|
|
};
|
|
|
|
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);
|
|
|
|
SPPRC_Example_Graph g3;
|
|
add_vertex( SPPRC_Example_Graph_Vert_Prop( 0, 0, 1000 ), g3 );
|
|
add_vertex( SPPRC_Example_Graph_Vert_Prop( 1, 0, 1000 ), g3 );
|
|
add_vertex( SPPRC_Example_Graph_Vert_Prop( 2, 0, 974 ), g3 );
|
|
add_vertex( SPPRC_Example_Graph_Vert_Prop( 3, 0, 972 ), g3 );
|
|
add_vertex( SPPRC_Example_Graph_Vert_Prop( 4, 0, 967 ), g3 );
|
|
add_vertex( SPPRC_Example_Graph_Vert_Prop( 5, 678, 801 ), g3 );
|
|
add_edge( 0, 2, SPPRC_Example_Graph_Arc_Prop( 0, 0, 16 ), g3 );
|
|
add_edge( 0, 3, SPPRC_Example_Graph_Arc_Prop( 1, 0, 18 ), g3 );
|
|
add_edge( 0, 4, SPPRC_Example_Graph_Arc_Prop( 2, 0, 23 ), g3 );
|
|
add_edge( 0, 5, SPPRC_Example_Graph_Arc_Prop( 3, 0, 25 ), g3 );
|
|
add_edge( 2, 3, SPPRC_Example_Graph_Arc_Prop( 4, 0, 33 ), g3 );
|
|
add_edge( 2, 4, SPPRC_Example_Graph_Arc_Prop( 5, 0, 15 ), g3 );
|
|
add_edge( 2, 5, SPPRC_Example_Graph_Arc_Prop( 6, 0, 33 ), g3 );
|
|
add_edge( 2, 1, SPPRC_Example_Graph_Arc_Prop( 7, 0, 16 ), g3 );
|
|
add_edge( 3, 2, SPPRC_Example_Graph_Arc_Prop( 8, 0, 33 ), g3 );
|
|
add_edge( 3, 4, SPPRC_Example_Graph_Arc_Prop( 9, 0, 35 ), g3 );
|
|
add_edge( 3, 5, SPPRC_Example_Graph_Arc_Prop( 10, 0, 21 ), g3 );
|
|
add_edge( 3, 1, SPPRC_Example_Graph_Arc_Prop( 11, 0, 18 ), g3 );
|
|
add_edge( 4, 2, SPPRC_Example_Graph_Arc_Prop( 12, 0, 15 ), g3 );
|
|
add_edge( 4, 3, SPPRC_Example_Graph_Arc_Prop( 13, 0, 35 ), g3 );
|
|
add_edge( 4, 5, SPPRC_Example_Graph_Arc_Prop( 14, 0, 25 ), g3 );
|
|
add_edge( 4, 1, SPPRC_Example_Graph_Arc_Prop( 15, 0, 23 ), g3 );
|
|
add_edge( 5, 2, SPPRC_Example_Graph_Arc_Prop( 16, 0, 33 ), g3 );
|
|
add_edge( 5, 3, SPPRC_Example_Graph_Arc_Prop( 17, 0, 21 ), g3 );
|
|
add_edge( 5, 4, SPPRC_Example_Graph_Arc_Prop( 18, 0, 25 ), g3 );
|
|
add_edge( 5, 1, SPPRC_Example_Graph_Arc_Prop( 19, 0, 25 ), g3 );
|
|
|
|
std::vector<std::vector<graph_traits<SPPRC_Example_Graph>::edge_descriptor> >
|
|
pareto_opt_marked_solutions;
|
|
std::vector<spp_spptw_marked_res_cont> pareto_opt_marked_resource_containers;
|
|
|
|
graph_traits<SPPRC_Example_Graph>::vertex_descriptor g3_source = 0, g3_target = 1;
|
|
r_c_shortest_paths( g3,
|
|
get( &SPPRC_Example_Graph_Vert_Prop::num, g3 ),
|
|
get( &SPPRC_Example_Graph_Arc_Prop::num, g3 ),
|
|
g3_source,
|
|
g3_target,
|
|
pareto_opt_marked_solutions,
|
|
pareto_opt_marked_resource_containers,
|
|
spp_spptw_marked_res_cont( 0, 0, 0 ),
|
|
ref_spptw_marked(),
|
|
dominance_spptw_marked(),
|
|
std::allocator
|
|
<r_c_shortest_paths_label
|
|
<SPPRC_Example_Graph, spp_spptw_marked_res_cont> >(),
|
|
default_r_c_shortest_paths_visitor() );
|
|
|
|
BOOST_CHECK(!pareto_opt_marked_solutions.empty());
|
|
std::vector<std::vector<graph_traits<SPPRC_Example_Graph>::edge_descriptor> >::const_iterator path_it, path_end_it;
|
|
for (path_it = pareto_opt_marked_solutions.begin(), path_end_it = pareto_opt_marked_solutions.end(); path_it != path_end_it; ++path_it) {
|
|
const std::vector<graph_traits<SPPRC_Example_Graph>::edge_descriptor> &path = *path_it;
|
|
BOOST_CHECK(!path.empty());
|
|
|
|
const graph_traits<SPPRC_Example_Graph>::edge_descriptor front = path.front();
|
|
BOOST_CHECK(boost::target(front, g3) == g3_target);
|
|
|
|
std::vector<graph_traits<SPPRC_Example_Graph>::edge_descriptor>::const_iterator edge_it, edge_it_end;
|
|
graph_traits<SPPRC_Example_Graph>::edge_descriptor prev_edge = front;
|
|
|
|
for(edge_it = path.begin() + 1, edge_it_end = path.end(); edge_it != edge_it_end; ++edge_it) {
|
|
graph_traits<SPPRC_Example_Graph>::edge_descriptor edge = *edge_it;
|
|
|
|
graph_traits<SPPRC_Example_Graph>::vertex_descriptor prev_end, current_end;
|
|
prev_end = boost::source(prev_edge, g3);
|
|
current_end = boost::target(edge, g3);
|
|
BOOST_CHECK(prev_end == current_end);
|
|
|
|
prev_edge = edge;
|
|
}
|
|
|
|
const graph_traits<SPPRC_Example_Graph>::edge_descriptor back = path.back();
|
|
BOOST_CHECK(boost::source(back, g3) == g3_source);
|
|
}
|
|
|
|
return 0;
|
|
}
|