Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 09:37:17 

0001 // Copyright (C) 2004-2006 The Trustees of Indiana University.
0002 
0003 // Use, modification and distribution is subject to the Boost Software
0004 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006 
0007 //  Authors: Douglas Gregor
0008 //           Andrew Lumsdaine
0009 #ifndef BOOST_GRAPH_PARALLEL_DIJKSTRA_HPP
0010 #define BOOST_GRAPH_PARALLEL_DIJKSTRA_HPP
0011 
0012 #ifndef BOOST_GRAPH_USE_MPI
0013 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
0014 #endif
0015 
0016 #include <boost/graph/dijkstra_shortest_paths.hpp>
0017 #include <boost/graph/overloading.hpp>
0018 #include <boost/graph/distributed/concepts.hpp>
0019 #include <boost/graph/parallel/properties.hpp>
0020 #include <boost/graph/distributed/crauser_et_al_shortest_paths.hpp>
0021 #include <boost/graph/distributed/eager_dijkstra_shortest_paths.hpp>
0022 
0023 namespace boost {
0024 
0025   namespace graph { namespace detail {
0026 
0027     
0028     template<typename Lookahead>
0029     struct parallel_dijkstra_impl2
0030     {
0031       template<typename DistributedGraph, typename DijkstraVisitor,
0032                typename PredecessorMap, typename DistanceMap, 
0033                typename WeightMap, typename IndexMap, typename ColorMap, 
0034                typename Compare, typename Combine, typename DistInf, 
0035                typename DistZero>
0036       static void 
0037       run(const DistributedGraph& g,
0038           typename graph_traits<DistributedGraph>::vertex_descriptor s,
0039           PredecessorMap predecessor, DistanceMap distance, 
0040           typename property_traits<DistanceMap>::value_type lookahead,
0041           WeightMap weight, IndexMap index_map, ColorMap color_map,
0042           Compare compare, Combine combine, DistInf inf, DistZero zero,
0043           DijkstraVisitor vis)
0044       {
0045         eager_dijkstra_shortest_paths(g, s, predecessor, distance, lookahead,
0046                                       weight, index_map, color_map, compare,
0047                                       combine, inf, zero, vis);
0048       }
0049     };
0050 
0051     template<>
0052     struct parallel_dijkstra_impl2< ::boost::param_not_found >
0053     {
0054       template<typename DistributedGraph, typename DijkstraVisitor,
0055                typename PredecessorMap, typename DistanceMap, 
0056                typename WeightMap, typename IndexMap, typename ColorMap, 
0057                typename Compare, typename Combine, typename DistInf, 
0058                typename DistZero>
0059       static void 
0060       run(const DistributedGraph& g,
0061           typename graph_traits<DistributedGraph>::vertex_descriptor s,
0062           PredecessorMap predecessor, DistanceMap distance, 
0063           ::boost::param_not_found,
0064           WeightMap weight, IndexMap index_map, ColorMap color_map,
0065           Compare compare, Combine combine, DistInf inf, DistZero zero,
0066           DijkstraVisitor vis)
0067       {
0068         crauser_et_al_shortest_paths(g, s, predecessor, distance, weight,
0069                                      index_map, color_map, compare, combine,
0070                                      inf, zero, vis);
0071       }
0072     };
0073 
0074     template<typename ColorMap>
0075     struct parallel_dijkstra_impl
0076     {
0077       template<typename DistributedGraph, typename DijkstraVisitor,
0078                typename PredecessorMap, typename DistanceMap, 
0079                typename Lookahead, typename WeightMap, typename IndexMap,
0080                typename Compare, typename Combine, 
0081                typename DistInf, typename DistZero>
0082       static void 
0083       run(const DistributedGraph& g,
0084           typename graph_traits<DistributedGraph>::vertex_descriptor s,
0085           PredecessorMap predecessor, DistanceMap distance, 
0086           Lookahead lookahead,
0087           WeightMap weight, IndexMap index_map, ColorMap color_map,
0088           Compare compare, Combine combine, DistInf inf, DistZero zero,
0089           DijkstraVisitor vis)
0090       {
0091         graph::detail::parallel_dijkstra_impl2<Lookahead>
0092           ::run(g, s, predecessor, distance, lookahead, weight, index_map,
0093                 color_map, compare, combine, inf, zero, vis);
0094       }
0095     };
0096     
0097     template<>
0098     struct parallel_dijkstra_impl< ::boost::param_not_found >
0099     {
0100     private:
0101       template<typename DistributedGraph, typename DijkstraVisitor,
0102                typename PredecessorMap, typename DistanceMap, 
0103                typename Lookahead, typename WeightMap, typename IndexMap,
0104                typename ColorMap, typename Compare, typename Combine, 
0105                typename DistInf, typename DistZero>
0106       static void 
0107       run_impl(const DistributedGraph& g,
0108                typename graph_traits<DistributedGraph>::vertex_descriptor s,
0109                PredecessorMap predecessor, DistanceMap distance, 
0110                Lookahead lookahead, WeightMap weight, IndexMap index_map, 
0111                ColorMap color_map, Compare compare, Combine combine, 
0112                DistInf inf, DistZero zero, DijkstraVisitor vis)
0113       {
0114         BGL_FORALL_VERTICES_T(u, g, DistributedGraph)
0115           BGL_FORALL_OUTEDGES_T(u, e, g, DistributedGraph)
0116             local_put(color_map, target(e, g), white_color);
0117 
0118         graph::detail::parallel_dijkstra_impl2<Lookahead>
0119           ::run(g, s, predecessor, distance, lookahead, weight, index_map,
0120                 color_map, compare, combine, inf, zero, vis);
0121       }
0122 
0123     public:
0124       template<typename DistributedGraph, typename DijkstraVisitor,
0125                typename PredecessorMap, typename DistanceMap, 
0126                typename Lookahead, typename WeightMap, typename IndexMap,
0127                typename Compare, typename Combine, 
0128                typename DistInf, typename DistZero>
0129       static void 
0130       run(const DistributedGraph& g,
0131           typename graph_traits<DistributedGraph>::vertex_descriptor s,
0132           PredecessorMap predecessor, DistanceMap distance, 
0133           Lookahead lookahead, WeightMap weight, IndexMap index_map, 
0134           ::boost::param_not_found,
0135           Compare compare, Combine combine, DistInf inf, DistZero zero,
0136           DijkstraVisitor vis)
0137       {
0138         typedef typename graph_traits<DistributedGraph>::vertices_size_type
0139           vertices_size_type;
0140 
0141         vertices_size_type n = num_vertices(g);
0142         std::vector<default_color_type> colors(n, white_color);
0143 
0144         run_impl(g, s, predecessor, distance, lookahead, weight, index_map,
0145                  make_iterator_property_map(colors.begin(), index_map),
0146                  compare, combine, inf, zero, vis);
0147       }
0148     };
0149   } } // end namespace graph::detail
0150 
0151 
0152   /** Dijkstra's single-source shortest paths algorithm for distributed
0153    * graphs.
0154    *
0155    * Also implements the heuristics of:
0156    *
0157    *   Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter
0158    *   Sanders. A Parallelization of Dijkstra's Shortest Path
0159    *   Algorithm. In Lubos Brim, Jozef Gruska, and Jiri Zlatuska,
0160    *   editors, Mathematical Foundations of Computer Science (MFCS),
0161    *   volume 1450 of Lecture Notes in Computer Science, pages
0162    *   722--731, 1998. Springer.
0163    */
0164   template<typename DistributedGraph, typename DijkstraVisitor,
0165            typename PredecessorMap, typename DistanceMap,
0166            typename WeightMap, typename IndexMap, typename Compare,
0167            typename Combine, typename DistInf, typename DistZero,
0168            typename T, typename Tag, typename Base>
0169   inline
0170   void
0171   dijkstra_shortest_paths
0172     (const DistributedGraph& g,
0173      typename graph_traits<DistributedGraph>::vertex_descriptor s,
0174      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
0175      IndexMap index_map,
0176      Compare compare, Combine combine, DistInf inf, DistZero zero,
0177      DijkstraVisitor vis,
0178      const bgl_named_params<T, Tag, Base>& params
0179      BOOST_GRAPH_ENABLE_IF_MODELS_PARM(DistributedGraph,distributed_graph_tag))
0180   {
0181     typedef typename graph_traits<DistributedGraph>::vertices_size_type
0182       vertices_size_type;
0183 
0184     // Build a distributed property map for vertex colors, if we need it
0185     bool use_default_color_map 
0186       = is_default_param(get_param(params, vertex_color));
0187     vertices_size_type n = use_default_color_map? num_vertices(g) : 1;
0188     std::vector<default_color_type> color(n, white_color);
0189     typedef iterator_property_map<std::vector<default_color_type>::iterator,
0190                                   IndexMap> DefColorMap;
0191     DefColorMap color_map(color.begin(), index_map);
0192 
0193     typedef typename get_param_type< vertex_color_t, bgl_named_params<T, Tag, Base> >::type color_map_type;
0194 
0195     graph::detail::parallel_dijkstra_impl<color_map_type>
0196       ::run(g, s, predecessor, distance, 
0197             get_param(params, lookahead_t()),
0198             weight, index_map,
0199             get_param(params, vertex_color),
0200             compare, combine, inf, zero, vis);
0201   }
0202 } // end namespace boost
0203 
0204 #endif // BOOST_GRAPH_PARALLEL_DIJKSTRA_HPP
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!