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