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 enum edge_info_t { edge_info = 114 };
13
14 BOOST_INSTALL_PROPERTY( edge, info );
15 }
16
17 template< typename EdgeInfo,
18 typename Directed >
19 class Graph
20 {
21 public:
22 typedef boost::property< boost::edge_info_t, EdgeInfo > tEdge_property;
23
24 typedef boost::adjacency_list< boost::setS,
25 boost::vecS,
26 Directed,
27 boost::no_property,
28 tEdge_property > 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
35 tGraph m_Graph;
36 };
37
38 class DataEdge;
39
40 class UndirectedGraph
41 : public Graph< DataEdge*,
42 boost::undirectedS >
43 {
44 public:
45
46 template< class Evaluator, class Filter >
47 void dijkstra( Evaluator const&,
48 Filter const& ) const;
49 };
50
51 template< typename Graph, typename Derived >
52 struct Evaluator : public boost::put_get_helper< int, Derived >
53 {
54 typedef int value_type;
55 typedef typename Graph::tEdge key_type;
56 typedef int reference;
57 typedef boost::readable_property_map_tag category;
58
59 explicit Evaluator( Graph const* pGraph );
60 };
61
62
63 template< typename Graph >
64 struct LengthEvaluator : public Evaluator< Graph, LengthEvaluator<Graph> >
65 {
66 explicit LengthEvaluator( Graph const* pGraph );
67
68 typedef typename Evaluator<Graph, LengthEvaluator<Graph> >::reference reference;
69 typedef typename Evaluator<Graph, LengthEvaluator<Graph> >::key_type key_type;
70
71 virtual reference operator[] ( key_type const& edge ) const;
72 };
73
74 template< class Graph >
75 struct EdgeFilter
76 {
77 typedef typename Graph::tEdge key_type;
78
79 EdgeFilter();
80
81 explicit EdgeFilter( Graph const*);
82
83 bool operator()( key_type const& ) const;
84
85 private:
86 const Graph* m_pGraph;
87 };
88
89
90 template< class Evaluator, class Filter >
91 void
dijkstra(Evaluator const & rEvaluator,Filter const & rFilter) const92 UndirectedGraph::dijkstra( Evaluator const& rEvaluator,
93 Filter const& rFilter ) const
94 {
95 tNode nodeSource = vertex(0, m_Graph);
96
97 std::vector< tNode > predecessors( num_vertices(m_Graph) );
98
99 boost::filtered_graph< tGraph, Filter > filteredGraph( m_Graph, rFilter );
100
101 boost::dijkstra_shortest_paths( filteredGraph,
102 nodeSource,
103 boost::predecessor_map( &predecessors[0] )
104 .weight_map( rEvaluator ) );
105 }
106
107 // explicit instantiation
108 template void UndirectedGraph::dijkstra( LengthEvaluator<UndirectedGraph> const&,
109 EdgeFilter<UndirectedGraph> const& ) const;
110
main(int,char **)111 int main(int, char**) {return 0;} // Tests above will fail to compile if anything is broken
112