Mercurial > hg > vamp-build-and-test

annotate DEPENDENCIES/generic/include/boost/graph/distributed/dijkstra_shortest_paths.hpp @ 133:4acb5d8d80b6 tip

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