ceph/src/boost/boost/graph/distributed/crauser_et_al_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
  10 /**************************************************************************
  11  * This source file implements the variation on Dijkstra's algorithm      *
  12  * presented by Crauser et al. in:                                        *
  13  *                                                                        *
  14  *   Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter              *
  15  *   Sanders. A Parallelization of Dijkstra's Shortest Path               *
  16  *   Algorithm. In Lubos Brim, Jozef Gruska, and Jiri Zlatuska,          *
  17  *   editors, Mathematical Foundations of Computer Science (MFCS),        *
  18  *   volume 1450 of Lecture Notes in Computer Science, pages              *
  19  *   722--731, 1998. Springer.                                            *
  20  *                                                                        *
  21  * This implementation is, however, restricted to the distributed-memory  *
  22  * case, where the work is distributed by virtue of the vertices being    *
  23  * distributed. In a shared-memory (single address space) context, we     *
  24  * would want to add an explicit balancing step.                          *
  25  **************************************************************************/
  26 #ifndef BOOST_GRAPH_CRAUSER_ET_AL_SHORTEST_PATHS_HPP
  27 #define BOOST_GRAPH_CRAUSER_ET_AL_SHORTEST_PATHS_HPP
  28
  29 #ifndef BOOST_GRAPH_USE_MPI
  30 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
  31 #endif
  32
  33 #include <boost/assert.hpp>
  34 #include <boost/graph/distributed/detail/dijkstra_shortest_paths.hpp>
  35 #include <boost/graph/parallel/algorithm.hpp>
  36 #include <functional>
  37 #include <boost/graph/iteration_macros.hpp>
  38 #include <boost/property_map/property_map_iterator.hpp>
  39 #include <boost/type_traits/is_same.hpp>
  40 #include <algorithm>
  41 #include <boost/property_map/parallel/caching_property_map.hpp>
  42 #include <boost/pending/indirect_cmp.hpp>
  43 #include <boost/graph/distributed/detail/remote_update_set.hpp>
  44 #include <vector>
  45 #include <boost/graph/breadth_first_search.hpp>
  46 #include <boost/graph/dijkstra_shortest_paths.hpp>
  47 #include <boost/graph/parallel/container_traits.hpp>
  48
  49 #ifdef PBGL_ACCOUNTING
  50 #  include <boost/graph/accounting.hpp>
  51 #  include <numeric>
  52 #endif // PBGL_ACCOUNTING
  53
  54 #ifdef MUTABLE_QUEUE
  55 #    include <boost/pending/mutable_queue.hpp>
  56 #endif
  57
  58 namespace boost { namespace graph { namespace distributed {
  59
  60 #ifdef PBGL_ACCOUNTING
  61 struct crauser_et_al_shortest_paths_stats_t
  62 {
  63   /* Total wall-clock time used by the algorithm.*/
  64   accounting::time_type execution_time;
  65
  66   /* The number of vertices deleted in each superstep. */
  67   std::vector<std::size_t> deleted_vertices;
  68
  69   template<typename OutputStream>
  70   void print(OutputStream& out)
  71   {
  72     double avg_deletions = std::accumulate(deleted_vertices.begin(),
  73                                            deleted_vertices.end(),
  74                                            0.0);
  75     avg_deletions /= deleted_vertices.size();
  76
  77     out << "Problem = \"Single-Source Shortest Paths\"\n"
  78         << "Algorithm = \"Crauser et al\"\n"
  79         << "Function = crauser_et_al_shortest_paths\n"
  80         << "Wall clock time = " << accounting::print_time(execution_time)
  81         << "\nSupersteps = " << deleted_vertices.size() << "\n"
  82         << "Avg. deletions per superstep = " << avg_deletions << "\n";
  83   }
  84 };
  85
  86 static crauser_et_al_shortest_paths_stats_t crauser_et_al_shortest_paths_stats;
  87 #endif
  88
  89 namespace detail {
  90
  91   /************************************************************************
  92    * Function objects that perform distance comparisons modified by the   *
  93    * minimum or maximum edge weights.                                     *
  94    ************************************************************************/
  95   template<typename Vertex, typename DistanceMap, typename MinInWeightMap,
  96            typename Combine, typename Compare>
  97   struct min_in_distance_compare
  98     : std::binary_function<Vertex, Vertex, bool>
  99   {
 100     min_in_distance_compare(DistanceMap d, MinInWeightMap m,
 101                             Combine combine, Compare compare)
 102       : distance_map(d), min_in_weight(m), combine(combine),
 103         compare(compare)
 104     {
 105     }
 106
 107     bool operator()(const Vertex& x, const Vertex& y) const
 108     {
 109       return compare(combine(get(distance_map, x), -get(min_in_weight, x)),
 110                      combine(get(distance_map, y), -get(min_in_weight, y)));
 111     }
 112
 113   private:
 114     DistanceMap distance_map;
 115     MinInWeightMap min_in_weight;
 116     Combine combine;
 117     Compare compare;
 118   };
 119
 120   template<typename Vertex, typename DistanceMap, typename MinOutWeightMap,
 121            typename Combine, typename Compare>
 122   struct min_out_distance_compare
 123     : std::binary_function<Vertex, Vertex, bool>
 124   {
 125     min_out_distance_compare(DistanceMap d, MinOutWeightMap m,
 126                              Combine combine, Compare compare)
 127       : distance_map(d), min_out_weight(m), combine(combine),
 128         compare(compare)
 129     {
 130     }
 131
 132     bool operator()(const Vertex& x, const Vertex& y) const
 133     {
 134       return compare(combine(get(distance_map, x), get(min_out_weight, x)),
 135                      combine(get(distance_map, y), get(min_out_weight, y)));
 136     }
 137
 138   private:
 139     DistanceMap distance_map;
 140     MinOutWeightMap min_out_weight;
 141     Combine combine;
 142     Compare compare;
 143   };
 144   /************************************************************************/
 145
 146   /************************************************************************
 147    * Dijkstra queue that implements Crauser et al.'s criteria. This queue *
 148    * actually stores three separate priority queues, to help expose all   *
 149    * vertices that can be processed in a single phase.                    *
 150    ************************************************************************/
 151   template<typename Graph, typename Combine,
 152            typename Compare, typename VertexIndexMap, typename DistanceMap,
 153            typename PredecessorMap, typename MinOutWeightMap,
 154            typename MinInWeightMap>
 155   class crauser_et_al_dijkstra_queue
 156     : public graph::detail::remote_update_set<
 157                crauser_et_al_dijkstra_queue<
 158                  Graph, Combine, Compare, VertexIndexMap, DistanceMap,
 159                  PredecessorMap, MinOutWeightMap, MinInWeightMap>,
 160                typename boost::graph::parallel::process_group_type<Graph>::type,
 161                typename dijkstra_msg_value<DistanceMap, PredecessorMap>::type,
 162                typename property_map<Graph, vertex_owner_t>::const_type>
 163   {
 164     typedef typename graph_traits<Graph>::vertex_descriptor
 165       vertex_descriptor;
 166     typedef crauser_et_al_dijkstra_queue self_type;
 167     typedef dijkstra_msg_value<DistanceMap, PredecessorMap> msg_value_creator;
 168     typedef typename msg_value_creator::type msg_value_type;
 169     typedef typename graph_traits<Graph>::vertices_size_type
 170       vertices_size_type;
 171     typedef typename property_map<Graph, vertex_owner_t>::const_type
 172       OwnerPropertyMap;
 173     typedef typename boost::graph::parallel::process_group_type<Graph>::type
 174       process_group_type;
 175     typedef graph::detail::remote_update_set<self_type, process_group_type,
 176                                              msg_value_type, OwnerPropertyMap>
 177       inherited;
 178
 179     // Priority queue for tentative distances
 180     typedef indirect_cmp<DistanceMap, Compare> dist_queue_compare_type;
 181
 182     typedef typename property_traits<DistanceMap>::value_type distance_type;
 183
 184 #ifdef MUTABLE_QUEUE
 185     typedef mutable_queue<vertex_descriptor, std::vector<vertex_descriptor>,
 186                           dist_queue_compare_type, VertexIndexMap> dist_queue_type;
 187
 188 #else
 189     typedef relaxed_heap<vertex_descriptor, dist_queue_compare_type,
 190                          VertexIndexMap> dist_queue_type;
 191 #endif // MUTABLE_QUEUE
 192
 193     // Priority queue for OUT criteria
 194     typedef min_out_distance_compare<vertex_descriptor, DistanceMap,
 195                                      MinOutWeightMap, Combine, Compare>
 196       out_queue_compare_type;
 197
 198 #ifdef MUTABLE_QUEUE
 199     typedef mutable_queue<vertex_descriptor, std::vector<vertex_descriptor>,
 200                           out_queue_compare_type, VertexIndexMap> out_queue_type;
 201
 202 #else
 203     typedef relaxed_heap<vertex_descriptor, out_queue_compare_type,
 204                          VertexIndexMap> out_queue_type;
 205 #endif // MUTABLE_QUEUE
 206
 207     // Priority queue for IN criteria
 208     typedef min_in_distance_compare<vertex_descriptor, DistanceMap,
 209                                     MinInWeightMap, Combine, Compare>
 210       in_queue_compare_type;
 211
 212 #ifdef MUTABLE_QUEUE
 213     typedef mutable_queue<vertex_descriptor, std::vector<vertex_descriptor>,
 214                           in_queue_compare_type, VertexIndexMap> in_queue_type;
 215
 216 #else
 217     typedef relaxed_heap<vertex_descriptor, in_queue_compare_type,
 218                          VertexIndexMap> in_queue_type;
 219 #endif // MUTABLE_QUEUE
 220
 221     typedef typename process_group_type::process_id_type process_id_type;
 222
 223   public:
 224     typedef typename dist_queue_type::size_type  size_type;
 225     typedef typename dist_queue_type::value_type value_type;
 226
 227     crauser_et_al_dijkstra_queue(const Graph& g,
 228                                  const Combine& combine,
 229                                  const Compare& compare,
 230                                  const VertexIndexMap& id,
 231                                  const DistanceMap& distance_map,
 232                                  const PredecessorMap& predecessor_map,
 233                                  const MinOutWeightMap& min_out_weight,
 234                                  const MinInWeightMap& min_in_weight)
 235       : inherited(boost::graph::parallel::process_group(g), get(vertex_owner, g)),
 236         dist_queue(num_vertices(g),
 237                    dist_queue_compare_type(distance_map, compare),
 238                    id),
 239         out_queue(num_vertices(g),
 240                   out_queue_compare_type(distance_map, min_out_weight,
 241                                          combine, compare),
 242                   id),
 243         in_queue(num_vertices(g),
 244                  in_queue_compare_type(distance_map, min_in_weight,
 245                                        combine, compare),
 246                  id),
 247         g(g),
 248         distance_map(distance_map),
 249         predecessor_map(predecessor_map),
 250         min_out_weight(min_out_weight),
 251         min_in_weight(min_in_weight),
 252         min_distance(0),
 253         min_out_distance(0)
 254 #ifdef PBGL_ACCOUNTING
 255         , local_deletions(0)
 256 #endif
 257     { }
 258
 259     void push(const value_type& x)
 260     {
 261       msg_value_type msg_value =
 262         msg_value_creator::create(get(distance_map, x),
 263                                   predecessor_value(get(predecessor_map, x)));
 264       inherited::update(x, msg_value);
 265     }
 266
 267     void update(const value_type& x) { push(x); }
 268
 269     void pop()
 270     {
 271       // Remove from distance queue
 272       dist_queue.remove(top_vertex);
 273
 274       // Remove from OUT queue
 275       out_queue.remove(top_vertex);
 276
 277       // Remove from IN queue
 278       in_queue.remove(top_vertex);
 279
 280 #ifdef PBGL_ACCOUNTING
 281       ++local_deletions;
 282 #endif
 283     }
 284
 285     vertex_descriptor& top() { return top_vertex; }
 286     const vertex_descriptor& top() const { return top_vertex; }
 287
 288     bool empty()
 289     {
 290       inherited::collect();
 291
 292       // If there are no suitable messages, wait until we get something
 293       while (!has_suitable_vertex()) {
 294         if (do_synchronize()) return true;
 295       }
 296       // Return true only if nobody has any messages; false if we
 297       // have suitable messages
 298       return false;
 299     }
 300
 301     bool do_synchronize()
 302     {
 303       using boost::parallel::all_reduce;
 304       using boost::parallel::minimum;
 305
 306       inherited::synchronize();
 307
 308       // TBD: could use combine here, but then we need to stop using
 309       // minimum<distance_type>() as the function object.
 310       distance_type local_distances[2];
 311       local_distances[0] =
 312         dist_queue.empty()? (std::numeric_limits<distance_type>::max)()
 313         : get(distance_map, dist_queue.top());
 314
 315       local_distances[1] =
 316         out_queue.empty()? (std::numeric_limits<distance_type>::max)()
 317         : (get(distance_map, out_queue.top())
 318            + get(min_out_weight, out_queue.top()));
 319
 320       distance_type distances[2];
 321       all_reduce(this->process_group, local_distances, local_distances + 2,
 322                  distances, minimum<distance_type>());
 323       min_distance = distances[0];
 324       min_out_distance = distances[1];
 325
 326 #ifdef PBGL_ACCOUNTING
 327       std::size_t deletions = 0;
 328       all_reduce(this->process_group, &local_deletions, &local_deletions + 1,
 329                  &deletions, std::plus<std::size_t>());
 330       if (process_id(this->process_group) == 0) {
 331         crauser_et_al_shortest_paths_stats.deleted_vertices.push_back(deletions);
 332       }
 333       local_deletions = 0;
 334       BOOST_ASSERT(deletions > 0);
 335 #endif
 336
 337       return min_distance == (std::numeric_limits<distance_type>::max)();
 338     }
 339
 340   private:
 341     vertex_descriptor predecessor_value(vertex_descriptor v) const
 342     { return v; }
 343
 344     vertex_descriptor
 345     predecessor_value(property_traits<dummy_property_map>::reference) const
 346     { return graph_traits<Graph>::null_vertex(); }
 347
 348     bool has_suitable_vertex() const
 349     {
 350       if (!dist_queue.empty()) {
 351         top_vertex = dist_queue.top();
 352         if (get(distance_map, dist_queue.top()) <= min_out_distance)
 353           return true;
 354       }
 355
 356       if (!in_queue.empty()) {
 357         top_vertex = in_queue.top();
 358         return (get(distance_map, top_vertex)
 359                 - get(min_in_weight, top_vertex)) <= min_distance;
 360       }
 361       return false;
 362     }
 363
 364   public:
 365     void
 366     receive_update(process_id_type source, vertex_descriptor vertex,
 367                    distance_type distance)
 368     {
 369       // Update the queue if the received distance is better than
 370       // the distance we know locally
 371       if (distance < get(distance_map, vertex)
 372           || (distance == get(distance_map, vertex)
 373               && source == process_id(this->process_group))) {
 374         // Update the local distance map
 375         put(distance_map, vertex, distance);
 376
 377         bool is_in_queue = dist_queue.contains(vertex);
 378
 379         if (!is_in_queue) {
 380           dist_queue.push(vertex);
 381           out_queue.push(vertex);
 382           in_queue.push(vertex);
 383         }
 384         else {
 385           dist_queue.update(vertex);
 386           out_queue.update(vertex);
 387           in_queue.update(vertex);
 388         }
 389       }
 390     }
 391
 392     void
 393     receive_update(process_id_type source, vertex_descriptor vertex,
 394                    std::pair<distance_type, vertex_descriptor> p)
 395     {
 396       if (p.first <= get(distance_map, vertex)) {
 397         put(predecessor_map, vertex, p.second);
 398         receive_update(source, vertex, p.first);
 399       }
 400     }
 401
 402   private:
 403     dist_queue_type           dist_queue;
 404     out_queue_type            out_queue;
 405     in_queue_type             in_queue;
 406     mutable value_type        top_vertex;
 407     const Graph&              g;
 408     DistanceMap               distance_map;
 409     PredecessorMap            predecessor_map;
 410     MinOutWeightMap           min_out_weight;
 411     MinInWeightMap            min_in_weight;
 412     distance_type             min_distance;
 413     distance_type             min_out_distance;
 414 #ifdef PBGL_ACCOUNTING
 415     std::size_t               local_deletions;
 416 #endif
 417   };
 418   /************************************************************************/
 419
 420   /************************************************************************
 421    * Initialize the property map that contains the minimum incoming edge  *
 422    * weight for each vertex. There are separate implementations for       *
 423    * directed, bidirectional, and undirected graph.                       *
 424    ************************************************************************/
 425   template<typename Graph, typename MinInWeightMap, typename WeightMap,
 426            typename Inf, typename Compare>
 427   void
 428   initialize_min_in_weights(const Graph& g, MinInWeightMap min_in_weight,
 429                             WeightMap weight, Inf inf, Compare compare,
 430                             directed_tag, incidence_graph_tag)
 431   {
 432     // Send minimum weights off to the owners
 433     set_property_map_role(vertex_distance, min_in_weight);
 434     BGL_FORALL_VERTICES_T(v, g, Graph) {
 435       BGL_FORALL_OUTEDGES_T(v, e, g, Graph) {
 436         if (get(weight, e) < get(min_in_weight, target(e, g)))
 437           put(min_in_weight, target(e, g), get(weight, e));
 438       }
 439     }
 440
 441     using boost::graph::parallel::process_group;
 442     synchronize(process_group(g));
 443
 444     // Replace any infinities with zeros
 445     BGL_FORALL_VERTICES_T(v, g, Graph) {
 446       if (get(min_in_weight, v) == inf) put(min_in_weight, v, 0);
 447     }
 448   }
 449
 450   template<typename Graph, typename MinInWeightMap, typename WeightMap,
 451            typename Inf, typename Compare>
 452   void
 453   initialize_min_in_weights(const Graph& g, MinInWeightMap min_in_weight,
 454                             WeightMap weight, Inf inf, Compare compare,
 455                             directed_tag, bidirectional_graph_tag)
 456   {
 457 #if 0
 458     typename property_map<Graph, vertex_local_t>::const_type
 459       local = get(vertex_local, g);
 460
 461     // This code assumes that the properties of the in-edges are
 462     // available locally. This is not necessarily the case, so don't
 463     // do this yet.
 464     set_property_map_role(vertex_distance, min_in_weight);
 465     BGL_FORALL_VERTICES_T(v, g, Graph) {
 466       if (in_edges(v, g).first != in_edges(v, g).second) {
 467         std::cerr << "weights(" << g.distribution().global(get(local, v))
 468                   << ") = ";
 469         BGL_FORALL_INEDGES_T(v, e, g, Graph) {
 470           std::cerr << get(weight, e) << ' ';
 471         }
 472         std::cerr << std::endl;
 473         put(min_in_weight, v,
 474             *std::min_element
 475             (make_property_map_iterator(weight, in_edges(v, g).first),
 476              make_property_map_iterator(weight, in_edges(v, g).second),
 477              compare));
 478       } else {
 479         put(min_in_weight, v, 0);
 480       }
 481       std::cerr << "miw(" << g.distribution().global(get(local, v)) << ") = "
 482                 << get(min_in_weight, v) << std::endl;
 483     }
 484 #else
 485     initialize_min_in_weights(g, min_in_weight, weight, inf, compare,
 486                               directed_tag(), incidence_graph_tag());
 487 #endif
 488   }
 489
 490   template<typename Graph, typename MinInWeightMap, typename WeightMap,
 491            typename Inf, typename Compare>
 492   inline void
 493   initialize_min_in_weights(const Graph&, MinInWeightMap, WeightMap, Inf,
 494                             Compare, undirected_tag, bidirectional_graph_tag)
 495   {
 496     // In weights are the same as out weights, so do nothing
 497   }
 498   /************************************************************************/
 499
 500
 501   /************************************************************************
 502    * Initialize the property map that contains the minimum outgoing edge  *
 503    * weight for each vertex.                                              *
 504    ************************************************************************/
 505   template<typename Graph, typename MinOutWeightMap, typename WeightMap,
 506            typename Compare>
 507   void
 508   initialize_min_out_weights(const Graph& g, MinOutWeightMap min_out_weight,
 509                              WeightMap weight, Compare compare)
 510   {
 511     typedef typename property_traits<WeightMap>::value_type weight_type;
 512
 513     BGL_FORALL_VERTICES_T(v, g, Graph) {
 514       if (out_edges(v, g).first != out_edges(v, g).second) {
 515         put(min_out_weight, v,
 516             *std::min_element
 517             (make_property_map_iterator(weight, out_edges(v, g).first),
 518              make_property_map_iterator(weight, out_edges(v, g).second),
 519              compare));
 520         if (get(min_out_weight, v) < weight_type(0))
 521             boost::throw_exception(negative_edge());
 522       }
 523     }
 524   }
 525
 526   /************************************************************************/
 527
 528 } // end namespace detail
 529
 530 template<typename DistributedGraph, typename DijkstraVisitor,
 531          typename PredecessorMap, typename DistanceMap, typename WeightMap,
 532          typename IndexMap, typename ColorMap, typename Compare,
 533          typename Combine, typename DistInf, typename DistZero>
 534 void
 535 crauser_et_al_shortest_paths
 536   (const DistributedGraph& g,
 537    typename graph_traits<DistributedGraph>::vertex_descriptor s,
 538    PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
 539    IndexMap index_map, ColorMap color_map,
 540    Compare compare, Combine combine, DistInf inf, DistZero zero,
 541    DijkstraVisitor vis)
 542 {
 543
 544 #ifdef PBGL_ACCOUNTING
 545   crauser_et_al_shortest_paths_stats.deleted_vertices.clear();
 546   crauser_et_al_shortest_paths_stats.execution_time = accounting::get_time();
 547 #endif
 548
 549   // Property map that stores the lowest edge weight outgoing from
 550   // each vertex. If a vertex has no out-edges, the stored weight
 551   // is zero.
 552   typedef typename property_traits<WeightMap>::value_type weight_type;
 553   typedef iterator_property_map<weight_type*, IndexMap> MinOutWeightMap;
 554   std::vector<weight_type> min_out_weights_vec(num_vertices(g), inf);
 555   MinOutWeightMap min_out_weight(&min_out_weights_vec.front(), index_map);
 556   detail::initialize_min_out_weights(g, min_out_weight, weight, compare);
 557
 558   // Property map that stores the lowest edge weight incoming to
 559   // each vertex. For undirected graphs, this will just be a
 560   // shallow copy of the version for outgoing edges.
 561   typedef typename graph_traits<DistributedGraph>::directed_category
 562     directed_category;
 563   const bool is_undirected =
 564     is_same<directed_category, undirected_tag>::value;
 565   typedef MinOutWeightMap MinInWeightMap;
 566   std::vector<weight_type>
 567     min_in_weights_vec(is_undirected? 1 : num_vertices(g), inf);
 568   MinInWeightMap min_in_weight(&min_in_weights_vec.front(), index_map);
 569   typedef typename graph_traits<DistributedGraph>::traversal_category
 570     category;
 571   detail::initialize_min_in_weights(g, min_in_weight, weight, inf, compare,
 572                                     directed_category(), category());
 573
 574   // Initialize local portion of property maps
 575   typename graph_traits<DistributedGraph>::vertex_iterator ui, ui_end;
 576   for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
 577     put(distance, *ui, inf);
 578     put(predecessor, *ui, *ui);
 579   }
 580   put(distance, s, zero);
 581
 582   // Dijkstra Queue
 583   typedef detail::crauser_et_al_dijkstra_queue
 584             <DistributedGraph, Combine, Compare, IndexMap, DistanceMap,
 585              PredecessorMap, MinOutWeightMap, MinInWeightMap>
 586     Queue;
 587
 588   Queue Q(g, combine, compare, index_map, distance, predecessor,
 589           min_out_weight, is_undirected? min_out_weight : min_in_weight);
 590
 591   // Parallel Dijkstra visitor
 592   ::boost::detail::dijkstra_bfs_visitor<
 593       DijkstraVisitor, Queue, WeightMap,
 594       boost::parallel::caching_property_map<PredecessorMap>,
 595       boost::parallel::caching_property_map<DistanceMap>, Combine, Compare
 596     > bfs_vis(vis, Q, weight,
 597               boost::parallel::make_caching_property_map(predecessor),
 598               boost::parallel::make_caching_property_map(distance),
 599               combine, compare, zero);
 600
 601   set_property_map_role(vertex_color, color_map);
 602   set_property_map_role(vertex_distance, distance);
 603
 604   breadth_first_search(g, s, Q, bfs_vis, color_map);
 605
 606 #ifdef PBGL_ACCOUNTING
 607   crauser_et_al_shortest_paths_stats.execution_time =
 608     accounting::get_time() - crauser_et_al_shortest_paths_stats.execution_time;
 609 #endif
 610 }
 611
 612 template<typename DistributedGraph, typename PredecessorMap,
 613          typename DistanceMap, typename WeightMap>
 614 void
 615 crauser_et_al_shortest_paths
 616   (const DistributedGraph& g,
 617    typename graph_traits<DistributedGraph>::vertex_descriptor s,
 618    PredecessorMap predecessor, DistanceMap distance, WeightMap weight)
 619 {
 620   typedef typename property_traits<DistanceMap>::value_type distance_type;
 621
 622   std::vector<default_color_type> colors(num_vertices(g), white_color);
 623
 624   crauser_et_al_shortest_paths(g, s, predecessor, distance, weight,
 625                                get(vertex_index, g),
 626                                make_iterator_property_map(&colors[0],
 627                                                           get(vertex_index, g)),
 628                                std::less<distance_type>(),
 629                                closed_plus<distance_type>(),
 630                                (std::numeric_limits<distance_type>::max)(),
 631                                distance_type(),
 632                                dijkstra_visitor<>());
 633 }
 634
 635 template<typename DistributedGraph, typename PredecessorMap,
 636          typename DistanceMap>
 637 void
 638 crauser_et_al_shortest_paths
 639   (const DistributedGraph& g,
 640    typename graph_traits<DistributedGraph>::vertex_descriptor s,
 641    PredecessorMap predecessor, DistanceMap distance)
 642 {
 643   crauser_et_al_shortest_paths(g, s, predecessor, distance,
 644                                get(edge_weight, g));
 645 }
 646
 647 } // end namespace distributed
 648
 649 #ifdef PBGL_ACCOUNTING
 650 using distributed::crauser_et_al_shortest_paths_stats;
 651 #endif
 652
 653 using distributed::crauser_et_al_shortest_paths;
 654
 655
 656 } } // end namespace boost::graph
 657
 658 #endif // BOOST_GRAPH_CRAUSER_ET_AL_SHORTEST_PATHS_HPP