diff options
Diffstat (limited to 'src/boost/libs/graph/example/r_c_shortest_paths_example.cpp')
| -rw-r--r-- | src/boost/libs/graph/example/r_c_shortest_paths_example.cpp | 332 |
1 files changed, 332 insertions, 0 deletions
diff --git a/src/boost/libs/graph/example/r_c_shortest_paths_example.cpp b/src/boost/libs/graph/example/r_c_shortest_paths_example.cpp new file mode 100644 index 000000000..2d759e73d --- /dev/null +++ b/src/boost/libs/graph/example/r_c_shortest_paths_example.cpp @@ -0,0 +1,332 @@ +// 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; +} |