1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Copyright 2009 Trustees of Indiana University.
4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Michael Hansen
5 //
6 // Distributed under the Boost Software License, Version 1.0. (See
7 // accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //=======================================================================
10
11 #ifndef BOOST_GRAPH_DIJKSTRA_NO_COLOR_MAP_HPP
12 #define BOOST_GRAPH_DIJKSTRA_NO_COLOR_MAP_HPP
13
14 #include <boost/pending/indirect_cmp.hpp>
15 #include <boost/graph/relax.hpp>
16 #include <boost/graph/detail/d_ary_heap.hpp>
17 #include <boost/graph/dijkstra_shortest_paths.hpp>
18 #include <boost/graph/iteration_macros.hpp>
19
20 namespace boost
21 {
22
23 // No init version
24 template < typename Graph, typename DijkstraVisitor, typename PredecessorMap,
25 typename DistanceMap, typename WeightMap, typename VertexIndexMap,
26 typename DistanceCompare, typename DistanceWeightCombine,
27 typename DistanceInfinity, typename DistanceZero >
dijkstra_shortest_paths_no_color_map_no_init(const Graph & graph,typename graph_traits<Graph>::vertex_descriptor start_vertex,PredecessorMap predecessor_map,DistanceMap distance_map,WeightMap weight_map,VertexIndexMap index_map,DistanceCompare distance_compare,DistanceWeightCombine distance_weight_combine,DistanceInfinity distance_infinity,DistanceZero distance_zero,DijkstraVisitor visitor)28 void dijkstra_shortest_paths_no_color_map_no_init(const Graph& graph,
29 typename graph_traits< Graph >::vertex_descriptor start_vertex,
30 PredecessorMap predecessor_map, DistanceMap distance_map,
31 WeightMap weight_map, VertexIndexMap index_map,
32 DistanceCompare distance_compare,
33 DistanceWeightCombine distance_weight_combine,
34 DistanceInfinity distance_infinity, DistanceZero distance_zero,
35 DijkstraVisitor visitor)
36 {
37 typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
38 typedef typename property_traits< DistanceMap >::value_type Distance;
39
40 typedef indirect_cmp< DistanceMap, DistanceCompare >
41 DistanceIndirectCompare;
42 DistanceIndirectCompare distance_indirect_compare(
43 distance_map, distance_compare);
44
45 // Default - use d-ary heap (d = 4)
46 typedef detail::vertex_property_map_generator< Graph, VertexIndexMap,
47 std::size_t >
48 IndexInHeapMapHelper;
49 typedef typename IndexInHeapMapHelper::type IndexInHeapMap;
50 typedef d_ary_heap_indirect< Vertex, 4, IndexInHeapMap, DistanceMap,
51 DistanceCompare >
52 VertexQueue;
53
54 boost::scoped_array< std::size_t > index_in_heap_map_holder;
55 IndexInHeapMap index_in_heap = IndexInHeapMapHelper::build(
56 graph, index_map, index_in_heap_map_holder);
57 VertexQueue vertex_queue(distance_map, index_in_heap, distance_compare);
58
59 // Add vertex to the queue
60 vertex_queue.push(start_vertex);
61
62 // Starting vertex will always be the first discovered vertex
63 visitor.discover_vertex(start_vertex, graph);
64
65 while (!vertex_queue.empty())
66 {
67 Vertex min_vertex = vertex_queue.top();
68 vertex_queue.pop();
69
70 visitor.examine_vertex(min_vertex, graph);
71
72 // Check if any other vertices can be reached
73 Distance min_vertex_distance = get(distance_map, min_vertex);
74
75 if (!distance_compare(min_vertex_distance, distance_infinity))
76 {
77 // This is the minimum vertex, so all other vertices are unreachable
78 return;
79 }
80
81 // Examine neighbors of min_vertex
82 BGL_FORALL_OUTEDGES_T(min_vertex, current_edge, graph, Graph)
83 {
84 visitor.examine_edge(current_edge, graph);
85
86 // Check if the edge has a negative weight
87 if (distance_compare(get(weight_map, current_edge), distance_zero))
88 {
89 boost::throw_exception(negative_edge());
90 }
91
92 // Extract the neighboring vertex and get its distance
93 Vertex neighbor_vertex = target(current_edge, graph);
94 Distance neighbor_vertex_distance
95 = get(distance_map, neighbor_vertex);
96 bool is_neighbor_undiscovered = !distance_compare(
97 neighbor_vertex_distance, distance_infinity);
98
99 // Attempt to relax the edge
100 bool was_edge_relaxed
101 = relax_target(current_edge, graph, weight_map, predecessor_map,
102 distance_map, distance_weight_combine, distance_compare);
103
104 if (was_edge_relaxed)
105 {
106 visitor.edge_relaxed(current_edge, graph);
107 if (is_neighbor_undiscovered)
108 {
109 visitor.discover_vertex(neighbor_vertex, graph);
110 vertex_queue.push(neighbor_vertex);
111 }
112 else
113 {
114 vertex_queue.update(neighbor_vertex);
115 }
116 }
117 else
118 {
119 visitor.edge_not_relaxed(current_edge, graph);
120 }
121
122 } // end out edge iteration
123
124 visitor.finish_vertex(min_vertex, graph);
125 } // end while queue not empty
126 }
127
128 // Full init version
129 template < typename Graph, typename DijkstraVisitor, typename PredecessorMap,
130 typename DistanceMap, typename WeightMap, typename VertexIndexMap,
131 typename DistanceCompare, typename DistanceWeightCombine,
132 typename DistanceInfinity, typename DistanceZero >
dijkstra_shortest_paths_no_color_map(const Graph & graph,typename graph_traits<Graph>::vertex_descriptor start_vertex,PredecessorMap predecessor_map,DistanceMap distance_map,WeightMap weight_map,VertexIndexMap index_map,DistanceCompare distance_compare,DistanceWeightCombine distance_weight_combine,DistanceInfinity distance_infinity,DistanceZero distance_zero,DijkstraVisitor visitor)133 void dijkstra_shortest_paths_no_color_map(const Graph& graph,
134 typename graph_traits< Graph >::vertex_descriptor start_vertex,
135 PredecessorMap predecessor_map, DistanceMap distance_map,
136 WeightMap weight_map, VertexIndexMap index_map,
137 DistanceCompare distance_compare,
138 DistanceWeightCombine distance_weight_combine,
139 DistanceInfinity distance_infinity, DistanceZero distance_zero,
140 DijkstraVisitor visitor)
141 {
142 // Initialize vertices
143 BGL_FORALL_VERTICES_T(current_vertex, graph, Graph)
144 {
145 visitor.initialize_vertex(current_vertex, graph);
146
147 // Default all distances to infinity
148 put(distance_map, current_vertex, distance_infinity);
149
150 // Default all vertex predecessors to the vertex itself
151 put(predecessor_map, current_vertex, current_vertex);
152 }
153
154 // Set distance for start_vertex to zero
155 put(distance_map, start_vertex, distance_zero);
156
157 // Pass everything on to the no_init version
158 dijkstra_shortest_paths_no_color_map_no_init(graph, start_vertex,
159 predecessor_map, distance_map, weight_map, index_map, distance_compare,
160 distance_weight_combine, distance_infinity, distance_zero, visitor);
161 }
162
163 namespace detail
164 {
165
166 // Handle defaults for PredecessorMap, DistanceCompare,
167 // DistanceWeightCombine, DistanceInfinity and DistanceZero
168 template < typename Graph, typename DistanceMap, typename WeightMap,
169 typename VertexIndexMap, typename Params >
dijkstra_no_color_map_dispatch2(const Graph & graph,typename graph_traits<Graph>::vertex_descriptor start_vertex,DistanceMap distance_map,WeightMap weight_map,VertexIndexMap index_map,const Params & params)170 inline void dijkstra_no_color_map_dispatch2(const Graph& graph,
171 typename graph_traits< Graph >::vertex_descriptor start_vertex,
172 DistanceMap distance_map, WeightMap weight_map,
173 VertexIndexMap index_map, const Params& params)
174 {
175 // Default for predecessor map
176 dummy_property_map predecessor_map;
177
178 typedef
179 typename property_traits< DistanceMap >::value_type DistanceType;
180 DistanceType inf = choose_param(get_param(params, distance_inf_t()),
181 (std::numeric_limits< DistanceType >::max)());
182 dijkstra_shortest_paths_no_color_map(graph, start_vertex,
183 choose_param(
184 get_param(params, vertex_predecessor), predecessor_map),
185 distance_map, weight_map, index_map,
186 choose_param(get_param(params, distance_compare_t()),
187 std::less< DistanceType >()),
188 choose_param(get_param(params, distance_combine_t()),
189 std::plus< DistanceType >()),
190 inf,
191 choose_param(get_param(params, distance_zero_t()), DistanceType()),
192 choose_param(get_param(params, graph_visitor),
193 make_dijkstra_visitor(null_visitor())));
194 }
195
196 template < typename Graph, typename DistanceMap, typename WeightMap,
197 typename IndexMap, typename Params >
dijkstra_no_color_map_dispatch1(const Graph & graph,typename graph_traits<Graph>::vertex_descriptor start_vertex,DistanceMap distance_map,WeightMap weight_map,IndexMap index_map,const Params & params)198 inline void dijkstra_no_color_map_dispatch1(const Graph& graph,
199 typename graph_traits< Graph >::vertex_descriptor start_vertex,
200 DistanceMap distance_map, WeightMap weight_map, IndexMap index_map,
201 const Params& params)
202 {
203 // Default for distance map
204 typedef typename property_traits< WeightMap >::value_type DistanceType;
205 typename std::vector< DistanceType >::size_type vertex_count
206 = is_default_param(distance_map) ? num_vertices(graph) : 1;
207
208 std::vector< DistanceType > default_distance_map(vertex_count);
209
210 detail::dijkstra_no_color_map_dispatch2(graph, start_vertex,
211 choose_param(distance_map,
212 make_iterator_property_map(default_distance_map.begin(),
213 index_map, default_distance_map[0])),
214 weight_map, index_map, params);
215 }
216 } // namespace detail
217
218 // Named parameter version
219 template < typename Graph, typename Param, typename Tag, typename Rest >
dijkstra_shortest_paths_no_color_map(const Graph & graph,typename graph_traits<Graph>::vertex_descriptor start_vertex,const bgl_named_params<Param,Tag,Rest> & params)220 inline void dijkstra_shortest_paths_no_color_map(const Graph& graph,
221 typename graph_traits< Graph >::vertex_descriptor start_vertex,
222 const bgl_named_params< Param, Tag, Rest >& params)
223 {
224 // Default for edge weight and vertex index map is to ask for them
225 // from the graph. Default for the visitor is null_visitor.
226 detail::dijkstra_no_color_map_dispatch1(graph, start_vertex,
227 get_param(params, vertex_distance),
228 choose_const_pmap(get_param(params, edge_weight), graph, edge_weight),
229 choose_const_pmap(get_param(params, vertex_index), graph, vertex_index),
230 params);
231 }
232
233 } // namespace boost
234
235 #endif // BOOST_GRAPH_DIJKSTRA_NO_COLOR_MAP_HPP
236