1 | //======================================================================= |
2 | // Copyright (c) 2013 Alberto Santini |
3 | // Author: Alberto Santini <alberto@santini.in> |
4 | // |
5 | // Distributed under the Boost Software License, Version 1.0. (See |
6 | // accompanying file LICENSE_1_0.txt or copy at |
7 | // http://www.boost.org/LICENSE_1_0.txt) |
8 | //======================================================================= |
9 | |
10 | #include <boost/config.hpp> |
11 | |
12 | #ifdef BOOST_MSVC |
13 | // Without disabling this we get hard errors about initialialized pointers: |
14 | #pragma warning(disable : 4703) |
15 | #endif |
16 | |
17 | #include <boost/graph/graph_traits.hpp> |
18 | #include <boost/graph/adjacency_list.hpp> |
19 | #include <boost/graph/r_c_shortest_paths.hpp> |
20 | #include <boost/graph/iteration_macros.hpp> |
21 | #include <vector> |
22 | #include <memory> |
23 | |
24 | using std::allocator; |
25 | using std::vector; |
26 | using namespace boost; |
27 | |
28 | class VertexProperty |
29 | { |
30 | public: |
31 | int property1; |
32 | int property2; |
33 | int id; |
34 | VertexProperty() {} |
35 | VertexProperty(const int property1, const int property2) |
36 | : property1(property1), property2(property2) |
37 | { |
38 | } |
39 | }; |
40 | |
41 | class EdgeProperty |
42 | { |
43 | public: |
44 | int cost; |
45 | int id; |
46 | EdgeProperty() {} |
47 | EdgeProperty(const int cost) : cost(cost) {} |
48 | }; |
49 | |
50 | typedef adjacency_list< listS, listS, bidirectionalS, VertexProperty, |
51 | EdgeProperty > |
52 | Graph; |
53 | typedef graph_traits< Graph >::vertex_descriptor Vertex; |
54 | typedef graph_traits< Graph >::edge_descriptor Edge; |
55 | |
56 | class ResourceCont |
57 | { |
58 | public: |
59 | int res; |
60 | ResourceCont(const int res = 5) : res(res) {} |
61 | bool operator==(const ResourceCont& rc) const { return (res == rc.res); } |
62 | bool operator<(const ResourceCont& rc) const { return (res > rc.res); } |
63 | }; |
64 | |
65 | class LabelExt |
66 | { |
67 | public: |
68 | bool operator()(const Graph& g, ResourceCont& rc, |
69 | const ResourceCont& old_rc, Edge e) const |
70 | { |
71 | rc.res = old_rc.res - g[e].cost; |
72 | return (rc.res > 0); |
73 | } |
74 | }; |
75 | |
76 | class LabelDom |
77 | { |
78 | public: |
79 | bool operator()(const ResourceCont& rc1, const ResourceCont& rc2) const |
80 | { |
81 | return (rc1 == rc2 || rc1 < rc2); |
82 | } |
83 | }; |
84 | |
85 | int main() |
86 | { |
87 | VertexProperty vp1(1, 1); |
88 | VertexProperty vp2(5, 9); |
89 | VertexProperty vp3(4, 3); |
90 | EdgeProperty e12(1); |
91 | EdgeProperty e23(2); |
92 | |
93 | Graph g; |
94 | |
95 | Vertex v1 = add_vertex(g_&: g); |
96 | g[v1] = vp1; |
97 | Vertex v2 = add_vertex(g_&: g); |
98 | g[v2] = vp2; |
99 | Vertex v3 = add_vertex(g_&: g); |
100 | g[v3] = vp3; |
101 | |
102 | add_edge(u: v1, v: v2, p: e12, g_&: g); |
103 | add_edge(u: v2, v: v3, p: e23, g_&: g); |
104 | |
105 | int index = 0; |
106 | BGL_FORALL_VERTICES(v, g, Graph) { g[v].id = index++; } |
107 | index = 0; |
108 | BGL_FORALL_EDGES(e, g, Graph) { g[e].id = index++; } |
109 | |
110 | typedef vector< vector< Edge > > OptPath; |
111 | typedef vector< ResourceCont > ParetoOpt; |
112 | |
113 | OptPath op; |
114 | ParetoOpt ol; |
115 | |
116 | r_c_shortest_paths(g, vertex_index_map: get(p: &VertexProperty::id, g), |
117 | edge_index_map: get(p: &EdgeProperty::id, g), s: v1, t: v2, pareto_optimal_solutions&: op, pareto_optimal_resource_containers&: ol, rc: ResourceCont(5), ref: LabelExt(), |
118 | dominance: LabelDom(), |
119 | la: allocator< r_c_shortest_paths_label< Graph, ResourceCont > >(), |
120 | vis: default_r_c_shortest_paths_visitor()); |
121 | |
122 | return 0; |
123 | } |
124 | |