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