| //======================================================================= |
| // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. |
| // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek |
| // |
| // Distributed under 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) |
| //======================================================================= |
| // |
| // |
| // Revision History: |
| // 04 April 2001: Added named parameter variant. (Jeremy Siek) |
| // 01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock) |
| // |
| #ifndef BOOST_GRAPH_DIJKSTRA_HPP |
| #define BOOST_GRAPH_DIJKSTRA_HPP |
| |
| #include <functional> |
| #include <boost/limits.hpp> |
| #include <boost/graph/named_function_params.hpp> |
| #include <boost/graph/breadth_first_search.hpp> |
| #include <boost/graph/relax.hpp> |
| #include <boost/pending/indirect_cmp.hpp> |
| #include <boost/graph/exception.hpp> |
| #include <boost/pending/relaxed_heap.hpp> |
| #include <boost/graph/overloading.hpp> |
| #include <boost/smart_ptr.hpp> |
| #include <boost/graph/detail/d_ary_heap.hpp> |
| #include <boost/graph/two_bit_color_map.hpp> |
| #include <boost/property_map/property_map.hpp> |
| #include <boost/property_map/vector_property_map.hpp> |
| #include <boost/type_traits.hpp> |
| |
| #ifdef BOOST_GRAPH_DIJKSTRA_TESTING |
| # include <boost/pending/mutable_queue.hpp> |
| #endif // BOOST_GRAPH_DIJKSTRA_TESTING |
| |
| namespace boost { |
| |
| /** |
| * @brief Updates a particular value in a queue used by Dijkstra's |
| * algorithm. |
| * |
| * This routine is called by Dijkstra's algorithm after it has |
| * decreased the distance from the source vertex to the given @p |
| * vertex. By default, this routine will just call @c |
| * Q.update(vertex). However, other queues may provide more |
| * specialized versions of this routine. |
| * |
| * @param Q the queue that will be updated. |
| * @param vertex the vertex whose distance has been updated |
| * @param old_distance the previous distance to @p vertex |
| */ |
| template<typename Buffer, typename Vertex, typename DistanceType> |
| inline void |
| dijkstra_queue_update(Buffer& Q, Vertex vertex, DistanceType old_distance) |
| { |
| (void)old_distance; |
| Q.update(vertex); |
| } |
| |
| #ifdef BOOST_GRAPH_DIJKSTRA_TESTING |
| // This is a misnomer now: it now just refers to the "default heap", which is |
| // currently d-ary (d=4) but can be changed by a #define. |
| static bool dijkstra_relaxed_heap = true; |
| #endif |
| |
| template <class Visitor, class Graph> |
| struct DijkstraVisitorConcept { |
| void constraints() { |
| function_requires< CopyConstructibleConcept<Visitor> >(); |
| vis.initialize_vertex(u, g); |
| vis.discover_vertex(u, g); |
| vis.examine_vertex(u, g); |
| vis.examine_edge(e, g); |
| vis.edge_relaxed(e, g); |
| vis.edge_not_relaxed(e, g); |
| vis.finish_vertex(u, g); |
| } |
| Visitor vis; |
| Graph g; |
| typename graph_traits<Graph>::vertex_descriptor u; |
| typename graph_traits<Graph>::edge_descriptor e; |
| }; |
| |
| template <class Visitors = null_visitor> |
| class dijkstra_visitor : public bfs_visitor<Visitors> { |
| public: |
| dijkstra_visitor() { } |
| dijkstra_visitor(Visitors vis) |
| : bfs_visitor<Visitors>(vis) { } |
| |
| template <class Edge, class Graph> |
| void edge_relaxed(Edge e, Graph& g) { |
| invoke_visitors(this->m_vis, e, g, on_edge_relaxed()); |
| } |
| template <class Edge, class Graph> |
| void edge_not_relaxed(Edge e, Graph& g) { |
| invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed()); |
| } |
| private: |
| template <class Edge, class Graph> |
| void tree_edge(Edge u, Graph& g) { } |
| }; |
| template <class Visitors> |
| dijkstra_visitor<Visitors> |
| make_dijkstra_visitor(Visitors vis) { |
| return dijkstra_visitor<Visitors>(vis); |
| } |
| typedef dijkstra_visitor<> default_dijkstra_visitor; |
| |
| namespace detail { |
| |
| template <class UniformCostVisitor, class UpdatableQueue, |
| class WeightMap, class PredecessorMap, class DistanceMap, |
| class BinaryFunction, class BinaryPredicate> |
| struct dijkstra_bfs_visitor |
| { |
| typedef typename property_traits<DistanceMap>::value_type D; |
| |
| dijkstra_bfs_visitor(UniformCostVisitor vis, UpdatableQueue& Q, |
| WeightMap w, PredecessorMap p, DistanceMap d, |
| BinaryFunction combine, BinaryPredicate compare, |
| D zero) |
| : m_vis(vis), m_Q(Q), m_weight(w), m_predecessor(p), m_distance(d), |
| m_combine(combine), m_compare(compare), m_zero(zero) { } |
| |
| template <class Edge, class Graph> |
| void tree_edge(Edge e, Graph& g) { |
| bool decreased = relax(e, g, m_weight, m_predecessor, m_distance, |
| m_combine, m_compare); |
| if (decreased) |
| m_vis.edge_relaxed(e, g); |
| else |
| m_vis.edge_not_relaxed(e, g); |
| } |
| template <class Edge, class Graph> |
| void gray_target(Edge e, Graph& g) { |
| D old_distance = get(m_distance, target(e, g)); |
| |
| bool decreased = relax(e, g, m_weight, m_predecessor, m_distance, |
| m_combine, m_compare); |
| if (decreased) { |
| dijkstra_queue_update(m_Q, target(e, g), old_distance); |
| m_vis.edge_relaxed(e, g); |
| } else |
| m_vis.edge_not_relaxed(e, g); |
| } |
| |
| template <class Vertex, class Graph> |
| void initialize_vertex(Vertex u, Graph& g) |
| { m_vis.initialize_vertex(u, g); } |
| template <class Edge, class Graph> |
| void non_tree_edge(Edge, Graph&) { } |
| template <class Vertex, class Graph> |
| void discover_vertex(Vertex u, Graph& g) { m_vis.discover_vertex(u, g); } |
| template <class Vertex, class Graph> |
| void examine_vertex(Vertex u, Graph& g) { m_vis.examine_vertex(u, g); } |
| template <class Edge, class Graph> |
| void examine_edge(Edge e, Graph& g) { |
| if (m_compare(get(m_weight, e), m_zero)) |
| boost::throw_exception(negative_edge()); |
| m_vis.examine_edge(e, g); |
| } |
| template <class Edge, class Graph> |
| void black_target(Edge, Graph&) { } |
| template <class Vertex, class Graph> |
| void finish_vertex(Vertex u, Graph& g) { m_vis.finish_vertex(u, g); } |
| |
| UniformCostVisitor m_vis; |
| UpdatableQueue& m_Q; |
| WeightMap m_weight; |
| PredecessorMap m_predecessor; |
| DistanceMap m_distance; |
| BinaryFunction m_combine; |
| BinaryPredicate m_compare; |
| D m_zero; |
| }; |
| |
| } // namespace detail |
| |
| namespace detail { |
| template <class Graph, class IndexMap, class Value, bool KnownNumVertices> |
| struct vertex_property_map_generator_helper {}; |
| |
| template <class Graph, class IndexMap, class Value> |
| struct vertex_property_map_generator_helper<Graph, IndexMap, Value, true> { |
| typedef boost::iterator_property_map<Value*, IndexMap> type; |
| static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) { |
| array_holder.reset(new Value[num_vertices(g)]); |
| std::fill(array_holder.get(), array_holder.get() + num_vertices(g), Value()); |
| return make_iterator_property_map(array_holder.get(), index); |
| } |
| }; |
| |
| template <class Graph, class IndexMap, class Value> |
| struct vertex_property_map_generator_helper<Graph, IndexMap, Value, false> { |
| typedef boost::vector_property_map<Value, IndexMap> type; |
| static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) { |
| return boost::make_vector_property_map<Value>(index); |
| } |
| }; |
| |
| template <class Graph, class IndexMap, class Value> |
| struct vertex_property_map_generator { |
| typedef boost::is_base_and_derived< |
| boost::vertex_list_graph_tag, |
| typename boost::graph_traits<Graph>::traversal_category> |
| known_num_vertices; |
| typedef vertex_property_map_generator_helper<Graph, IndexMap, Value, known_num_vertices::value> helper; |
| typedef typename helper::type type; |
| static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) { |
| return helper::build(g, index, array_holder); |
| } |
| }; |
| } |
| |
| namespace detail { |
| template <class Graph, class IndexMap, bool KnownNumVertices> |
| struct default_color_map_generator_helper {}; |
| |
| template <class Graph, class IndexMap> |
| struct default_color_map_generator_helper<Graph, IndexMap, true> { |
| typedef boost::two_bit_color_map<IndexMap> type; |
| static type build(const Graph& g, const IndexMap& index) { |
| size_t nv = num_vertices(g); |
| return boost::two_bit_color_map<IndexMap>(nv, index); |
| } |
| }; |
| |
| template <class Graph, class IndexMap> |
| struct default_color_map_generator_helper<Graph, IndexMap, false> { |
| typedef boost::vector_property_map<boost::two_bit_color_type, IndexMap> type; |
| static type build(const Graph& g, const IndexMap& index) { |
| return boost::make_vector_property_map<boost::two_bit_color_type>(index); |
| } |
| }; |
| |
| template <class Graph, class IndexMap> |
| struct default_color_map_generator { |
| typedef boost::is_base_and_derived< |
| boost::vertex_list_graph_tag, |
| typename boost::graph_traits<Graph>::traversal_category> |
| known_num_vertices; |
| typedef default_color_map_generator_helper<Graph, IndexMap, known_num_vertices::value> helper; |
| typedef typename helper::type type; |
| static type build(const Graph& g, const IndexMap& index) { |
| return helper::build(g, index); |
| } |
| }; |
| } |
| |
| // Call breadth first search with default color map. |
| template <class Graph, class DijkstraVisitor, |
| class PredecessorMap, class DistanceMap, |
| class WeightMap, class IndexMap, class Compare, class Combine, |
| class DistZero> |
| inline void |
| dijkstra_shortest_paths_no_init |
| (const Graph& g, |
| typename graph_traits<Graph>::vertex_descriptor s, |
| PredecessorMap predecessor, DistanceMap distance, WeightMap weight, |
| IndexMap index_map, |
| Compare compare, Combine combine, DistZero zero, |
| DijkstraVisitor vis) |
| { |
| typedef |
| detail::default_color_map_generator<Graph, IndexMap> |
| ColorMapHelper; |
| typedef typename ColorMapHelper::type ColorMap; |
| ColorMap color = |
| ColorMapHelper::build(g, index_map); |
| dijkstra_shortest_paths_no_init( g, s, predecessor, distance, weight, |
| index_map, compare, combine, zero, vis, |
| color); |
| } |
| |
| // Call breadth first search |
| template <class Graph, class DijkstraVisitor, |
| class PredecessorMap, class DistanceMap, |
| class WeightMap, class IndexMap, class Compare, class Combine, |
| class DistZero, class ColorMap> |
| inline void |
| dijkstra_shortest_paths_no_init |
| (const Graph& g, |
| typename graph_traits<Graph>::vertex_descriptor s, |
| PredecessorMap predecessor, DistanceMap distance, WeightMap weight, |
| IndexMap index_map, |
| Compare compare, Combine combine, DistZero zero, |
| DijkstraVisitor vis, ColorMap color) |
| { |
| typedef indirect_cmp<DistanceMap, Compare> IndirectCmp; |
| IndirectCmp icmp(distance, compare); |
| |
| typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
| |
| #ifdef BOOST_GRAPH_DIJKSTRA_TESTING |
| if (!dijkstra_relaxed_heap) { |
| typedef mutable_queue<Vertex, std::vector<Vertex>, IndirectCmp, IndexMap> |
| MutableQueue; |
| |
| MutableQueue Q(num_vertices(g), icmp, index_map); |
| detail::dijkstra_bfs_visitor<DijkstraVisitor, MutableQueue, WeightMap, |
| PredecessorMap, DistanceMap, Combine, Compare> |
| bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero); |
| |
| breadth_first_visit(g, s, Q, bfs_vis, color); |
| return; |
| } |
| #endif // BOOST_GRAPH_DIJKSTRA_TESTING |
| |
| #ifdef BOOST_GRAPH_DIJKSTRA_USE_RELAXED_HEAP |
| typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue; |
| MutableQueue Q(num_vertices(g), icmp, index_map); |
| #else // Now the default: use a d-ary heap |
| boost::scoped_array<std::size_t> index_in_heap_map_holder; |
| typedef |
| detail::vertex_property_map_generator<Graph, IndexMap, std::size_t> |
| IndexInHeapMapHelper; |
| typedef typename IndexInHeapMapHelper::type IndexInHeapMap; |
| IndexInHeapMap index_in_heap = |
| IndexInHeapMapHelper::build(g, index_map, index_in_heap_map_holder); |
| typedef d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, DistanceMap, Compare> |
| MutableQueue; |
| MutableQueue Q(distance, index_in_heap, compare); |
| #endif // Relaxed heap |
| |
| detail::dijkstra_bfs_visitor<DijkstraVisitor, MutableQueue, WeightMap, |
| PredecessorMap, DistanceMap, Combine, Compare> |
| bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero); |
| |
| breadth_first_visit(g, s, Q, bfs_vis, color); |
| } |
| |
| // Initialize distances and call breadth first search with default color map |
| template <class VertexListGraph, class DijkstraVisitor, |
| class PredecessorMap, class DistanceMap, |
| class WeightMap, class IndexMap, class Compare, class Combine, |
| class DistInf, class DistZero, typename T, typename Tag, |
| typename Base> |
| inline void |
| dijkstra_shortest_paths |
| (const VertexListGraph& g, |
| typename graph_traits<VertexListGraph>::vertex_descriptor s, |
| PredecessorMap predecessor, DistanceMap distance, WeightMap weight, |
| IndexMap index_map, |
| Compare compare, Combine combine, DistInf inf, DistZero zero, |
| DijkstraVisitor vis, |
| const bgl_named_params<T, Tag, Base>& |
| BOOST_GRAPH_ENABLE_IF_MODELS_PARM(VertexListGraph,vertex_list_graph_tag)) |
| { |
| boost::two_bit_color_map<IndexMap> color(num_vertices(g), index_map); |
| dijkstra_shortest_paths(g, s, predecessor, distance, weight, index_map, |
| compare, combine, inf, zero, vis, |
| color); |
| } |
| |
| // Initialize distances and call breadth first search |
| template <class VertexListGraph, class DijkstraVisitor, |
| class PredecessorMap, class DistanceMap, |
| class WeightMap, class IndexMap, class Compare, class Combine, |
| class DistInf, class DistZero, class ColorMap> |
| inline void |
| dijkstra_shortest_paths |
| (const VertexListGraph& g, |
| typename graph_traits<VertexListGraph>::vertex_descriptor s, |
| PredecessorMap predecessor, DistanceMap distance, WeightMap weight, |
| IndexMap index_map, |
| Compare compare, Combine combine, DistInf inf, DistZero zero, |
| DijkstraVisitor vis, ColorMap color) |
| { |
| typedef typename property_traits<ColorMap>::value_type ColorValue; |
| typedef color_traits<ColorValue> Color; |
| typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end; |
| for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) { |
| vis.initialize_vertex(*ui, g); |
| put(distance, *ui, inf); |
| put(predecessor, *ui, *ui); |
| put(color, *ui, Color::white()); |
| } |
| put(distance, s, zero); |
| |
| dijkstra_shortest_paths_no_init(g, s, predecessor, distance, weight, |
| index_map, compare, combine, zero, vis, color); |
| } |
| |
| // Initialize distances and call breadth first search |
| template <class VertexListGraph, class DijkstraVisitor, |
| class PredecessorMap, class DistanceMap, |
| class WeightMap, class IndexMap, class Compare, class Combine, |
| class DistInf, class DistZero> |
| inline void |
| dijkstra_shortest_paths |
| (const VertexListGraph& g, |
| typename graph_traits<VertexListGraph>::vertex_descriptor s, |
| PredecessorMap predecessor, DistanceMap distance, WeightMap weight, |
| IndexMap index_map, |
| Compare compare, Combine combine, DistInf inf, DistZero zero, |
| DijkstraVisitor vis) |
| { |
| dijkstra_shortest_paths(g, s, predecessor, distance, weight, index_map, |
| compare, combine, inf, zero, vis, |
| no_named_parameters()); |
| } |
| |
| namespace detail { |
| |
| // Handle defaults for PredecessorMap and |
| // Distance Compare, Combine, Inf and Zero |
| template <class VertexListGraph, class DistanceMap, class WeightMap, |
| class IndexMap, class Params> |
| inline void |
| dijkstra_dispatch2 |
| (const VertexListGraph& g, |
| typename graph_traits<VertexListGraph>::vertex_descriptor s, |
| DistanceMap distance, WeightMap weight, IndexMap index_map, |
| const Params& params) |
| { |
| // Default for predecessor map |
| dummy_property_map p_map; |
| |
| typedef typename property_traits<DistanceMap>::value_type D; |
| dijkstra_shortest_paths |
| (g, s, |
| choose_param(get_param(params, vertex_predecessor), p_map), |
| distance, weight, index_map, |
| choose_param(get_param(params, distance_compare_t()), |
| std::less<D>()), |
| choose_param(get_param(params, distance_combine_t()), |
| closed_plus<D>()), |
| choose_param(get_param(params, distance_inf_t()), |
| (std::numeric_limits<D>::max)()), |
| choose_param(get_param(params, distance_zero_t()), |
| D()), |
| choose_param(get_param(params, graph_visitor), |
| make_dijkstra_visitor(null_visitor())), |
| params); |
| } |
| |
| template <class VertexListGraph, class DistanceMap, class WeightMap, |
| class IndexMap, class Params> |
| inline void |
| dijkstra_dispatch1 |
| (const VertexListGraph& g, |
| typename graph_traits<VertexListGraph>::vertex_descriptor s, |
| DistanceMap distance, WeightMap weight, IndexMap index_map, |
| const Params& params) |
| { |
| // Default for distance map |
| typedef typename property_traits<WeightMap>::value_type D; |
| typename std::vector<D>::size_type |
| n = is_default_param(distance) ? num_vertices(g) : 1; |
| std::vector<D> distance_map(n); |
| |
| detail::dijkstra_dispatch2 |
| (g, s, choose_param(distance, make_iterator_property_map |
| (distance_map.begin(), index_map, |
| distance_map[0])), |
| weight, index_map, params); |
| } |
| } // namespace detail |
| |
| // Named Parameter Variant |
| template <class VertexListGraph, class Param, class Tag, class Rest> |
| inline void |
| dijkstra_shortest_paths |
| (const VertexListGraph& g, |
| typename graph_traits<VertexListGraph>::vertex_descriptor s, |
| const bgl_named_params<Param,Tag,Rest>& params) |
| { |
| // Default for edge weight and vertex index map is to ask for them |
| // from the graph. Default for the visitor is null_visitor. |
| detail::dijkstra_dispatch1 |
| (g, s, |
| get_param(params, vertex_distance), |
| choose_const_pmap(get_param(params, edge_weight), g, edge_weight), |
| choose_const_pmap(get_param(params, vertex_index), g, vertex_index), |
| params); |
| } |
| |
| } // namespace boost |
| |
| #ifdef BOOST_GRAPH_USE_MPI |
| # include <boost/graph/distributed/dijkstra_shortest_paths.hpp> |
| #endif |
| |
| #endif // BOOST_GRAPH_DIJKSTRA_HPP |