ceph/src/boost/libs/graph/test/rcsp_custom_vertex_id.cpp

   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::vector;
  25 using std::allocator;
  26 using namespace boost;
  27
  28 class VertexProperty {
  29 public:
  30   int property1;
  31   int property2;
  32   int id;
  33   VertexProperty() {}
  34   VertexProperty(const int property1, const int property2) : property1(property1), property2(property2) {}
  35 };
  36
  37 class EdgeProperty {
  38 public:
  39   int cost;
  40   int id;
  41   EdgeProperty() {}
  42   EdgeProperty(const int cost) : cost(cost) {}
  43 };
  44
  45 typedef adjacency_list<listS, listS, bidirectionalS, VertexProperty, EdgeProperty> Graph;
  46 typedef graph_traits<Graph>::vertex_descriptor Vertex;
  47 typedef graph_traits<Graph>::edge_descriptor Edge;
  48
  49 class ResourceCont {
  50 public:
  51   int res;
  52   ResourceCont(const int res = 5) : res(res) {}
  53   bool operator==(const ResourceCont& rc) const { return (res == rc.res); }
  54   bool operator<(const ResourceCont& rc) const { return (res > rc.res); }
  55 };
  56
  57 class LabelExt {
  58 public:
  59   bool operator()(const Graph& g, ResourceCont& rc, const ResourceCont& old_rc, Edge e) const {
  60     rc.res = old_rc.res - g[e].cost;
  61     return (rc.res > 0);
  62   }
  63 };
  64
  65 class LabelDom {
  66 public:
  67   bool operator()(const ResourceCont& rc1, const ResourceCont& rc2) const {
  68     return (rc1 == rc2 || rc1 < rc2);
  69   }
  70 };
  71
  72 int main() {
  73   VertexProperty vp1(1, 1);
  74   VertexProperty vp2(5, 9);
  75   VertexProperty vp3(4, 3);
  76   EdgeProperty e12(1);
  77   EdgeProperty e23(2);
  78
  79   Graph g;
  80
  81   Vertex v1 = add_vertex(g); g[v1] = vp1;
  82   Vertex v2 = add_vertex(g); g[v2] = vp2;
  83   Vertex v3 = add_vertex(g); g[v3] = vp3;
  84
  85   add_edge(v1, v2, e12, g);
  86   add_edge(v2, v3, e23, g);
  87
  88   int index = 0;
  89   BGL_FORALL_VERTICES(v, g, Graph) {
  90     g[v].id = index++;
  91   }
  92   index = 0;
  93   BGL_FORALL_EDGES(e, g, Graph) {
  94     g[e].id = index++;
  95   }
  96
  97   typedef vector<vector<Edge> > OptPath;
  98   typedef vector<ResourceCont> ParetoOpt;
  99
 100   OptPath op;
 101   ParetoOpt ol;
 102
 103   r_c_shortest_paths( g,
 104                       get(&VertexProperty::id, g),
 105                       get(&EdgeProperty::id, g),
 106                       v1,
 107                       v2,
 108                       op,
 109                       ol,
 110                       ResourceCont(5),
 111                       LabelExt(),
 112                       LabelDom(),
 113                       allocator<r_c_shortest_paths_label<Graph, ResourceCont> >(),
 114                       default_r_c_shortest_paths_visitor());
 115
 116   return 0;
 117 }