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(n: 0, m_Graph); |
89 | |
90 | std::vector< tNode > predecessors(num_vertices(g_: 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(p: &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 |
107 | |