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;
VertexProperty()34 VertexProperty() {}
VertexProperty(const int property1,const int property2)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;
EdgeProperty()46 EdgeProperty() {}
EdgeProperty(const int cost)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;
ResourceCont(const int res=5)60 ResourceCont(const int res = 5) : res(res) {}
operator ==(const ResourceCont & rc) const61 bool operator==(const ResourceCont& rc) const { return (res == rc.res); }
operator <(const ResourceCont & rc) const62 bool operator<(const ResourceCont& rc) const { return (res > rc.res); }
63 };
64
65 class LabelExt
66 {
67 public:
operator ()(const Graph & g,ResourceCont & rc,const ResourceCont & old_rc,Edge e) const68 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:
operator ()(const ResourceCont & rc1,const ResourceCont & rc2) const79 bool operator()(const ResourceCont& rc1, const ResourceCont& rc2) const
80 {
81 return (rc1 == rc2 || rc1 < rc2);
82 }
83 };
84
main()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);
96 g[v1] = vp1;
97 Vertex v2 = add_vertex(g);
98 g[v2] = vp2;
99 Vertex v3 = add_vertex(g);
100 g[v3] = vp3;
101
102 add_edge(v1, v2, e12, g);
103 add_edge(v2, v3, e23, 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, get(&VertexProperty::id, g),
117 get(&EdgeProperty::id, g), v1, v2, op, ol, ResourceCont(5), LabelExt(),
118 LabelDom(),
119 allocator< r_c_shortest_paths_label< Graph, ResourceCont > >(),
120 default_r_c_shortest_paths_visitor());
121
122 return 0;
123 }
124