124 lines
2.9 KiB
C++
124 lines
2.9 KiB
C++
//=======================================================================
|
|
// 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;
|
|
}
|