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

   1 // (c) Copyright Juergen Hunold 2012
   2 // Use, modification and distribution is subject to the Boost Software
   3 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   4 // http://www.boost.org/LICENSE_1_0.txt)
   5
   6 #include <boost/graph/adjacency_list.hpp>
   7 #include <boost/graph/dijkstra_shortest_paths.hpp>
   8 #include <boost/graph/filtered_graph.hpp>
   9
  10 namespace boost
  11 {
  12
  13 enum edge_info_t
  14 {
  15     edge_info = 114
  16 };
  17
  18 BOOST_INSTALL_PROPERTY(edge, info);
  19 }
  20
  21 template < typename EdgeInfo, typename Directed > class Graph
  22 {
  23 public:
  24     typedef boost::property< boost::edge_info_t, EdgeInfo > tEdge_property;
  25
  26     typedef boost::adjacency_list< boost::setS, boost::vecS, Directed,
  27         boost::no_property, tEdge_property >
  28         tGraph;
  29
  30     typedef typename boost::graph_traits< tGraph >::vertex_descriptor tNode;
  31     typedef typename boost::graph_traits< tGraph >::edge_descriptor tEdge;
  32
  33 protected:
  34     tGraph m_Graph;
  35 };
  36
  37 class DataEdge;
  38
  39 class UndirectedGraph : public Graph< DataEdge*, boost::undirectedS >
  40 {
  41 public:
  42     template < class Evaluator, class Filter >
  43     void dijkstra(Evaluator const&, Filter const&) const;
  44 };
  45
  46 template < typename Graph, typename Derived >
  47 struct Evaluator : public boost::put_get_helper< int, Derived >
  48 {
  49     typedef int value_type;
  50     typedef typename Graph::tEdge key_type;
  51     typedef int reference;
  52     typedef boost::readable_property_map_tag category;
  53
  54     explicit Evaluator(Graph const* pGraph);
  55 };
  56
  57 template < typename Graph >
  58 struct LengthEvaluator : public Evaluator< Graph, LengthEvaluator< Graph > >
  59 {
  60     explicit LengthEvaluator(Graph const* pGraph);
  61
  62     typedef typename Evaluator< Graph, LengthEvaluator< Graph > >::reference
  63         reference;
  64     typedef typename Evaluator< Graph, LengthEvaluator< Graph > >::key_type
  65         key_type;
  66
  67     virtual reference operator[](key_type const& edge) const;
  68 };
  69
  70 template < class Graph > struct EdgeFilter
  71 {
  72     typedef typename Graph::tEdge key_type;
  73
  74     EdgeFilter();
  75
  76     explicit EdgeFilter(Graph const*);
  77
  78     bool operator()(key_type const&) const;
  79
  80 private:
  81     const Graph* m_pGraph;
  82 };
  83
  84 template < class Evaluator, class Filter >
  85 void UndirectedGraph::dijkstra(
  86     Evaluator const& rEvaluator, Filter const& rFilter) const
  87 {
  88     tNode nodeSource = vertex(0, m_Graph);
  89
  90     std::vector< tNode > predecessors(num_vertices(m_Graph));
  91
  92     boost::filtered_graph< tGraph, Filter > filteredGraph(m_Graph, rFilter);
  93
  94     boost::dijkstra_shortest_paths(filteredGraph, nodeSource,
  95         boost::predecessor_map(&predecessors[0]).weight_map(rEvaluator));
  96 }
  97
  98 // explicit instantiation
  99 template void UndirectedGraph::dijkstra(
 100     LengthEvaluator< UndirectedGraph > const&,
 101     EdgeFilter< UndirectedGraph > const&) const;
 102
 103 int main(int, char**)
 104 {
 105     return 0;
 106 } // Tests above will fail to compile if anything is broken