ceph/src/boost/boost/graph/distributed/dijkstra_shortest_paths.hpp

   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