Chris@16: // Copyright (C) 2004-2006 The Trustees of Indiana University.
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software
Chris@16: // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: //  Authors: Douglas Gregor
Chris@16: //           Andrew Lumsdaine
Chris@16: #ifndef BOOST_GRAPH_PARALLEL_DIJKSTRA_HPP
Chris@16: #define BOOST_GRAPH_PARALLEL_DIJKSTRA_HPP
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_USE_MPI
Chris@16: #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
Chris@16: #endif
Chris@16: 
Chris@16: #include <boost/graph/dijkstra_shortest_paths.hpp>
Chris@16: #include <boost/graph/overloading.hpp>
Chris@16: #include <boost/graph/distributed/concepts.hpp>
Chris@16: #include <boost/graph/parallel/properties.hpp>
Chris@16: #include <boost/graph/distributed/crauser_et_al_shortest_paths.hpp>
Chris@16: #include <boost/graph/distributed/eager_dijkstra_shortest_paths.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   namespace graph { namespace detail {
Chris@16: 
Chris@16:     
Chris@16:     template<typename Lookahead>
Chris@16:     struct parallel_dijkstra_impl2
Chris@16:     {
Chris@16:       template<typename DistributedGraph, typename DijkstraVisitor,
Chris@16:                typename PredecessorMap, typename DistanceMap, 
Chris@16:                typename WeightMap, typename IndexMap, typename ColorMap, 
Chris@16:                typename Compare, typename Combine, typename DistInf, 
Chris@16:                typename DistZero>
Chris@16:       static void 
Chris@16:       run(const DistributedGraph& g,
Chris@16:           typename graph_traits<DistributedGraph>::vertex_descriptor s,
Chris@16:           PredecessorMap predecessor, DistanceMap distance, 
Chris@16:           typename property_traits<DistanceMap>::value_type lookahead,
Chris@16:           WeightMap weight, IndexMap index_map, ColorMap color_map,
Chris@16:           Compare compare, Combine combine, DistInf inf, DistZero zero,
Chris@16:           DijkstraVisitor vis)
Chris@16:       {
Chris@16:         eager_dijkstra_shortest_paths(g, s, predecessor, distance, lookahead,
Chris@16:                                       weight, index_map, color_map, compare,
Chris@16:                                       combine, inf, zero, vis);
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     template<>
Chris@16:     struct parallel_dijkstra_impl2< ::boost::param_not_found >
Chris@16:     {
Chris@16:       template<typename DistributedGraph, typename DijkstraVisitor,
Chris@16:                typename PredecessorMap, typename DistanceMap, 
Chris@16:                typename WeightMap, typename IndexMap, typename ColorMap, 
Chris@16:                typename Compare, typename Combine, typename DistInf, 
Chris@16:                typename DistZero>
Chris@16:       static void 
Chris@16:       run(const DistributedGraph& g,
Chris@16:           typename graph_traits<DistributedGraph>::vertex_descriptor s,
Chris@16:           PredecessorMap predecessor, DistanceMap distance, 
Chris@16:           ::boost::param_not_found,
Chris@16:           WeightMap weight, IndexMap index_map, ColorMap color_map,
Chris@16:           Compare compare, Combine combine, DistInf inf, DistZero zero,
Chris@16:           DijkstraVisitor vis)
Chris@16:       {
Chris@16:         crauser_et_al_shortest_paths(g, s, predecessor, distance, weight,
Chris@16:                                      index_map, color_map, compare, combine,
Chris@16:                                      inf, zero, vis);
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     template<typename ColorMap>
Chris@16:     struct parallel_dijkstra_impl
Chris@16:     {
Chris@16:       template<typename DistributedGraph, typename DijkstraVisitor,
Chris@16:                typename PredecessorMap, typename DistanceMap, 
Chris@16:                typename Lookahead, typename WeightMap, typename IndexMap,
Chris@16:                typename Compare, typename Combine, 
Chris@16:                typename DistInf, typename DistZero>
Chris@16:       static void 
Chris@16:       run(const DistributedGraph& g,
Chris@16:           typename graph_traits<DistributedGraph>::vertex_descriptor s,
Chris@16:           PredecessorMap predecessor, DistanceMap distance, 
Chris@16:           Lookahead lookahead,
Chris@16:           WeightMap weight, IndexMap index_map, ColorMap color_map,
Chris@16:           Compare compare, Combine combine, DistInf inf, DistZero zero,
Chris@16:           DijkstraVisitor vis)
Chris@16:       {
Chris@16:         graph::detail::parallel_dijkstra_impl2<Lookahead>
Chris@16:           ::run(g, s, predecessor, distance, lookahead, weight, index_map,
Chris@16:                 color_map, compare, combine, inf, zero, vis);
Chris@16:       }
Chris@16:     };
Chris@16:     
Chris@16:     template<>
Chris@16:     struct parallel_dijkstra_impl< ::boost::param_not_found >
Chris@16:     {
Chris@16:     private:
Chris@16:       template<typename DistributedGraph, typename DijkstraVisitor,
Chris@16:                typename PredecessorMap, typename DistanceMap, 
Chris@16:                typename Lookahead, typename WeightMap, typename IndexMap,
Chris@16:                typename ColorMap, typename Compare, typename Combine, 
Chris@16:                typename DistInf, typename DistZero>
Chris@16:       static void 
Chris@16:       run_impl(const DistributedGraph& g,
Chris@16:                typename graph_traits<DistributedGraph>::vertex_descriptor s,
Chris@16:                PredecessorMap predecessor, DistanceMap distance, 
Chris@16:                Lookahead lookahead, WeightMap weight, IndexMap index_map, 
Chris@16:                ColorMap color_map, Compare compare, Combine combine, 
Chris@16:                DistInf inf, DistZero zero, DijkstraVisitor vis)
Chris@16:       {
Chris@16:         BGL_FORALL_VERTICES_T(u, g, DistributedGraph)
Chris@16:           BGL_FORALL_OUTEDGES_T(u, e, g, DistributedGraph)
Chris@16:             local_put(color_map, target(e, g), white_color);
Chris@16: 
Chris@16:         graph::detail::parallel_dijkstra_impl2<Lookahead>
Chris@16:           ::run(g, s, predecessor, distance, lookahead, weight, index_map,
Chris@16:                 color_map, compare, combine, inf, zero, vis);
Chris@16:       }
Chris@16: 
Chris@16:     public:
Chris@16:       template<typename DistributedGraph, typename DijkstraVisitor,
Chris@16:                typename PredecessorMap, typename DistanceMap, 
Chris@16:                typename Lookahead, typename WeightMap, typename IndexMap,
Chris@16:                typename Compare, typename Combine, 
Chris@16:                typename DistInf, typename DistZero>
Chris@16:       static void 
Chris@16:       run(const DistributedGraph& g,
Chris@16:           typename graph_traits<DistributedGraph>::vertex_descriptor s,
Chris@16:           PredecessorMap predecessor, DistanceMap distance, 
Chris@16:           Lookahead lookahead, WeightMap weight, IndexMap index_map, 
Chris@16:           ::boost::param_not_found,
Chris@16:           Compare compare, Combine combine, DistInf inf, DistZero zero,
Chris@16:           DijkstraVisitor vis)
Chris@16:       {
Chris@16:         typedef typename graph_traits<DistributedGraph>::vertices_size_type
Chris@16:           vertices_size_type;
Chris@16: 
Chris@16:         vertices_size_type n = num_vertices(g);
Chris@16:         std::vector<default_color_type> colors(n, white_color);
Chris@16: 
Chris@16:         run_impl(g, s, predecessor, distance, lookahead, weight, index_map,
Chris@16:                  make_iterator_property_map(colors.begin(), index_map),
Chris@16:                  compare, combine, inf, zero, vis);
Chris@16:       }
Chris@16:     };
Chris@16:   } } // end namespace graph::detail
Chris@16: 
Chris@16: 
Chris@16:   /** Dijkstra's single-source shortest paths algorithm for distributed
Chris@16:    * graphs.
Chris@16:    *
Chris@16:    * Also implements the heuristics of:
Chris@16:    *
Chris@16:    *   Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter
Chris@16:    *   Sanders. A Parallelization of Dijkstra's Shortest Path
Chris@16:    *   Algorithm. In Lubos Brim, Jozef Gruska, and Jiri Zlatuska,
Chris@16:    *   editors, Mathematical Foundations of Computer Science (MFCS),
Chris@16:    *   volume 1450 of Lecture Notes in Computer Science, pages
Chris@16:    *   722--731, 1998. Springer.
Chris@16:    */
Chris@16:   template<typename DistributedGraph, typename DijkstraVisitor,
Chris@16:            typename PredecessorMap, typename DistanceMap,
Chris@16:            typename WeightMap, typename IndexMap, typename Compare,
Chris@16:            typename Combine, typename DistInf, typename DistZero,
Chris@16:            typename T, typename Tag, typename Base>
Chris@16:   inline
Chris@16:   void
Chris@16:   dijkstra_shortest_paths
Chris@16:     (const DistributedGraph& g,
Chris@16:      typename graph_traits<DistributedGraph>::vertex_descriptor s,
Chris@16:      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
Chris@16:      IndexMap index_map,
Chris@16:      Compare compare, Combine combine, DistInf inf, DistZero zero,
Chris@16:      DijkstraVisitor vis,
Chris@16:      const bgl_named_params<T, Tag, Base>& params
Chris@16:      BOOST_GRAPH_ENABLE_IF_MODELS_PARM(DistributedGraph,distributed_graph_tag))
Chris@16:   {
Chris@16:     typedef typename graph_traits<DistributedGraph>::vertices_size_type
Chris@16:       vertices_size_type;
Chris@16: 
Chris@16:     // Build a distributed property map for vertex colors, if we need it
Chris@16:     bool use_default_color_map 
Chris@16:       = is_default_param(get_param(params, vertex_color));
Chris@16:     vertices_size_type n = use_default_color_map? num_vertices(g) : 1;
Chris@16:     std::vector<default_color_type> color(n, white_color);
Chris@16:     typedef iterator_property_map<std::vector<default_color_type>::iterator,
Chris@16:                                   IndexMap> DefColorMap;
Chris@16:     DefColorMap color_map(color.begin(), index_map);
Chris@16: 
Chris@16:     typedef typename get_param_type< vertex_color_t, bgl_named_params<T, Tag, Base> >::type color_map_type;
Chris@16: 
Chris@16:     graph::detail::parallel_dijkstra_impl<color_map_type>
Chris@16:       ::run(g, s, predecessor, distance, 
Chris@16:             get_param(params, lookahead_t()),
Chris@16:             weight, index_map,
Chris@16:             get_param(params, vertex_color),
Chris@16:             compare, combine, inf, zero, vis);
Chris@16:   }
Chris@16: } // end namespace boost
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_PARALLEL_DIJKSTRA_HPP