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

source code of boost/boost/graph/dijkstra_shortest_paths_no_color_map.hpp