786 lines
32 KiB
C++
786 lines
32 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/core/lightweight_test.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 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_TEST(
|
|
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_TEST(
|
|
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_TEST(
|
|
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_TEST(
|
|
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_TEST(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_TEST(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_TEST(!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_TEST(!path.empty());
|
|
|
|
const graph_traits< SPPRC_Example_Graph >::edge_descriptor front
|
|
= path.front();
|
|
BOOST_TEST(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_TEST(prev_end == current_end);
|
|
|
|
prev_edge = edge;
|
|
}
|
|
|
|
const graph_traits< SPPRC_Example_Graph >::edge_descriptor back
|
|
= path.back();
|
|
BOOST_TEST(boost::source(back, g3) == g3_source);
|
|
}
|
|
|
|
return boost::report_errors();
|
|
}
|