1 // Copyright (C) 2004-2006 The Trustees of Indiana University.
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)
7 // Authors: Douglas Gregor
9 #ifndef BOOST_GRAPH_PARALLEL_DIJKSTRA_HPP
10 #define BOOST_GRAPH_PARALLEL_DIJKSTRA_HPP
12 #ifndef BOOST_GRAPH_USE_MPI
13 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
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>
25 namespace graph { namespace detail {
28 template<typename Lookahead>
29 struct parallel_dijkstra_impl2
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,
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,
45 eager_dijkstra_shortest_paths(g, s, predecessor, distance, lookahead,
46 weight, index_map, color_map, compare,
47 combine, inf, zero, vis);
52 struct parallel_dijkstra_impl2< ::boost::param_not_found >
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,
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,
68 crauser_et_al_shortest_paths(g, s, predecessor, distance, weight,
69 index_map, color_map, compare, combine,
74 template<typename ColorMap>
75 struct parallel_dijkstra_impl
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>
83 run(const DistributedGraph& g,
84 typename graph_traits<DistributedGraph>::vertex_descriptor s,
85 PredecessorMap predecessor, DistanceMap distance,
87 WeightMap weight, IndexMap index_map, ColorMap color_map,
88 Compare compare, Combine combine, DistInf inf, DistZero zero,
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);
98 struct parallel_dijkstra_impl< ::boost::param_not_found >
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>
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)
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);
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);
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>
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,
138 typedef typename graph_traits<DistributedGraph>::vertices_size_type
141 vertices_size_type n = num_vertices(g);
142 std::vector<default_color_type> colors(n, white_color);
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);
149 } } // end namespace graph::detail
152 /** Dijkstra's single-source shortest paths algorithm for distributed
155 * Also implements the heuristics of:
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.
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>
171 dijkstra_shortest_paths
172 (const DistributedGraph& g,
173 typename graph_traits<DistributedGraph>::vertex_descriptor s,
174 PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
176 Compare compare, Combine combine, DistInf inf, DistZero zero,
178 const bgl_named_params<T, Tag, Base>& params
179 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(DistributedGraph,distributed_graph_tag))
181 typedef typename graph_traits<DistributedGraph>::vertices_size_type
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);
193 typedef typename get_param_type< vertex_color_t, bgl_named_params<T, Tag, Base> >::type color_map_type;
195 graph::detail::parallel_dijkstra_impl<color_map_type>
196 ::run(g, s, predecessor, distance,
197 get_param(params, lookahead_t()),
199 get_param(params, vertex_color),
200 compare, combine, inf, zero, vis);
202 } // end namespace boost
204 #endif // BOOST_GRAPH_PARALLEL_DIJKSTRA_HPP