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 runboost::graph::detail::parallel_dijkstra_impl237 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 runboost::graph::detail::parallel_dijkstra_impl260 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 runboost::graph::detail::parallel_dijkstra_impl83 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 run_implboost::graph::detail::parallel_dijkstra_impl107 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 runboost::graph::detail::parallel_dijkstra_impl130 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 dijkstra_shortest_paths(const DistributedGraph & g,typename graph_traits<DistributedGraph>::vertex_descriptor s,PredecessorMap predecessor,DistanceMap distance,WeightMap weight,IndexMap index_map,Compare compare,Combine combine,DistInf inf,DistZero zero,DijkstraVisitor vis,const bgl_named_params<T,Tag,Base> & params BOOST_GRAPH_ENABLE_IF_MODELS_PARM (DistributedGraph,distributed_graph_tag))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 205