| // Copyright (C) 2004-2006 The Trustees of Indiana University. |
| |
| // Use, modification and distribution is subject to the Boost Software |
| // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| |
| // Authors: Douglas Gregor |
| // Andrew Lumsdaine |
| |
| /************************************************************************** |
| * This source file implements the variation on Dijkstra's algorithm * |
| * presented by Crauser et al. in: * |
| * * |
| * Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter * |
| * Sanders. A Parallelization of Dijkstra's Shortest Path * |
| * Algorithm. In Lubos Brim, Jozef Gruska, and Jiri Zlatuska, * |
| * editors, Mathematical Foundations of Computer Science (MFCS), * |
| * volume 1450 of Lecture Notes in Computer Science, pages * |
| * 722--731, 1998. Springer. * |
| * * |
| * This implementation is, however, restricted to the distributed-memory * |
| * case, where the work is distributed by virtue of the vertices being * |
| * distributed. In a shared-memory (single address space) context, we * |
| * would want to add an explicit balancing step. * |
| **************************************************************************/ |
| #ifndef BOOST_GRAPH_CRAUSER_ET_AL_SHORTEST_PATHS_HPP |
| #define BOOST_GRAPH_CRAUSER_ET_AL_SHORTEST_PATHS_HPP |
| |
| #ifndef BOOST_GRAPH_USE_MPI |
| #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included" |
| #endif |
| |
| #include <boost/graph/distributed/detail/dijkstra_shortest_paths.hpp> |
| #include <boost/graph/parallel/algorithm.hpp> |
| #include <functional> |
| #include <boost/graph/iteration_macros.hpp> |
| #include <boost/property_map/property_map_iterator.hpp> |
| #include <boost/type_traits/is_same.hpp> |
| #include <algorithm> |
| #include <boost/property_map/parallel/caching_property_map.hpp> |
| #include <boost/pending/indirect_cmp.hpp> |
| #include <boost/graph/distributed/detail/remote_update_set.hpp> |
| #include <vector> |
| #include <boost/graph/breadth_first_search.hpp> |
| #include <boost/graph/dijkstra_shortest_paths.hpp> |
| #include <boost/graph/parallel/container_traits.hpp> |
| |
| #ifdef PBGL_ACCOUNTING |
| # include <boost/graph/accounting.hpp> |
| # include <numeric> |
| #endif // PBGL_ACCOUNTING |
| |
| #ifdef MUTABLE_QUEUE |
| # include <boost/pending/mutable_queue.hpp> |
| #endif |
| |
| namespace boost { namespace graph { namespace distributed { |
| |
| #ifdef PBGL_ACCOUNTING |
| struct crauser_et_al_shortest_paths_stats_t |
| { |
| /* Total wall-clock time used by the algorithm.*/ |
| accounting::time_type execution_time; |
| |
| /* The number of vertices deleted in each superstep. */ |
| std::vector<std::size_t> deleted_vertices; |
| |
| template<typename OutputStream> |
| void print(OutputStream& out) |
| { |
| double avg_deletions = std::accumulate(deleted_vertices.begin(), |
| deleted_vertices.end(), |
| 0.0); |
| avg_deletions /= deleted_vertices.size(); |
| |
| out << "Problem = \"Single-Source Shortest Paths\"\n" |
| << "Algorithm = \"Crauser et al\"\n" |
| << "Function = crauser_et_al_shortest_paths\n" |
| << "Wall clock time = " << accounting::print_time(execution_time) |
| << "\nSupersteps = " << deleted_vertices.size() << "\n" |
| << "Avg. deletions per superstep = " << avg_deletions << "\n"; |
| } |
| }; |
| |
| static crauser_et_al_shortest_paths_stats_t crauser_et_al_shortest_paths_stats; |
| #endif |
| |
| namespace detail { |
| |
| /************************************************************************ |
| * Function objects that perform distance comparisons modified by the * |
| * minimum or maximum edge weights. * |
| ************************************************************************/ |
| template<typename Vertex, typename DistanceMap, typename MinInWeightMap, |
| typename Combine, typename Compare> |
| struct min_in_distance_compare |
| : std::binary_function<Vertex, Vertex, bool> |
| { |
| min_in_distance_compare(DistanceMap d, MinInWeightMap m, |
| Combine combine, Compare compare) |
| : distance_map(d), min_in_weight(m), combine(combine), |
| compare(compare) |
| { |
| } |
| |
| bool operator()(const Vertex& x, const Vertex& y) const |
| { |
| return compare(combine(get(distance_map, x), -get(min_in_weight, x)), |
| combine(get(distance_map, y), -get(min_in_weight, y))); |
| } |
| |
| private: |
| DistanceMap distance_map; |
| MinInWeightMap min_in_weight; |
| Combine combine; |
| Compare compare; |
| }; |
| |
| template<typename Vertex, typename DistanceMap, typename MinOutWeightMap, |
| typename Combine, typename Compare> |
| struct min_out_distance_compare |
| : std::binary_function<Vertex, Vertex, bool> |
| { |
| min_out_distance_compare(DistanceMap d, MinOutWeightMap m, |
| Combine combine, Compare compare) |
| : distance_map(d), min_out_weight(m), combine(combine), |
| compare(compare) |
| { |
| } |
| |
| bool operator()(const Vertex& x, const Vertex& y) const |
| { |
| return compare(combine(get(distance_map, x), get(min_out_weight, x)), |
| combine(get(distance_map, y), get(min_out_weight, y))); |
| } |
| |
| private: |
| DistanceMap distance_map; |
| MinOutWeightMap min_out_weight; |
| Combine combine; |
| Compare compare; |
| }; |
| /************************************************************************/ |
| |
| /************************************************************************ |
| * Dijkstra queue that implements Crauser et al.'s criteria. This queue * |
| * actually stores three separate priority queues, to help expose all * |
| * vertices that can be processed in a single phase. * |
| ************************************************************************/ |
| template<typename Graph, typename Combine, |
| typename Compare, typename VertexIndexMap, typename DistanceMap, |
| typename PredecessorMap, typename MinOutWeightMap, |
| typename MinInWeightMap> |
| class crauser_et_al_dijkstra_queue |
| : public graph::detail::remote_update_set< |
| crauser_et_al_dijkstra_queue< |
| Graph, Combine, Compare, VertexIndexMap, DistanceMap, |
| PredecessorMap, MinOutWeightMap, MinInWeightMap>, |
| typename boost::graph::parallel::process_group_type<Graph>::type, |
| typename dijkstra_msg_value<DistanceMap, PredecessorMap>::type, |
| typename property_map<Graph, vertex_owner_t>::const_type> |
| { |
| typedef typename graph_traits<Graph>::vertex_descriptor |
| vertex_descriptor; |
| typedef crauser_et_al_dijkstra_queue self_type; |
| typedef dijkstra_msg_value<DistanceMap, PredecessorMap> msg_value_creator; |
| typedef typename msg_value_creator::type msg_value_type; |
| typedef typename graph_traits<Graph>::vertices_size_type |
| vertices_size_type; |
| typedef typename property_map<Graph, vertex_owner_t>::const_type |
| OwnerPropertyMap; |
| typedef typename boost::graph::parallel::process_group_type<Graph>::type |
| process_group_type; |
| typedef graph::detail::remote_update_set<self_type, process_group_type, |
| msg_value_type, OwnerPropertyMap> |
| inherited; |
| |
| // Priority queue for tentative distances |
| typedef indirect_cmp<DistanceMap, Compare> dist_queue_compare_type; |
| |
| typedef typename property_traits<DistanceMap>::value_type distance_type; |
| |
| #ifdef MUTABLE_QUEUE |
| typedef mutable_queue<vertex_descriptor, std::vector<vertex_descriptor>, |
| dist_queue_compare_type, VertexIndexMap> dist_queue_type; |
| |
| #else |
| typedef relaxed_heap<vertex_descriptor, dist_queue_compare_type, |
| VertexIndexMap> dist_queue_type; |
| #endif // MUTABLE_QUEUE |
| |
| // Priority queue for OUT criteria |
| typedef min_out_distance_compare<vertex_descriptor, DistanceMap, |
| MinOutWeightMap, Combine, Compare> |
| out_queue_compare_type; |
| |
| #ifdef MUTABLE_QUEUE |
| typedef mutable_queue<vertex_descriptor, std::vector<vertex_descriptor>, |
| out_queue_compare_type, VertexIndexMap> out_queue_type; |
| |
| #else |
| typedef relaxed_heap<vertex_descriptor, out_queue_compare_type, |
| VertexIndexMap> out_queue_type; |
| #endif // MUTABLE_QUEUE |
| |
| // Priority queue for IN criteria |
| typedef min_in_distance_compare<vertex_descriptor, DistanceMap, |
| MinInWeightMap, Combine, Compare> |
| in_queue_compare_type; |
| |
| #ifdef MUTABLE_QUEUE |
| typedef mutable_queue<vertex_descriptor, std::vector<vertex_descriptor>, |
| in_queue_compare_type, VertexIndexMap> in_queue_type; |
| |
| #else |
| typedef relaxed_heap<vertex_descriptor, in_queue_compare_type, |
| VertexIndexMap> in_queue_type; |
| #endif // MUTABLE_QUEUE |
| |
| typedef typename process_group_type::process_id_type process_id_type; |
| |
| public: |
| typedef typename dist_queue_type::size_type size_type; |
| typedef typename dist_queue_type::value_type value_type; |
| |
| crauser_et_al_dijkstra_queue(const Graph& g, |
| const Combine& combine, |
| const Compare& compare, |
| const VertexIndexMap& id, |
| const DistanceMap& distance_map, |
| const PredecessorMap& predecessor_map, |
| const MinOutWeightMap& min_out_weight, |
| const MinInWeightMap& min_in_weight) |
| : inherited(boost::graph::parallel::process_group(g), get(vertex_owner, g)), |
| dist_queue(num_vertices(g), |
| dist_queue_compare_type(distance_map, compare), |
| id), |
| out_queue(num_vertices(g), |
| out_queue_compare_type(distance_map, min_out_weight, |
| combine, compare), |
| id), |
| in_queue(num_vertices(g), |
| in_queue_compare_type(distance_map, min_in_weight, |
| combine, compare), |
| id), |
| g(g), |
| distance_map(distance_map), |
| predecessor_map(predecessor_map), |
| min_out_weight(min_out_weight), |
| min_in_weight(min_in_weight), |
| min_distance(0), |
| min_out_distance(0) |
| #ifdef PBGL_ACCOUNTING |
| , local_deletions(0) |
| #endif |
| { } |
| |
| void push(const value_type& x) |
| { |
| msg_value_type msg_value = |
| msg_value_creator::create(get(distance_map, x), |
| predecessor_value(get(predecessor_map, x))); |
| inherited::update(x, msg_value); |
| } |
| |
| void update(const value_type& x) { push(x); } |
| |
| void pop() |
| { |
| // Remove from distance queue |
| dist_queue.remove(top_vertex); |
| |
| // Remove from OUT queue |
| out_queue.remove(top_vertex); |
| |
| // Remove from IN queue |
| in_queue.remove(top_vertex); |
| |
| #ifdef PBGL_ACCOUNTING |
| ++local_deletions; |
| #endif |
| } |
| |
| vertex_descriptor& top() { return top_vertex; } |
| const vertex_descriptor& top() const { return top_vertex; } |
| |
| bool empty() |
| { |
| inherited::collect(); |
| |
| // If there are no suitable messages, wait until we get something |
| while (!has_suitable_vertex()) { |
| if (do_synchronize()) return true; |
| } |
| // Return true only if nobody has any messages; false if we |
| // have suitable messages |
| return false; |
| } |
| |
| bool do_synchronize() |
| { |
| using boost::parallel::all_reduce; |
| using boost::parallel::minimum; |
| |
| inherited::synchronize(); |
| |
| // TBD: could use combine here, but then we need to stop using |
| // minimum<distance_type>() as the function object. |
| distance_type local_distances[2]; |
| local_distances[0] = |
| dist_queue.empty()? (std::numeric_limits<distance_type>::max)() |
| : get(distance_map, dist_queue.top()); |
| |
| local_distances[1] = |
| out_queue.empty()? (std::numeric_limits<distance_type>::max)() |
| : (get(distance_map, out_queue.top()) |
| + get(min_out_weight, out_queue.top())); |
| |
| distance_type distances[2]; |
| all_reduce(this->process_group, local_distances, local_distances + 2, |
| distances, minimum<distance_type>()); |
| min_distance = distances[0]; |
| min_out_distance = distances[1]; |
| |
| #ifdef PBGL_ACCOUNTING |
| std::size_t deletions = 0; |
| all_reduce(this->process_group, &local_deletions, &local_deletions + 1, |
| &deletions, std::plus<std::size_t>()); |
| if (process_id(this->process_group) == 0) { |
| crauser_et_al_shortest_paths_stats.deleted_vertices.push_back(deletions); |
| } |
| local_deletions = 0; |
| assert(deletions > 0); |
| #endif |
| |
| return min_distance == (std::numeric_limits<distance_type>::max)(); |
| } |
| |
| private: |
| vertex_descriptor predecessor_value(vertex_descriptor v) const |
| { return v; } |
| |
| vertex_descriptor |
| predecessor_value(property_traits<dummy_property_map>::reference) const |
| { return graph_traits<Graph>::null_vertex(); } |
| |
| bool has_suitable_vertex() const |
| { |
| if (!dist_queue.empty()) { |
| top_vertex = dist_queue.top(); |
| if (get(distance_map, dist_queue.top()) <= min_out_distance) |
| return true; |
| } |
| |
| if (!in_queue.empty()) { |
| top_vertex = in_queue.top(); |
| return (get(distance_map, top_vertex) |
| - get(min_in_weight, top_vertex)) <= min_distance; |
| } |
| return false; |
| } |
| |
| public: |
| void |
| receive_update(process_id_type source, vertex_descriptor vertex, |
| distance_type distance) |
| { |
| // Update the queue if the received distance is better than |
| // the distance we know locally |
| if (distance < get(distance_map, vertex) |
| || (distance == get(distance_map, vertex) |
| && source == process_id(this->process_group))) { |
| // Update the local distance map |
| put(distance_map, vertex, distance); |
| |
| bool is_in_queue = dist_queue.contains(vertex); |
| |
| if (!is_in_queue) { |
| dist_queue.push(vertex); |
| out_queue.push(vertex); |
| in_queue.push(vertex); |
| } |
| else { |
| dist_queue.update(vertex); |
| out_queue.update(vertex); |
| in_queue.update(vertex); |
| } |
| } |
| } |
| |
| void |
| receive_update(process_id_type source, vertex_descriptor vertex, |
| std::pair<distance_type, vertex_descriptor> p) |
| { |
| if (p.first <= get(distance_map, vertex)) { |
| put(predecessor_map, vertex, p.second); |
| receive_update(source, vertex, p.first); |
| } |
| } |
| |
| private: |
| dist_queue_type dist_queue; |
| out_queue_type out_queue; |
| in_queue_type in_queue; |
| mutable value_type top_vertex; |
| const Graph& g; |
| DistanceMap distance_map; |
| PredecessorMap predecessor_map; |
| MinOutWeightMap min_out_weight; |
| MinInWeightMap min_in_weight; |
| distance_type min_distance; |
| distance_type min_out_distance; |
| #ifdef PBGL_ACCOUNTING |
| std::size_t local_deletions; |
| #endif |
| }; |
| /************************************************************************/ |
| |
| /************************************************************************ |
| * Initialize the property map that contains the minimum incoming edge * |
| * weight for each vertex. There are separate implementations for * |
| * directed, bidirectional, and undirected graph. * |
| ************************************************************************/ |
| template<typename Graph, typename MinInWeightMap, typename WeightMap, |
| typename Inf, typename Compare> |
| void |
| initialize_min_in_weights(const Graph& g, MinInWeightMap min_in_weight, |
| WeightMap weight, Inf inf, Compare compare, |
| directed_tag, incidence_graph_tag) |
| { |
| // Send minimum weights off to the owners |
| set_property_map_role(vertex_distance, min_in_weight); |
| BGL_FORALL_VERTICES_T(v, g, Graph) { |
| BGL_FORALL_OUTEDGES_T(v, e, g, Graph) { |
| if (get(weight, e) < get(min_in_weight, target(e, g))) |
| put(min_in_weight, target(e, g), get(weight, e)); |
| } |
| } |
| |
| using boost::graph::parallel::process_group; |
| synchronize(process_group(g)); |
| |
| // Replace any infinities with zeros |
| BGL_FORALL_VERTICES_T(v, g, Graph) { |
| if (get(min_in_weight, v) == inf) put(min_in_weight, v, 0); |
| } |
| } |
| |
| template<typename Graph, typename MinInWeightMap, typename WeightMap, |
| typename Inf, typename Compare> |
| void |
| initialize_min_in_weights(const Graph& g, MinInWeightMap min_in_weight, |
| WeightMap weight, Inf inf, Compare compare, |
| directed_tag, bidirectional_graph_tag) |
| { |
| #if 0 |
| typename property_map<Graph, vertex_local_t>::const_type |
| local = get(vertex_local, g); |
| |
| // This code assumes that the properties of the in-edges are |
| // available locally. This is not necessarily the case, so don't |
| // do this yet. |
| set_property_map_role(vertex_distance, min_in_weight); |
| BGL_FORALL_VERTICES_T(v, g, Graph) { |
| if (in_edges(v, g).first != in_edges(v, g).second) { |
| std::cerr << "weights(" << g.distribution().global(get(local, v)) |
| << ") = "; |
| BGL_FORALL_INEDGES_T(v, e, g, Graph) { |
| std::cerr << get(weight, e) << ' '; |
| } |
| std::cerr << std::endl; |
| put(min_in_weight, v, |
| *std::min_element |
| (make_property_map_iterator(weight, in_edges(v, g).first), |
| make_property_map_iterator(weight, in_edges(v, g).second), |
| compare)); |
| } else { |
| put(min_in_weight, v, 0); |
| } |
| std::cerr << "miw(" << g.distribution().global(get(local, v)) << ") = " |
| << get(min_in_weight, v) << std::endl; |
| } |
| #else |
| initialize_min_in_weights(g, min_in_weight, weight, inf, compare, |
| directed_tag(), incidence_graph_tag()); |
| #endif |
| } |
| |
| template<typename Graph, typename MinInWeightMap, typename WeightMap, |
| typename Inf, typename Compare> |
| inline void |
| initialize_min_in_weights(const Graph&, MinInWeightMap, WeightMap, Inf, |
| Compare, undirected_tag, bidirectional_graph_tag) |
| { |
| // In weights are the same as out weights, so do nothing |
| } |
| /************************************************************************/ |
| |
| |
| /************************************************************************ |
| * Initialize the property map that contains the minimum outgoing edge * |
| * weight for each vertex. * |
| ************************************************************************/ |
| template<typename Graph, typename MinOutWeightMap, typename WeightMap, |
| typename Compare> |
| void |
| initialize_min_out_weights(const Graph& g, MinOutWeightMap min_out_weight, |
| WeightMap weight, Compare compare) |
| { |
| typedef typename property_traits<WeightMap>::value_type weight_type; |
| |
| BGL_FORALL_VERTICES_T(v, g, Graph) { |
| if (out_edges(v, g).first != out_edges(v, g).second) { |
| put(min_out_weight, v, |
| *std::min_element |
| (make_property_map_iterator(weight, out_edges(v, g).first), |
| make_property_map_iterator(weight, out_edges(v, g).second), |
| compare)); |
| if (get(min_out_weight, v) < weight_type(0)) |
| boost::throw_exception(negative_edge()); |
| } |
| } |
| } |
| |
| /************************************************************************/ |
| |
| } // end namespace detail |
| |
| template<typename DistributedGraph, typename DijkstraVisitor, |
| typename PredecessorMap, typename DistanceMap, typename WeightMap, |
| typename IndexMap, typename ColorMap, typename Compare, |
| typename Combine, typename DistInf, typename DistZero> |
| void |
| crauser_et_al_shortest_paths |
| (const DistributedGraph& g, |
| typename graph_traits<DistributedGraph>::vertex_descriptor s, |
| PredecessorMap predecessor, DistanceMap distance, WeightMap weight, |
| IndexMap index_map, ColorMap color_map, |
| Compare compare, Combine combine, DistInf inf, DistZero zero, |
| DijkstraVisitor vis) |
| { |
| typedef typename boost::graph::parallel::process_group_type<DistributedGraph>::type |
| process_group_type; |
| typedef typename process_group_type::process_id_type process_id_type; |
| typedef typename graph_traits<DistributedGraph>::vertex_descriptor |
| Vertex; |
| typedef typename graph_traits<DistributedGraph>::vertices_size_type |
| vertices_size_type; |
| |
| #ifdef PBGL_ACCOUNTING |
| crauser_et_al_shortest_paths_stats.deleted_vertices.clear(); |
| crauser_et_al_shortest_paths_stats.execution_time = accounting::get_time(); |
| #endif |
| |
| // Property map that stores the lowest edge weight outgoing from |
| // each vertex. If a vertex has no out-edges, the stored weight |
| // is zero. |
| typedef typename property_traits<WeightMap>::value_type weight_type; |
| typedef iterator_property_map<weight_type*, IndexMap> MinOutWeightMap; |
| std::vector<weight_type> min_out_weights_vec(num_vertices(g), inf); |
| MinOutWeightMap min_out_weight(&min_out_weights_vec.front(), index_map); |
| detail::initialize_min_out_weights(g, min_out_weight, weight, compare); |
| |
| // Property map that stores the lowest edge weight incoming to |
| // each vertex. For undirected graphs, this will just be a |
| // shallow copy of the version for outgoing edges. |
| typedef typename graph_traits<DistributedGraph>::directed_category |
| directed_category; |
| const bool is_undirected = |
| is_same<directed_category, undirected_tag>::value; |
| typedef MinOutWeightMap MinInWeightMap; |
| std::vector<weight_type> |
| min_in_weights_vec(is_undirected? 1 : num_vertices(g), inf); |
| MinInWeightMap min_in_weight(&min_in_weights_vec.front(), index_map); |
| typedef typename graph_traits<DistributedGraph>::traversal_category |
| category; |
| detail::initialize_min_in_weights(g, min_in_weight, weight, inf, compare, |
| directed_category(), category()); |
| |
| // Initialize local portion of property maps |
| typename graph_traits<DistributedGraph>::vertex_iterator ui, ui_end; |
| for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) { |
| put(distance, *ui, inf); |
| put(predecessor, *ui, *ui); |
| } |
| put(distance, s, zero); |
| |
| // Dijkstra Queue |
| typedef detail::crauser_et_al_dijkstra_queue |
| <DistributedGraph, Combine, Compare, IndexMap, DistanceMap, |
| PredecessorMap, MinOutWeightMap, MinInWeightMap> |
| Queue; |
| |
| Queue Q(g, combine, compare, index_map, distance, predecessor, |
| min_out_weight, is_undirected? min_out_weight : min_in_weight); |
| |
| // Parallel Dijkstra visitor |
| ::boost::detail::dijkstra_bfs_visitor< |
| DijkstraVisitor, Queue, WeightMap, |
| boost::parallel::caching_property_map<PredecessorMap>, |
| boost::parallel::caching_property_map<DistanceMap>, Combine, Compare |
| > bfs_vis(vis, Q, weight, |
| boost::parallel::make_caching_property_map(predecessor), |
| boost::parallel::make_caching_property_map(distance), |
| combine, compare, zero); |
| |
| set_property_map_role(vertex_color, color_map); |
| set_property_map_role(vertex_distance, distance); |
| |
| breadth_first_search(g, s, Q, bfs_vis, color_map); |
| |
| #ifdef PBGL_ACCOUNTING |
| crauser_et_al_shortest_paths_stats.execution_time = |
| accounting::get_time() - crauser_et_al_shortest_paths_stats.execution_time; |
| #endif |
| } |
| |
| template<typename DistributedGraph, typename PredecessorMap, |
| typename DistanceMap, typename WeightMap> |
| void |
| crauser_et_al_shortest_paths |
| (const DistributedGraph& g, |
| typename graph_traits<DistributedGraph>::vertex_descriptor s, |
| PredecessorMap predecessor, DistanceMap distance, WeightMap weight) |
| { |
| typedef typename property_traits<DistanceMap>::value_type distance_type; |
| |
| std::vector<default_color_type> colors(num_vertices(g), white_color); |
| |
| crauser_et_al_shortest_paths(g, s, predecessor, distance, weight, |
| get(vertex_index, g), |
| make_iterator_property_map(&colors[0], |
| get(vertex_index, g)), |
| std::less<distance_type>(), |
| closed_plus<distance_type>(), |
| (std::numeric_limits<distance_type>::max)(), |
| distance_type(), |
| dijkstra_visitor<>()); |
| } |
| |
| template<typename DistributedGraph, typename PredecessorMap, |
| typename DistanceMap> |
| void |
| crauser_et_al_shortest_paths |
| (const DistributedGraph& g, |
| typename graph_traits<DistributedGraph>::vertex_descriptor s, |
| PredecessorMap predecessor, DistanceMap distance) |
| { |
| crauser_et_al_shortest_paths(g, s, predecessor, distance, |
| get(edge_weight, g)); |
| } |
| |
| } // end namespace distributed |
| |
| #ifdef PBGL_ACCOUNTING |
| using distributed::crauser_et_al_shortest_paths_stats; |
| #endif |
| |
| using distributed::crauser_et_al_shortest_paths; |
| |
| |
| } } // end namespace boost::graph |
| |
| #endif // BOOST_GRAPH_CRAUSER_ET_AL_SHORTEST_PATHS_HPP |