graph/distributed/crauser_et_al_shortest_paths.hpp

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
0010 /**************************************************************************
0011  * This source file implements the variation on Dijkstra's algorithm      *
0012  * presented by Crauser et al. in:                                        *
0013  *                                                                        *
0014  *   Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter              *
0015  *   Sanders. A Parallelization of Dijkstra's Shortest Path               *
0016  *   Algorithm. In Lubos Brim, Jozef Gruska, and Jiri Zlatuska,          *
0017  *   editors, Mathematical Foundations of Computer Science (MFCS),        *
0018  *   volume 1450 of Lecture Notes in Computer Science, pages              *
0019  *   722--731, 1998. Springer.                                            *
0020  *                                                                        *
0021  * This implementation is, however, restricted to the distributed-memory  *
0022  * case, where the work is distributed by virtue of the vertices being    *
0023  * distributed. In a shared-memory (single address space) context, we     *
0024  * would want to add an explicit balancing step.                          *
0025  **************************************************************************/
0026 #ifndef BOOST_GRAPH_CRAUSER_ET_AL_SHORTEST_PATHS_HPP
0027 #define BOOST_GRAPH_CRAUSER_ET_AL_SHORTEST_PATHS_HPP
0028
0029 #ifndef BOOST_GRAPH_USE_MPI
0030 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
0031 #endif
0032
0033 #include <boost/assert.hpp>
0034 #include <boost/graph/distributed/detail/dijkstra_shortest_paths.hpp>
0035 #include <boost/graph/parallel/algorithm.hpp>
0036 #include <functional>
0037 #include <boost/graph/iteration_macros.hpp>
0038 #include <boost/property_map/property_map_iterator.hpp>
0039 #include <boost/type_traits/is_same.hpp>
0040 #include <boost/algorithm/minmax_element.hpp>
0041 #include <boost/property_map/parallel/caching_property_map.hpp>
0042 #include <boost/pending/indirect_cmp.hpp>
0043 #include <boost/graph/distributed/detail/remote_update_set.hpp>
0044 #include <vector>
0045 #include <boost/graph/breadth_first_search.hpp>
0046 #include <boost/graph/dijkstra_shortest_paths.hpp>
0047 #include <boost/graph/parallel/container_traits.hpp>
0048 #include <boost/pending/relaxed_heap.hpp>
0049
0050 #ifdef PBGL_ACCOUNTING
0051 #  include <boost/graph/accounting.hpp>
0052 #  include <numeric>
0053 #endif // PBGL_ACCOUNTING
0054
0055 #ifdef MUTABLE_QUEUE
0056 #    include <boost/pending/mutable_queue.hpp>
0057 #endif
0058
0059 namespace boost { namespace graph { namespace distributed {
0060
0061 #ifdef PBGL_ACCOUNTING
0062 struct crauser_et_al_shortest_paths_stats_t
0063 {
0064   /* Total wall-clock time used by the algorithm.*/
0065   accounting::time_type execution_time;
0066
0067   /* The number of vertices deleted in each superstep. */
0068   std::vector<std::size_t> deleted_vertices;
0069
0070   template<typename OutputStream>
0071   void print(OutputStream& out)
0072   {
0073     double avg_deletions = std::accumulate(deleted_vertices.begin(),
0074                                            deleted_vertices.end(),
0075                                            0.0);
0076     avg_deletions /= deleted_vertices.size();
0077
0078     out << "Problem = \"Single-Source Shortest Paths\"\n"
0079         << "Algorithm = \"Crauser et al\"\n"
0080         << "Function = crauser_et_al_shortest_paths\n"
0081         << "Wall clock time = " << accounting::print_time(execution_time)
0082         << "\nSupersteps = " << deleted_vertices.size() << "\n"
0083         << "Avg. deletions per superstep = " << avg_deletions << "\n";
0084   }
0085 };
0086
0087 static crauser_et_al_shortest_paths_stats_t crauser_et_al_shortest_paths_stats;
0088 #endif
0089
0090 namespace detail {
0091
0092   /************************************************************************
0093    * Function objects that perform distance comparisons modified by the   *
0094    * minimum or maximum edge weights.                                     *
0095    ************************************************************************/
0096   template<typename Vertex, typename DistanceMap, typename MinInWeightMap,
0097            typename Combine, typename Compare>
0098   struct min_in_distance_compare
0099   {
0100     typedef Vertex first_argument_type;
0101     typedef Vertex second_argument_type;
0102     typedef bool result_type;
0103     min_in_distance_compare(DistanceMap d, MinInWeightMap m,
0104                             Combine combine, Compare compare)
0105       : distance_map(d), min_in_weight(m), combine(combine),
0106         compare(compare)
0107     {
0108     }
0109
0110     bool operator()(const Vertex& x, const Vertex& y) const
0111     {
0112       return compare(combine(get(distance_map, x), -get(min_in_weight, x)),
0113                      combine(get(distance_map, y), -get(min_in_weight, y)));
0114     }
0115
0116   private:
0117     DistanceMap distance_map;
0118     MinInWeightMap min_in_weight;
0119     Combine combine;
0120     Compare compare;
0121   };
0122
0123   template<typename Vertex, typename DistanceMap, typename MinOutWeightMap,
0124            typename Combine, typename Compare>
0125   struct min_out_distance_compare
0126   {
0127     typedef Vertex first_argument_type;
0128     typedef Vertex second_argument_type;
0129     typedef bool result_type;
0130     min_out_distance_compare(DistanceMap d, MinOutWeightMap m,
0131                              Combine combine, Compare compare)
0132       : distance_map(d), min_out_weight(m), combine(combine),
0133         compare(compare)
0134     {
0135     }
0136
0137     bool operator()(const Vertex& x, const Vertex& y) const
0138     {
0139       return compare(combine(get(distance_map, x), get(min_out_weight, x)),
0140                      combine(get(distance_map, y), get(min_out_weight, y)));
0141     }
0142
0143   private:
0144     DistanceMap distance_map;
0145     MinOutWeightMap min_out_weight;
0146     Combine combine;
0147     Compare compare;
0148   };
0149   /************************************************************************/
0150
0151   /************************************************************************
0152    * Dijkstra queue that implements Crauser et al.'s criteria. This queue *
0153    * actually stores three separate priority queues, to help expose all   *
0154    * vertices that can be processed in a single phase.                    *
0155    ************************************************************************/
0156   template<typename Graph, typename Combine,
0157            typename Compare, typename VertexIndexMap, typename DistanceMap,
0158            typename PredecessorMap, typename MinOutWeightMap,
0159            typename MinInWeightMap>
0160   class crauser_et_al_dijkstra_queue
0161     : public graph::detail::remote_update_set<
0162                crauser_et_al_dijkstra_queue<
0163                  Graph, Combine, Compare, VertexIndexMap, DistanceMap,
0164                  PredecessorMap, MinOutWeightMap, MinInWeightMap>,
0165                typename boost::graph::parallel::process_group_type<Graph>::type,
0166                typename dijkstra_msg_value<DistanceMap, PredecessorMap>::type,
0167                typename property_map<Graph, vertex_owner_t>::const_type>
0168   {
0169     typedef typename graph_traits<Graph>::vertex_descriptor
0170       vertex_descriptor;
0171     typedef crauser_et_al_dijkstra_queue self_type;
0172     typedef dijkstra_msg_value<DistanceMap, PredecessorMap> msg_value_creator;
0173     typedef typename msg_value_creator::type msg_value_type;
0174     typedef typename graph_traits<Graph>::vertices_size_type
0175       vertices_size_type;
0176     typedef typename property_map<Graph, vertex_owner_t>::const_type
0177       OwnerPropertyMap;
0178     typedef typename boost::graph::parallel::process_group_type<Graph>::type
0179       process_group_type;
0180     typedef graph::detail::remote_update_set<self_type, process_group_type,
0181                                              msg_value_type, OwnerPropertyMap>
0182       inherited;
0183
0184     // Priority queue for tentative distances
0185     typedef indirect_cmp<DistanceMap, Compare> dist_queue_compare_type;
0186
0187     typedef typename property_traits<DistanceMap>::value_type distance_type;
0188
0189 #ifdef MUTABLE_QUEUE
0190     typedef mutable_queue<vertex_descriptor, std::vector<vertex_descriptor>,
0191                           dist_queue_compare_type, VertexIndexMap> dist_queue_type;
0192
0193 #else
0194     typedef relaxed_heap<vertex_descriptor, dist_queue_compare_type,
0195                          VertexIndexMap> dist_queue_type;
0196 #endif // MUTABLE_QUEUE
0197
0198     // Priority queue for OUT criteria
0199     typedef min_out_distance_compare<vertex_descriptor, DistanceMap,
0200                                      MinOutWeightMap, Combine, Compare>
0201       out_queue_compare_type;
0202
0203 #ifdef MUTABLE_QUEUE
0204     typedef mutable_queue<vertex_descriptor, std::vector<vertex_descriptor>,
0205                           out_queue_compare_type, VertexIndexMap> out_queue_type;
0206
0207 #else
0208     typedef relaxed_heap<vertex_descriptor, out_queue_compare_type,
0209                          VertexIndexMap> out_queue_type;
0210 #endif // MUTABLE_QUEUE
0211
0212     // Priority queue for IN criteria
0213     typedef min_in_distance_compare<vertex_descriptor, DistanceMap,
0214                                     MinInWeightMap, Combine, Compare>
0215       in_queue_compare_type;
0216
0217 #ifdef MUTABLE_QUEUE
0218     typedef mutable_queue<vertex_descriptor, std::vector<vertex_descriptor>,
0219                           in_queue_compare_type, VertexIndexMap> in_queue_type;
0220
0221 #else
0222     typedef relaxed_heap<vertex_descriptor, in_queue_compare_type,
0223                          VertexIndexMap> in_queue_type;
0224 #endif // MUTABLE_QUEUE
0225
0226     typedef typename process_group_type::process_id_type process_id_type;
0227
0228   public:
0229     typedef typename dist_queue_type::size_type  size_type;
0230     typedef typename dist_queue_type::value_type value_type;
0231
0232     crauser_et_al_dijkstra_queue(const Graph& g,
0233                                  const Combine& combine,
0234                                  const Compare& compare,
0235                                  const VertexIndexMap& id,
0236                                  const DistanceMap& distance_map,
0237                                  const PredecessorMap& predecessor_map,
0238                                  const MinOutWeightMap& min_out_weight,
0239                                  const MinInWeightMap& min_in_weight)
0240       : inherited(boost::graph::parallel::process_group(g), get(vertex_owner, g)),
0241         dist_queue(num_vertices(g),
0242                    dist_queue_compare_type(distance_map, compare),
0243                    id),
0244         out_queue(num_vertices(g),
0245                   out_queue_compare_type(distance_map, min_out_weight,
0246                                          combine, compare),
0247                   id),
0248         in_queue(num_vertices(g),
0249                  in_queue_compare_type(distance_map, min_in_weight,
0250                                        combine, compare),
0251                  id),
0252         g(g),
0253         distance_map(distance_map),
0254         predecessor_map(predecessor_map),
0255         min_out_weight(min_out_weight),
0256         min_in_weight(min_in_weight),
0257         min_distance(0),
0258         min_out_distance(0)
0259 #ifdef PBGL_ACCOUNTING
0260         , local_deletions(0)
0261 #endif
0262     { }
0263
0264     void push(const value_type& x)
0265     {
0266       msg_value_type msg_value =
0267         msg_value_creator::create(get(distance_map, x),
0268                                   predecessor_value(get(predecessor_map, x)));
0269       inherited::update(x, msg_value);
0270     }
0271
0272     void update(const value_type& x) { push(x); }
0273
0274     void pop()
0275     {
0276       // Remove from distance queue
0277       dist_queue.remove(top_vertex);
0278
0279       // Remove from OUT queue
0280       out_queue.remove(top_vertex);
0281
0282       // Remove from IN queue
0283       in_queue.remove(top_vertex);
0284
0285 #ifdef PBGL_ACCOUNTING
0286       ++local_deletions;
0287 #endif
0288     }
0289
0290     vertex_descriptor& top() { return top_vertex; }
0291     const vertex_descriptor& top() const { return top_vertex; }
0292
0293     bool empty()
0294     {
0295       inherited::collect();
0296
0297       // If there are no suitable messages, wait until we get something
0298       while (!has_suitable_vertex()) {
0299         if (do_synchronize()) return true;
0300       }
0301       // Return true only if nobody has any messages; false if we
0302       // have suitable messages
0303       return false;
0304     }
0305
0306     bool do_synchronize()
0307     {
0308       using boost::parallel::all_reduce;
0309       using boost::parallel::minimum;
0310
0311       inherited::synchronize();
0312
0313       // TBD: could use combine here, but then we need to stop using
0314       // minimum<distance_type>() as the function object.
0315       distance_type local_distances[2];
0316       local_distances[0] =
0317         dist_queue.empty()? (std::numeric_limits<distance_type>::max)()
0318         : get(distance_map, dist_queue.top());
0319
0320       local_distances[1] =
0321         out_queue.empty()? (std::numeric_limits<distance_type>::max)()
0322         : (get(distance_map, out_queue.top())
0323            + get(min_out_weight, out_queue.top()));
0324
0325       distance_type distances[2];
0326       all_reduce(this->process_group, local_distances, local_distances + 2,
0327                  distances, minimum<distance_type>());
0328       min_distance = distances[0];
0329       min_out_distance = distances[1];
0330
0331 #ifdef PBGL_ACCOUNTING
0332       std::size_t deletions = 0;
0333       all_reduce(this->process_group, &local_deletions, &local_deletions + 1,
0334                  &deletions, std::plus<std::size_t>());
0335       if (process_id(this->process_group) == 0) {
0336         crauser_et_al_shortest_paths_stats.deleted_vertices.push_back(deletions);
0337       }
0338       local_deletions = 0;
0339       BOOST_ASSERT(deletions > 0);
0340 #endif
0341
0342       return min_distance == (std::numeric_limits<distance_type>::max)();
0343     }
0344
0345   private:
0346     vertex_descriptor predecessor_value(vertex_descriptor v) const
0347     { return v; }
0348
0349     vertex_descriptor
0350     predecessor_value(property_traits<dummy_property_map>::reference) const
0351     { return graph_traits<Graph>::null_vertex(); }
0352
0353     bool has_suitable_vertex() const
0354     {
0355       if (!dist_queue.empty()) {
0356         top_vertex = dist_queue.top();
0357         if (get(distance_map, dist_queue.top()) <= min_out_distance)
0358           return true;
0359       }
0360
0361       if (!in_queue.empty()) {
0362         top_vertex = in_queue.top();
0363         return (get(distance_map, top_vertex)
0364                 - get(min_in_weight, top_vertex)) <= min_distance;
0365       }
0366       return false;
0367     }
0368
0369   public:
0370     void
0371     receive_update(process_id_type source, vertex_descriptor vertex,
0372                    distance_type distance)
0373     {
0374       // Update the queue if the received distance is better than
0375       // the distance we know locally
0376       if (distance < get(distance_map, vertex)
0377           || (distance == get(distance_map, vertex)
0378               && source == process_id(this->process_group))) {
0379         // Update the local distance map
0380         put(distance_map, vertex, distance);
0381
0382         bool is_in_queue = dist_queue.contains(vertex);
0383
0384         if (!is_in_queue) {
0385           dist_queue.push(vertex);
0386           out_queue.push(vertex);
0387           in_queue.push(vertex);
0388         }
0389         else {
0390           dist_queue.update(vertex);
0391           out_queue.update(vertex);
0392           in_queue.update(vertex);
0393         }
0394       }
0395     }
0396
0397     void
0398     receive_update(process_id_type source, vertex_descriptor vertex,
0399                    std::pair<distance_type, vertex_descriptor> p)
0400     {
0401       if (p.first <= get(distance_map, vertex)) {
0402         put(predecessor_map, vertex, p.second);
0403         receive_update(source, vertex, p.first);
0404       }
0405     }
0406
0407   private:
0408     dist_queue_type           dist_queue;
0409     out_queue_type            out_queue;
0410     in_queue_type             in_queue;
0411     mutable value_type        top_vertex;
0412     const Graph&              g;
0413     DistanceMap               distance_map;
0414     PredecessorMap            predecessor_map;
0415     MinOutWeightMap           min_out_weight;
0416     MinInWeightMap            min_in_weight;
0417     distance_type             min_distance;
0418     distance_type             min_out_distance;
0419 #ifdef PBGL_ACCOUNTING
0420     std::size_t               local_deletions;
0421 #endif
0422   };
0423   /************************************************************************/
0424
0425   /************************************************************************
0426    * Initialize the property map that contains the minimum incoming edge  *
0427    * weight for each vertex. There are separate implementations for       *
0428    * directed, bidirectional, and undirected graph.                       *
0429    ************************************************************************/
0430   template<typename Graph, typename MinInWeightMap, typename WeightMap,
0431            typename Inf, typename Compare>
0432   void
0433   initialize_min_in_weights(const Graph& g, MinInWeightMap min_in_weight,
0434                             WeightMap weight, Inf inf, Compare compare,
0435                             directed_tag, incidence_graph_tag)
0436   {
0437     // Send minimum weights off to the owners
0438     set_property_map_role(vertex_distance, min_in_weight);
0439     BGL_FORALL_VERTICES_T(v, g, Graph) {
0440       BGL_FORALL_OUTEDGES_T(v, e, g, Graph) {
0441         if (get(weight, e) < get(min_in_weight, target(e, g)))
0442           put(min_in_weight, target(e, g), get(weight, e));
0443       }
0444     }
0445
0446     using boost::graph::parallel::process_group;
0447     synchronize(process_group(g));
0448
0449     // Replace any infinities with zeros
0450     BGL_FORALL_VERTICES_T(v, g, Graph) {
0451       if (get(min_in_weight, v) == inf) put(min_in_weight, v, 0);
0452     }
0453   }
0454
0455   template<typename Graph, typename MinInWeightMap, typename WeightMap,
0456            typename Inf, typename Compare>
0457   void
0458   initialize_min_in_weights(const Graph& g, MinInWeightMap min_in_weight,
0459                             WeightMap weight, Inf inf, Compare compare,
0460                             directed_tag, bidirectional_graph_tag)
0461   {
0462 #if 0
0463     typename property_map<Graph, vertex_local_t>::const_type
0464       local = get(vertex_local, g);
0465
0466     // This code assumes that the properties of the in-edges are
0467     // available locally. This is not necessarily the case, so don't
0468     // do this yet.
0469     set_property_map_role(vertex_distance, min_in_weight);
0470     BGL_FORALL_VERTICES_T(v, g, Graph) {
0471       if (in_edges(v, g).first != in_edges(v, g).second) {
0472         std::cerr << "weights(" << g.distribution().global(get(local, v))
0473                   << ") = ";
0474         BGL_FORALL_INEDGES_T(v, e, g, Graph) {
0475           std::cerr << get(weight, e) << ' ';
0476         }
0477         std::cerr << std::endl;
0478         put(min_in_weight, v,
0479             *boost::first_min_element
0480             (make_property_map_iterator(weight, in_edges(v, g).first),
0481              make_property_map_iterator(weight, in_edges(v, g).second),
0482              compare));
0483       } else {
0484         put(min_in_weight, v, 0);
0485       }
0486       std::cerr << "miw(" << g.distribution().global(get(local, v)) << ") = "
0487                 << get(min_in_weight, v) << std::endl;
0488     }
0489 #else
0490     initialize_min_in_weights(g, min_in_weight, weight, inf, compare,
0491                               directed_tag(), incidence_graph_tag());
0492 #endif
0493   }
0494
0495   template<typename Graph, typename MinInWeightMap, typename WeightMap,
0496            typename Inf, typename Compare>
0497   inline void
0498   initialize_min_in_weights(const Graph&, MinInWeightMap, WeightMap, Inf,
0499                             Compare, undirected_tag, bidirectional_graph_tag)
0500   {
0501     // In weights are the same as out weights, so do nothing
0502   }
0503   /************************************************************************/
0504
0505
0506   /************************************************************************
0507    * Initialize the property map that contains the minimum outgoing edge  *
0508    * weight for each vertex.                                              *
0509    ************************************************************************/
0510   template<typename Graph, typename MinOutWeightMap, typename WeightMap,
0511            typename Compare>
0512   void
0513   initialize_min_out_weights(const Graph& g, MinOutWeightMap min_out_weight,
0514                              WeightMap weight, Compare compare)
0515   {
0516     typedef typename property_traits<WeightMap>::value_type weight_type;
0517
0518     BGL_FORALL_VERTICES_T(v, g, Graph) {
0519       if (out_edges(v, g).first != out_edges(v, g).second) {
0520         put(min_out_weight, v,
0521             *boost::first_min_element
0522             (make_property_map_iterator(weight, out_edges(v, g).first),
0523              make_property_map_iterator(weight, out_edges(v, g).second),
0524              compare));
0525         if (get(min_out_weight, v) < weight_type(0))
0526             boost::throw_exception(negative_edge());
0527       }
0528     }
0529   }
0530
0531   /************************************************************************/
0532
0533 } // end namespace detail
0534
0535 template<typename DistributedGraph, typename DijkstraVisitor,
0536          typename PredecessorMap, typename DistanceMap, typename WeightMap,
0537          typename IndexMap, typename ColorMap, typename Compare,
0538          typename Combine, typename DistInf, typename DistZero>
0539 void
0540 crauser_et_al_shortest_paths
0541   (const DistributedGraph& g,
0542    typename graph_traits<DistributedGraph>::vertex_descriptor s,
0543    PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
0544    IndexMap index_map, ColorMap color_map,
0545    Compare compare, Combine combine, DistInf inf, DistZero zero,
0546    DijkstraVisitor vis)
0547 {
0548
0549 #ifdef PBGL_ACCOUNTING
0550   crauser_et_al_shortest_paths_stats.deleted_vertices.clear();
0551   crauser_et_al_shortest_paths_stats.execution_time = accounting::get_time();
0552 #endif
0553
0554   // Property map that stores the lowest edge weight outgoing from
0555   // each vertex. If a vertex has no out-edges, the stored weight
0556   // is zero.
0557   typedef typename property_traits<WeightMap>::value_type weight_type;
0558   typedef iterator_property_map<weight_type*, IndexMap> MinOutWeightMap;
0559   std::vector<weight_type> min_out_weights_vec(num_vertices(g), inf);
0560   MinOutWeightMap min_out_weight(&min_out_weights_vec.front(), index_map);
0561   detail::initialize_min_out_weights(g, min_out_weight, weight, compare);
0562
0563   // Property map that stores the lowest edge weight incoming to
0564   // each vertex. For undirected graphs, this will just be a
0565   // shallow copy of the version for outgoing edges.
0566   typedef typename graph_traits<DistributedGraph>::directed_category
0567     directed_category;
0568   const bool is_undirected =
0569     is_same<directed_category, undirected_tag>::value;
0570   typedef MinOutWeightMap MinInWeightMap;
0571   std::vector<weight_type>
0572     min_in_weights_vec(is_undirected? 1 : num_vertices(g), inf);
0573   MinInWeightMap min_in_weight(&min_in_weights_vec.front(), index_map);
0574   typedef typename graph_traits<DistributedGraph>::traversal_category
0575     category;
0576   detail::initialize_min_in_weights(g, min_in_weight, weight, inf, compare,
0577                                     directed_category(), category());
0578
0579   // Initialize local portion of property maps
0580   typename graph_traits<DistributedGraph>::vertex_iterator ui, ui_end;
0581   for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
0582     put(distance, *ui, inf);
0583     put(predecessor, *ui, *ui);
0584   }
0585   put(distance, s, zero);
0586
0587   // Dijkstra Queue
0588   typedef detail::crauser_et_al_dijkstra_queue
0589             <DistributedGraph, Combine, Compare, IndexMap, DistanceMap,
0590              PredecessorMap, MinOutWeightMap, MinInWeightMap>
0591     Queue;
0592
0593   Queue Q(g, combine, compare, index_map, distance, predecessor,
0594           min_out_weight, is_undirected? min_out_weight : min_in_weight);
0595
0596   // Parallel Dijkstra visitor
0597   ::boost::detail::dijkstra_bfs_visitor<
0598       DijkstraVisitor, Queue, WeightMap,
0599       boost::parallel::caching_property_map<PredecessorMap>,
0600       boost::parallel::caching_property_map<DistanceMap>, Combine, Compare
0601     > bfs_vis(vis, Q, weight,
0602               boost::parallel::make_caching_property_map(predecessor),
0603               boost::parallel::make_caching_property_map(distance),
0604               combine, compare, zero);
0605
0606   set_property_map_role(vertex_color, color_map);
0607   set_property_map_role(vertex_distance, distance);
0608
0609   breadth_first_search(g, s, Q, bfs_vis, color_map);
0610
0611 #ifdef PBGL_ACCOUNTING
0612   crauser_et_al_shortest_paths_stats.execution_time =
0613     accounting::get_time() - crauser_et_al_shortest_paths_stats.execution_time;
0614 #endif
0615 }
0616
0617 template<typename DistributedGraph, typename PredecessorMap,
0618          typename DistanceMap, typename WeightMap>
0619 void
0620 crauser_et_al_shortest_paths
0621   (const DistributedGraph& g,
0622    typename graph_traits<DistributedGraph>::vertex_descriptor s,
0623    PredecessorMap predecessor, DistanceMap distance, WeightMap weight)
0624 {
0625   typedef typename property_traits<DistanceMap>::value_type distance_type;
0626
0627   std::vector<default_color_type> colors(num_vertices(g), white_color);
0628
0629   crauser_et_al_shortest_paths(g, s, predecessor, distance, weight,
0630                                get(vertex_index, g),
0631                                make_iterator_property_map(&colors[0],
0632                                                           get(vertex_index, g)),
0633                                std::less<distance_type>(),
0634                                closed_plus<distance_type>(),
0635                                (std::numeric_limits<distance_type>::max)(),
0636                                distance_type(),
0637                                dijkstra_visitor<>());
0638 }
0639
0640 template<typename DistributedGraph, typename PredecessorMap,
0641          typename DistanceMap>
0642 void
0643 crauser_et_al_shortest_paths
0644   (const DistributedGraph& g,
0645    typename graph_traits<DistributedGraph>::vertex_descriptor s,
0646    PredecessorMap predecessor, DistanceMap distance)
0647 {
0648   crauser_et_al_shortest_paths(g, s, predecessor, distance,
0649                                get(edge_weight, g));
0650 }
0651
0652 } // end namespace distributed
0653
0654 #ifdef PBGL_ACCOUNTING
0655 using distributed::crauser_et_al_shortest_paths_stats;
0656 #endif
0657
0658 using distributed::crauser_et_al_shortest_paths;
0659
0660
0661 } } // end namespace boost::graph
0662
0663 #endif // BOOST_GRAPH_CRAUSER_ET_AL_SHORTEST_PATHS_HPP