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 | |
21 | namespace 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 | |