]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright (C) 2004-2006 The Trustees of Indiana University. |
2 | ||
3 | // Use, modification and distribution is subject to the Boost Software | |
4 | // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
5 | // http://www.boost.org/LICENSE_1_0.txt) | |
6 | ||
7 | // Authors: Douglas Gregor | |
8 | // Andrew Lumsdaine | |
9 | #ifndef BOOST_GRAPH_PARALLEL_DIJKSTRA_HPP | |
10 | #define BOOST_GRAPH_PARALLEL_DIJKSTRA_HPP | |
11 | ||
12 | #ifndef BOOST_GRAPH_USE_MPI | |
13 | #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included" | |
14 | #endif | |
15 | ||
16 | #include <boost/graph/dijkstra_shortest_paths.hpp> | |
17 | #include <boost/graph/overloading.hpp> | |
18 | #include <boost/graph/distributed/concepts.hpp> | |
19 | #include <boost/graph/parallel/properties.hpp> | |
20 | #include <boost/graph/distributed/crauser_et_al_shortest_paths.hpp> | |
21 | #include <boost/graph/distributed/eager_dijkstra_shortest_paths.hpp> | |
22 | ||
23 | namespace boost { | |
24 | ||
25 | namespace graph { namespace detail { | |
26 | ||
27 | ||
28 | template<typename Lookahead> | |
29 | struct parallel_dijkstra_impl2 | |
30 | { | |
31 | template<typename DistributedGraph, typename DijkstraVisitor, | |
32 | typename PredecessorMap, typename DistanceMap, | |
33 | typename WeightMap, typename IndexMap, typename ColorMap, | |
34 | typename Compare, typename Combine, typename DistInf, | |
35 | typename DistZero> | |
36 | static void | |
37 | run(const DistributedGraph& g, | |
38 | typename graph_traits<DistributedGraph>::vertex_descriptor s, | |
39 | PredecessorMap predecessor, DistanceMap distance, | |
40 | typename property_traits<DistanceMap>::value_type lookahead, | |
41 | WeightMap weight, IndexMap index_map, ColorMap color_map, | |
42 | Compare compare, Combine combine, DistInf inf, DistZero zero, | |
43 | DijkstraVisitor vis) | |
44 | { | |
45 | eager_dijkstra_shortest_paths(g, s, predecessor, distance, lookahead, | |
46 | weight, index_map, color_map, compare, | |
47 | combine, inf, zero, vis); | |
48 | } | |
49 | }; | |
50 | ||
51 | template<> | |
52 | struct parallel_dijkstra_impl2< ::boost::param_not_found > | |
53 | { | |
54 | template<typename DistributedGraph, typename DijkstraVisitor, | |
55 | typename PredecessorMap, typename DistanceMap, | |
56 | typename WeightMap, typename IndexMap, typename ColorMap, | |
57 | typename Compare, typename Combine, typename DistInf, | |
58 | typename DistZero> | |
59 | static void | |
60 | run(const DistributedGraph& g, | |
61 | typename graph_traits<DistributedGraph>::vertex_descriptor s, | |
62 | PredecessorMap predecessor, DistanceMap distance, | |
63 | ::boost::param_not_found, | |
64 | WeightMap weight, IndexMap index_map, ColorMap color_map, | |
65 | Compare compare, Combine combine, DistInf inf, DistZero zero, | |
66 | DijkstraVisitor vis) | |
67 | { | |
68 | crauser_et_al_shortest_paths(g, s, predecessor, distance, weight, | |
69 | index_map, color_map, compare, combine, | |
70 | inf, zero, vis); | |
71 | } | |
72 | }; | |
73 | ||
74 | template<typename ColorMap> | |
75 | struct parallel_dijkstra_impl | |
76 | { | |
77 | template<typename DistributedGraph, typename DijkstraVisitor, | |
78 | typename PredecessorMap, typename DistanceMap, | |
79 | typename Lookahead, typename WeightMap, typename IndexMap, | |
80 | typename Compare, typename Combine, | |
81 | typename DistInf, typename DistZero> | |
82 | static void | |
83 | run(const DistributedGraph& g, | |
84 | typename graph_traits<DistributedGraph>::vertex_descriptor s, | |
85 | PredecessorMap predecessor, DistanceMap distance, | |
86 | Lookahead lookahead, | |
87 | WeightMap weight, IndexMap index_map, ColorMap color_map, | |
88 | Compare compare, Combine combine, DistInf inf, DistZero zero, | |
89 | DijkstraVisitor vis) | |
90 | { | |
91 | graph::detail::parallel_dijkstra_impl2<Lookahead> | |
92 | ::run(g, s, predecessor, distance, lookahead, weight, index_map, | |
93 | color_map, compare, combine, inf, zero, vis); | |
94 | } | |
95 | }; | |
96 | ||
97 | template<> | |
98 | struct parallel_dijkstra_impl< ::boost::param_not_found > | |
99 | { | |
100 | private: | |
101 | template<typename DistributedGraph, typename DijkstraVisitor, | |
102 | typename PredecessorMap, typename DistanceMap, | |
103 | typename Lookahead, typename WeightMap, typename IndexMap, | |
104 | typename ColorMap, typename Compare, typename Combine, | |
105 | typename DistInf, typename DistZero> | |
106 | static void | |
107 | run_impl(const DistributedGraph& g, | |
108 | typename graph_traits<DistributedGraph>::vertex_descriptor s, | |
109 | PredecessorMap predecessor, DistanceMap distance, | |
110 | Lookahead lookahead, WeightMap weight, IndexMap index_map, | |
111 | ColorMap color_map, Compare compare, Combine combine, | |
112 | DistInf inf, DistZero zero, DijkstraVisitor vis) | |
113 | { | |
114 | BGL_FORALL_VERTICES_T(u, g, DistributedGraph) | |
115 | BGL_FORALL_OUTEDGES_T(u, e, g, DistributedGraph) | |
116 | local_put(color_map, target(e, g), white_color); | |
117 | ||
118 | graph::detail::parallel_dijkstra_impl2<Lookahead> | |
119 | ::run(g, s, predecessor, distance, lookahead, weight, index_map, | |
120 | color_map, compare, combine, inf, zero, vis); | |
121 | } | |
122 | ||
123 | public: | |
124 | template<typename DistributedGraph, typename DijkstraVisitor, | |
125 | typename PredecessorMap, typename DistanceMap, | |
126 | typename Lookahead, typename WeightMap, typename IndexMap, | |
127 | typename Compare, typename Combine, | |
128 | typename DistInf, typename DistZero> | |
129 | static void | |
130 | run(const DistributedGraph& g, | |
131 | typename graph_traits<DistributedGraph>::vertex_descriptor s, | |
132 | PredecessorMap predecessor, DistanceMap distance, | |
133 | Lookahead lookahead, WeightMap weight, IndexMap index_map, | |
134 | ::boost::param_not_found, | |
135 | Compare compare, Combine combine, DistInf inf, DistZero zero, | |
136 | DijkstraVisitor vis) | |
137 | { | |
138 | typedef typename graph_traits<DistributedGraph>::vertices_size_type | |
139 | vertices_size_type; | |
140 | ||
141 | vertices_size_type n = num_vertices(g); | |
142 | std::vector<default_color_type> colors(n, white_color); | |
143 | ||
144 | run_impl(g, s, predecessor, distance, lookahead, weight, index_map, | |
145 | make_iterator_property_map(colors.begin(), index_map), | |
146 | compare, combine, inf, zero, vis); | |
147 | } | |
148 | }; | |
149 | } } // end namespace graph::detail | |
150 | ||
151 | ||
152 | /** Dijkstra's single-source shortest paths algorithm for distributed | |
153 | * graphs. | |
154 | * | |
155 | * Also implements the heuristics of: | |
156 | * | |
157 | * Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter | |
158 | * Sanders. A Parallelization of Dijkstra's Shortest Path | |
159 | * Algorithm. In Lubos Brim, Jozef Gruska, and Jiri Zlatuska, | |
160 | * editors, Mathematical Foundations of Computer Science (MFCS), | |
161 | * volume 1450 of Lecture Notes in Computer Science, pages | |
162 | * 722--731, 1998. Springer. | |
163 | */ | |
164 | template<typename DistributedGraph, typename DijkstraVisitor, | |
165 | typename PredecessorMap, typename DistanceMap, | |
166 | typename WeightMap, typename IndexMap, typename Compare, | |
167 | typename Combine, typename DistInf, typename DistZero, | |
168 | typename T, typename Tag, typename Base> | |
169 | inline | |
170 | void | |
171 | dijkstra_shortest_paths | |
172 | (const DistributedGraph& g, | |
173 | typename graph_traits<DistributedGraph>::vertex_descriptor s, | |
174 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight, | |
175 | IndexMap index_map, | |
176 | Compare compare, Combine combine, DistInf inf, DistZero zero, | |
177 | DijkstraVisitor vis, | |
178 | const bgl_named_params<T, Tag, Base>& params | |
179 | BOOST_GRAPH_ENABLE_IF_MODELS_PARM(DistributedGraph,distributed_graph_tag)) | |
180 | { | |
181 | typedef typename graph_traits<DistributedGraph>::vertices_size_type | |
182 | vertices_size_type; | |
183 | ||
184 | // Build a distributed property map for vertex colors, if we need it | |
185 | bool use_default_color_map | |
186 | = is_default_param(get_param(params, vertex_color)); | |
187 | vertices_size_type n = use_default_color_map? num_vertices(g) : 1; | |
188 | std::vector<default_color_type> color(n, white_color); | |
189 | typedef iterator_property_map<std::vector<default_color_type>::iterator, | |
190 | IndexMap> DefColorMap; | |
191 | DefColorMap color_map(color.begin(), index_map); | |
192 | ||
193 | typedef typename get_param_type< vertex_color_t, bgl_named_params<T, Tag, Base> >::type color_map_type; | |
194 | ||
195 | graph::detail::parallel_dijkstra_impl<color_map_type> | |
196 | ::run(g, s, predecessor, distance, | |
197 | get_param(params, lookahead_t()), | |
198 | weight, index_map, | |
199 | get_param(params, vertex_color), | |
200 | compare, combine, inf, zero, vis); | |
201 | } | |
202 | } // end namespace boost | |
203 | ||
204 | #endif // BOOST_GRAPH_PARALLEL_DIJKSTRA_HPP |