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