williamr@2: //=======================================================================
williamr@2: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
williamr@2: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
williamr@2: //
williamr@2: // Distributed under the Boost Software License, Version 1.0. (See
williamr@2: // accompanying file LICENSE_1_0.txt or copy at
williamr@2: // http://www.boost.org/LICENSE_1_0.txt)
williamr@2: //=======================================================================
williamr@2: #ifndef BOOST_GRAPH_DIJKSTRA_HPP
williamr@2: #define BOOST_GRAPH_DIJKSTRA_HPP
williamr@2: 
williamr@2: #include <functional>
williamr@2: #include <boost/limits.hpp>
williamr@2: #include <boost/graph/named_function_params.hpp>
williamr@2: #include <boost/graph/breadth_first_search.hpp>
williamr@2: #include <boost/graph/relax.hpp>
williamr@2: #include <boost/pending/indirect_cmp.hpp>
williamr@2: #include <boost/graph/exception.hpp>
williamr@2: #include <boost/pending/relaxed_heap.hpp>
williamr@2: 
williamr@2: #ifdef BOOST_GRAPH_DIJKSTRA_TESTING
williamr@2: #  include <boost/pending/mutable_queue.hpp>
williamr@2: #endif // BOOST_GRAPH_DIJKSTRA_TESTING
williamr@2: 
williamr@2: namespace boost {
williamr@2: 
williamr@2: #ifdef BOOST_GRAPH_DIJKSTRA_TESTING
williamr@2:   static bool dijkstra_relaxed_heap = true;
williamr@2: #endif
williamr@2: 
williamr@2:   template <class Visitor, class Graph>
williamr@2:   struct DijkstraVisitorConcept {
williamr@2:     void constraints() {
williamr@2:       function_requires< CopyConstructibleConcept<Visitor> >();
williamr@2:       vis.initialize_vertex(u, g);
williamr@2:       vis.discover_vertex(u, g);
williamr@2:       vis.examine_vertex(u, g);
williamr@2:       vis.examine_edge(e, g);
williamr@2:       vis.edge_relaxed(e, g);
williamr@2:       vis.edge_not_relaxed(e, g);
williamr@2:       vis.finish_vertex(u, g);
williamr@2:     }
williamr@2:     Visitor vis;
williamr@2:     Graph g;
williamr@2:     typename graph_traits<Graph>::vertex_descriptor u;
williamr@2:     typename graph_traits<Graph>::edge_descriptor e;
williamr@2:   };
williamr@2: 
williamr@2:   template <class Visitors = null_visitor>
williamr@2:   class dijkstra_visitor : public bfs_visitor<Visitors> {
williamr@2:   public:
williamr@2:     dijkstra_visitor() { }
williamr@2:     dijkstra_visitor(Visitors vis)
williamr@2:       : bfs_visitor<Visitors>(vis) { }
williamr@2: 
williamr@2:     template <class Edge, class Graph>
williamr@2:     void edge_relaxed(Edge e, Graph& g) {
williamr@2:       invoke_visitors(this->m_vis, e, g, on_edge_relaxed());
williamr@2:     }
williamr@2:     template <class Edge, class Graph>
williamr@2:     void edge_not_relaxed(Edge e, Graph& g) {
williamr@2:       invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed());
williamr@2:     }
williamr@2:   private:
williamr@2:     template <class Edge, class Graph>
williamr@2:     void tree_edge(Edge u, Graph& g) { }
williamr@2:   };
williamr@2:   template <class Visitors>
williamr@2:   dijkstra_visitor<Visitors>
williamr@2:   make_dijkstra_visitor(Visitors vis) {
williamr@2:     return dijkstra_visitor<Visitors>(vis);
williamr@2:   }
williamr@2:   typedef dijkstra_visitor<> default_dijkstra_visitor;
williamr@2: 
williamr@2:   namespace detail {
williamr@2: 
williamr@2:     template <class UniformCostVisitor, class UpdatableQueue,
williamr@2:       class WeightMap, class PredecessorMap, class DistanceMap,
williamr@2:       class BinaryFunction, class BinaryPredicate>
williamr@2:     struct dijkstra_bfs_visitor
williamr@2:     {
williamr@2:       typedef typename property_traits<DistanceMap>::value_type D;
williamr@2: 
williamr@2:       dijkstra_bfs_visitor(UniformCostVisitor vis, UpdatableQueue& Q,
williamr@2:                            WeightMap w, PredecessorMap p, DistanceMap d,
williamr@2:                            BinaryFunction combine, BinaryPredicate compare,
williamr@2:                            D zero)
williamr@2:         : m_vis(vis), m_Q(Q), m_weight(w), m_predecessor(p), m_distance(d),
williamr@2:           m_combine(combine), m_compare(compare), m_zero(zero)  { }
williamr@2: 
williamr@2:       template <class Edge, class Graph>
williamr@2:       void tree_edge(Edge e, Graph& g) {
williamr@2:         m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
williamr@2:                             m_combine, m_compare);
williamr@2:         if (m_decreased)
williamr@2:           m_vis.edge_relaxed(e, g);
williamr@2:         else
williamr@2:           m_vis.edge_not_relaxed(e, g);
williamr@2:       }
williamr@2:       template <class Edge, class Graph>
williamr@2:       void gray_target(Edge e, Graph& g) {
williamr@2:         m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
williamr@2:                             m_combine, m_compare);
williamr@2:         if (m_decreased) {
williamr@2:           m_Q.update(target(e, g));
williamr@2:           m_vis.edge_relaxed(e, g);
williamr@2:         } else
williamr@2:           m_vis.edge_not_relaxed(e, g);
williamr@2:       }
williamr@2: 
williamr@2:       template <class Vertex, class Graph>
williamr@2:       void initialize_vertex(Vertex u, Graph& g) { }
williamr@2:       template <class Edge, class Graph>
williamr@2:       void non_tree_edge(Edge, Graph&) { }
williamr@2:       template <class Vertex, class Graph>
williamr@2:       void discover_vertex(Vertex u, Graph& g) { m_vis.discover_vertex(u, g); }
williamr@2:       template <class Vertex, class Graph>
williamr@2:       void examine_vertex(Vertex u, Graph& g) { m_vis.examine_vertex(u, g); }
williamr@2:       template <class Edge, class Graph>
williamr@2:       void examine_edge(Edge e, Graph& g) {
williamr@2:         if (m_compare(get(m_weight, e), m_zero))
williamr@2:           throw negative_edge();
williamr@2:         m_vis.examine_edge(e, g);
williamr@2:       }
williamr@2:       template <class Edge, class Graph>
williamr@2:       void black_target(Edge, Graph&) { }
williamr@2:       template <class Vertex, class Graph>
williamr@2:       void finish_vertex(Vertex u, Graph& g) { m_vis.finish_vertex(u, g); }
williamr@2: 
williamr@2:       UniformCostVisitor m_vis;
williamr@2:       UpdatableQueue& m_Q;
williamr@2:       WeightMap m_weight;
williamr@2:       PredecessorMap m_predecessor;
williamr@2:       DistanceMap m_distance;
williamr@2:       BinaryFunction m_combine;
williamr@2:       BinaryPredicate m_compare;
williamr@2:       bool m_decreased;
williamr@2:       D m_zero;
williamr@2:     };
williamr@2: 
williamr@2:   } // namespace detail
williamr@2: 
williamr@2:   // Call breadth first search with default color map.
williamr@2:   template <class VertexListGraph, class DijkstraVisitor,
williamr@2:             class PredecessorMap, class DistanceMap,
williamr@2:             class WeightMap, class IndexMap, class Compare, class Combine,
williamr@2:             class DistZero>
williamr@2:   inline void
williamr@2:   dijkstra_shortest_paths_no_init
williamr@2:     (const VertexListGraph& g,
williamr@2:      typename graph_traits<VertexListGraph>::vertex_descriptor s,
williamr@2:      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
williamr@2:      IndexMap index_map,
williamr@2:      Compare compare, Combine combine, DistZero zero,
williamr@2:      DijkstraVisitor vis)
williamr@2:   {
williamr@2:     std::vector<default_color_type> color(num_vertices(g));
williamr@2:     default_color_type c = white_color;
williamr@2:     dijkstra_shortest_paths_no_init( g, s, predecessor, distance, weight,
williamr@2:       index_map, compare, combine, zero, vis,
williamr@2:         make_iterator_property_map(&color[0], index_map, c));
williamr@2:   }
williamr@2: 
williamr@2:   // Call breadth first search
williamr@2:   template <class VertexListGraph, class DijkstraVisitor,
williamr@2:             class PredecessorMap, class DistanceMap,
williamr@2:             class WeightMap, class IndexMap, class Compare, class Combine,
williamr@2:             class DistZero, class ColorMap>
williamr@2:   inline void
williamr@2:   dijkstra_shortest_paths_no_init
williamr@2:     (const VertexListGraph& g,
williamr@2:      typename graph_traits<VertexListGraph>::vertex_descriptor s,
williamr@2:      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
williamr@2:      IndexMap index_map,
williamr@2:      Compare compare, Combine combine, DistZero zero,
williamr@2:      DijkstraVisitor vis, ColorMap color)
williamr@2:   {
williamr@2:     typedef indirect_cmp<DistanceMap, Compare> IndirectCmp;
williamr@2:     IndirectCmp icmp(distance, compare);
williamr@2: 
williamr@2:     typedef typename graph_traits<VertexListGraph>::vertex_descriptor Vertex;
williamr@2: 
williamr@2: #ifdef BOOST_GRAPH_DIJKSTRA_TESTING
williamr@2:     if (!dijkstra_relaxed_heap) {
williamr@2:       typedef mutable_queue<Vertex, std::vector<Vertex>, IndirectCmp, IndexMap>
williamr@2:         MutableQueue;
williamr@2: 
williamr@2:       MutableQueue Q(num_vertices(g), icmp, index_map);
williamr@2: 
williamr@2:       detail::dijkstra_bfs_visitor<DijkstraVisitor, MutableQueue, WeightMap,
williamr@2:         PredecessorMap, DistanceMap, Combine, Compare>
williamr@2:       bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero);
williamr@2: 
williamr@2:       breadth_first_visit(g, s, Q, bfs_vis, color);
williamr@2:       return;
williamr@2:     }
williamr@2: #endif // BOOST_GRAPH_DIJKSTRA_TESTING
williamr@2: 
williamr@2:     typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue;
williamr@2: 
williamr@2:     MutableQueue Q(num_vertices(g), icmp, index_map);
williamr@2: 
williamr@2:     detail::dijkstra_bfs_visitor<DijkstraVisitor, MutableQueue, WeightMap,
williamr@2:       PredecessorMap, DistanceMap, Combine, Compare>
williamr@2:         bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero);
williamr@2: 
williamr@2:     breadth_first_visit(g, s, Q, bfs_vis, color);
williamr@2:   }
williamr@2: 
williamr@2:   // Initialize distances and call breadth first search with default color map
williamr@2:   template <class VertexListGraph, class DijkstraVisitor,
williamr@2:             class PredecessorMap, class DistanceMap,
williamr@2:             class WeightMap, class IndexMap, class Compare, class Combine,
williamr@2:             class DistInf, class DistZero>
williamr@2:   inline void
williamr@2:   dijkstra_shortest_paths
williamr@2:     (const VertexListGraph& g,
williamr@2:      typename graph_traits<VertexListGraph>::vertex_descriptor s,
williamr@2:      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
williamr@2:      IndexMap index_map,
williamr@2:      Compare compare, Combine combine, DistInf inf, DistZero zero,
williamr@2:      DijkstraVisitor vis)
williamr@2:   {
williamr@2:     std::vector<default_color_type> color(num_vertices(g));
williamr@2:     default_color_type c = white_color;
williamr@2:     dijkstra_shortest_paths(g, s, predecessor, distance, weight, index_map,
williamr@2:                             compare, combine, inf, zero, vis,
williamr@2:                             make_iterator_property_map(&color[0], index_map,
williamr@2:                                                        c));
williamr@2:   }
williamr@2: 
williamr@2:   // Initialize distances and call breadth first search
williamr@2:   template <class VertexListGraph, class DijkstraVisitor,
williamr@2:             class PredecessorMap, class DistanceMap,
williamr@2:             class WeightMap, class IndexMap, class Compare, class Combine,
williamr@2:             class DistInf, class DistZero, class ColorMap>
williamr@2:   inline void
williamr@2:   dijkstra_shortest_paths
williamr@2:     (const VertexListGraph& g,
williamr@2:      typename graph_traits<VertexListGraph>::vertex_descriptor s,
williamr@2:      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
williamr@2:      IndexMap index_map,
williamr@2:      Compare compare, Combine combine, DistInf inf, DistZero zero,
williamr@2:      DijkstraVisitor vis, ColorMap color)
williamr@2:   {
williamr@2:     typedef typename property_traits<ColorMap>::value_type ColorValue;
williamr@2:     typedef color_traits<ColorValue> Color;
williamr@2:     typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end;
williamr@2:     for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
williamr@2:       vis.initialize_vertex(*ui, g);
williamr@2:       put(distance, *ui, inf);
williamr@2:       put(predecessor, *ui, *ui);
williamr@2:       put(color, *ui, Color::white());
williamr@2:     }
williamr@2:     put(distance, s, zero);
williamr@2: 
williamr@2:     dijkstra_shortest_paths_no_init(g, s, predecessor, distance, weight,
williamr@2:                             index_map, compare, combine, zero, vis, color);
williamr@2:   }
williamr@2: 
williamr@2:   namespace detail {
williamr@2: 
williamr@2:     // Handle defaults for PredecessorMap and
williamr@2:     // Distance Compare, Combine, Inf and Zero
williamr@2:     template <class VertexListGraph, class DistanceMap, class WeightMap,
williamr@2:               class IndexMap, class Params, class ColorMap>
williamr@2:     inline void
williamr@2:     dijkstra_dispatch2
williamr@2:       (const VertexListGraph& g,
williamr@2:        typename graph_traits<VertexListGraph>::vertex_descriptor s,
williamr@2:        DistanceMap distance, WeightMap weight, IndexMap index_map,
williamr@2:        const Params& params, ColorMap color)
williamr@2:     {
williamr@2:       // Default for predecessor map
williamr@2:       dummy_property_map p_map;
williamr@2: 
williamr@2:       typedef typename property_traits<DistanceMap>::value_type D;
williamr@2:       dijkstra_shortest_paths
williamr@2:         (g, s,
williamr@2:          choose_param(get_param(params, vertex_predecessor), p_map),
williamr@2:          distance, weight, index_map,
williamr@2:          choose_param(get_param(params, distance_compare_t()),
williamr@2:                       std::less<D>()),
williamr@2:          choose_param(get_param(params, distance_combine_t()),
williamr@2:                       closed_plus<D>()),
williamr@2:          choose_param(get_param(params, distance_inf_t()),
williamr@2:                       (std::numeric_limits<D>::max)()),
williamr@2:          choose_param(get_param(params, distance_zero_t()),
williamr@2:                       D()),
williamr@2:          choose_param(get_param(params, graph_visitor),
williamr@2:                       make_dijkstra_visitor(null_visitor())),
williamr@2:          color);
williamr@2:     }
williamr@2: 
williamr@2:     template <class VertexListGraph, class DistanceMap, class WeightMap,
williamr@2:               class IndexMap, class Params, class ColorMap>
williamr@2:     inline void
williamr@2:     dijkstra_dispatch1
williamr@2:       (const VertexListGraph& g,
williamr@2:        typename graph_traits<VertexListGraph>::vertex_descriptor s,
williamr@2:        DistanceMap distance, WeightMap weight, IndexMap index_map,
williamr@2:        const Params& params, ColorMap color)
williamr@2:     {
williamr@2:       // Default for distance map
williamr@2:       typedef typename property_traits<WeightMap>::value_type D;
williamr@2:       typename std::vector<D>::size_type
williamr@2:         n = is_default_param(distance) ? num_vertices(g) : 1;
williamr@2:       std::vector<D> distance_map(n);
williamr@2: 
williamr@2:       // Default for color map
williamr@2:       typename std::vector<default_color_type>::size_type
williamr@2:         m = is_default_param(color) ? num_vertices(g) : 1;
williamr@2:       std::vector<default_color_type> color_map(m);
williamr@2: 
williamr@2:       detail::dijkstra_dispatch2
williamr@2:         (g, s, choose_param(distance, make_iterator_property_map
williamr@2:                             (distance_map.begin(), index_map,
williamr@2:                              distance_map[0])),
williamr@2:          weight, index_map, params,
williamr@2:          choose_param(color, make_iterator_property_map
williamr@2:                       (color_map.begin(), index_map,
williamr@2:                        color_map[0])));
williamr@2:     }
williamr@2:   } // namespace detail
williamr@2: 
williamr@2:   // Named Parameter Variant
williamr@2:   template <class VertexListGraph, class Param, class Tag, class Rest>
williamr@2:   inline void
williamr@2:   dijkstra_shortest_paths
williamr@2:     (const VertexListGraph& g,
williamr@2:      typename graph_traits<VertexListGraph>::vertex_descriptor s,
williamr@2:      const bgl_named_params<Param,Tag,Rest>& params)
williamr@2:   {
williamr@2:     // Default for edge weight and vertex index map is to ask for them
williamr@2:     // from the graph.  Default for the visitor is null_visitor.
williamr@2:     detail::dijkstra_dispatch1
williamr@2:       (g, s,
williamr@2:        get_param(params, vertex_distance),
williamr@2:        choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
williamr@2:        choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
williamr@2:        params,
williamr@2:        get_param(params, vertex_color));
williamr@2:   }
williamr@2: 
williamr@2: } // namespace boost
williamr@2: 
williamr@2: #endif // BOOST_GRAPH_DIJKSTRA_HPP