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
10namespace boost
11{
12
13enum edge_info_t
14{
15 edge_info = 114
16};
17
18BOOST_INSTALL_PROPERTY(edge, info);
19}
20
21template < typename EdgeInfo, typename Directed > class Graph
22{
23public:
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
33protected:
34 tGraph m_Graph;
35};
36
37class DataEdge;
38
39class UndirectedGraph : public Graph< DataEdge*, boost::undirectedS >
40{
41public:
42 template < class Evaluator, class Filter >
43 void dijkstra(Evaluator const&, Filter const&) const;
44};
45
46template < typename Graph, typename Derived >
47struct 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
57template < typename Graph >
58struct 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
70template < 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
80private:
81 const Graph* m_pGraph;
82};
83
84template < class Evaluator, class Filter >
85void 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
99template void UndirectedGraph::dijkstra(
100 LengthEvaluator< UndirectedGraph > const&,
101 EdgeFilter< UndirectedGraph > const&) const;
102
103int main(int, char**)
104{
105 return 0;
106} // Tests above will fail to compile if anything is broken
107

source code of boost/libs/graph/test/filtered_graph_properties_dijkstra.cpp