boost/graph/bellman_ford_shortest_paths.hpp

   1 //
   2 //=======================================================================
   3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   5 //
   6 // Distributed under the Boost Software License, Version 1.0. (See
   7 // accompanying file LICENSE_1_0.txt or copy at
   8 // http://www.boost.org/LICENSE_1_0.txt)
   9 //=======================================================================
  10 //
  11
  12 /*
  13   This file implements the function
  14
  15   template <class EdgeListGraph, class Size, class P, class T, class R>
  16   bool bellman_ford_shortest_paths(EdgeListGraph& g, Size N,
  17      const bgl_named_params<P, T, R>& params)
  18
  19  */
  20
  21
  22 #ifndef BOOST_GRAPH_BELLMAN_FORD_SHORTEST_PATHS_HPP
  23 #define BOOST_GRAPH_BELLMAN_FORD_SHORTEST_PATHS_HPP
  24
  25 #include <boost/config.hpp>
  26 #include <boost/graph/graph_traits.hpp>
  27 #include <boost/graph/graph_concepts.hpp>
  28 #include <boost/graph/properties.hpp>
  29 #include <boost/graph/relax.hpp>
  30 #include <boost/graph/visitors.hpp>
  31 #include <boost/graph/named_function_params.hpp>
  32
  33 namespace boost {
  34
  35   template <class Visitor, class Graph>
  36   struct BellmanFordVisitorConcept {
  37     void constraints() {
  38       function_requires< CopyConstructibleConcept<Visitor> >();
  39       vis.examine_edge(e, g);
  40       vis.edge_relaxed(e, g);
  41       vis.edge_not_relaxed(e, g);
  42       vis.edge_minimized(e, g);
  43       vis.edge_not_minimized(e, g);
  44     }
  45     Visitor vis;
  46     Graph g;
  47     typename graph_traits<Graph>::edge_descriptor e;
  48   };
  49
  50   template <class Visitors = null_visitor>
  51   class bellman_visitor {
  52   public:
  53     bellman_visitor() { }
  54     bellman_visitor(Visitors vis) : m_vis(vis) { }
  55
  56     template <class Edge, class Graph>
  57     void examine_edge(Edge u, Graph& g) {
  58       invoke_visitors(m_vis, u, g, on_examine_edge());
  59     }
  60     template <class Edge, class Graph>
  61     void edge_relaxed(Edge u, Graph& g) {
  62       invoke_visitors(m_vis, u, g, on_edge_relaxed());
  63     }
  64     template <class Edge, class Graph>
  65     void edge_not_relaxed(Edge u, Graph& g) {
  66       invoke_visitors(m_vis, u, g, on_edge_not_relaxed());
  67     }
  68     template <class Edge, class Graph>
  69     void edge_minimized(Edge u, Graph& g) {
  70       invoke_visitors(m_vis, u, g, on_edge_minimized());
  71     }
  72     template <class Edge, class Graph>
  73     void edge_not_minimized(Edge u, Graph& g) {
  74       invoke_visitors(m_vis, u, g, on_edge_not_minimized());
  75     }
  76   protected:
  77     Visitors m_vis;
  78   };
  79   template <class Visitors>
  80   bellman_visitor<Visitors>
  81   make_bellman_visitor(Visitors vis) {
  82     return bellman_visitor<Visitors>(vis);
  83   }
  84   typedef bellman_visitor<> default_bellman_visitor;
  85
  86   template <class EdgeListGraph, class Size, class WeightMap,
  87             class PredecessorMap, class DistanceMap,
  88             class BinaryFunction, class BinaryPredicate,
  89             class BellmanFordVisitor>
  90   bool bellman_ford_shortest_paths(EdgeListGraph& g, Size N,
  91                          WeightMap weight,
  92                          PredecessorMap pred,
  93                          DistanceMap distance,
  94                          BinaryFunction combine,
  95                          BinaryPredicate compare,
  96                          BellmanFordVisitor v)
  97   {
  98     function_requires<EdgeListGraphConcept<EdgeListGraph> >();
  99     typedef graph_traits<EdgeListGraph> GTraits;
 100     typedef typename GTraits::edge_descriptor Edge;
 101     typedef typename GTraits::vertex_descriptor Vertex;
 102     function_requires<ReadWritePropertyMapConcept<DistanceMap, Vertex> >();
 103     function_requires<ReadablePropertyMapConcept<WeightMap, Edge> >();
 104     typedef typename property_traits<DistanceMap>::value_type D_value;
 105     typedef typename property_traits<WeightMap>::value_type W_value;
 106
 107     typename GTraits::edge_iterator i, end;
 108
 109     for (Size k = 0; k < N; ++k) {
 110       bool at_least_one_edge_relaxed = false;
 111       for (tie(i, end) = edges(g); i != end; ++i) {
 112         v.examine_edge(*i, g);
 113         if (relax(*i, g, weight, pred, distance, combine, compare)) {
 114           at_least_one_edge_relaxed = true;
 115           v.edge_relaxed(*i, g);
 116         } else
 117           v.edge_not_relaxed(*i, g);
 118       }
 119       if (!at_least_one_edge_relaxed)
 120         break;
 121     }
 122
 123     for (tie(i, end) = edges(g); i != end; ++i)
 124       if (compare(combine(get(distance, source(*i, g)), get(weight, *i)),
 125                   get(distance, target(*i,g))))
 126       {
 127         v.edge_not_minimized(*i, g);
 128         return false;
 129       } else
 130         v.edge_minimized(*i, g);
 131
 132     return true;
 133   }
 134
 135   namespace detail {
 136
 137     template<typename VertexAndEdgeListGraph, typename Size,
 138              typename WeightMap, typename PredecessorMap, typename DistanceMap,
 139              typename P, typename T, typename R>
 140     bool
 141     bellman_dispatch2
 142       (VertexAndEdgeListGraph& g,
 143        typename graph_traits<VertexAndEdgeListGraph>::vertex_descriptor s,
 144        Size N, WeightMap weight, PredecessorMap pred, DistanceMap distance,
 145        const bgl_named_params<P, T, R>& params)
 146     {
 147       typedef typename property_traits<DistanceMap>::value_type D;
 148       bellman_visitor<> null_vis;
 149       typedef typename property_traits<WeightMap>::value_type weight_type;
 150       typename graph_traits<VertexAndEdgeListGraph>::vertex_iterator v, v_end;
 151       for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
 152         put(distance, *v, (std::numeric_limits<weight_type>::max)());
 153         put(pred, *v, *v);
 154       }
 155       put(distance, s, weight_type(0));
 156       return bellman_ford_shortest_paths
 157                (g, N, weight, pred, distance,
 158                 choose_param(get_param(params, distance_combine_t()),
 159                              closed_plus<D>()),
 160                 choose_param(get_param(params, distance_compare_t()),
 161                              std::less<D>()),
 162                 choose_param(get_param(params, graph_visitor),
 163                              null_vis)
 164                 );
 165     }
 166
 167     template<typename VertexAndEdgeListGraph, typename Size,
 168              typename WeightMap, typename PredecessorMap, typename DistanceMap,
 169              typename P, typename T, typename R>
 170     bool
 171     bellman_dispatch2
 172       (VertexAndEdgeListGraph& g,
 173        detail::error_property_not_found,
 174        Size N, WeightMap weight, PredecessorMap pred, DistanceMap distance,
 175        const bgl_named_params<P, T, R>& params)
 176     {
 177       typedef typename property_traits<DistanceMap>::value_type D;
 178       bellman_visitor<> null_vis;
 179       return bellman_ford_shortest_paths
 180                (g, N, weight, pred, distance,
 181                 choose_param(get_param(params, distance_combine_t()),
 182                              closed_plus<D>()),
 183                 choose_param(get_param(params, distance_compare_t()),
 184                              std::less<D>()),
 185                 choose_param(get_param(params, graph_visitor),
 186                              null_vis)
 187                 );
 188     }
 189
 190     template <class EdgeListGraph, class Size, class WeightMap,
 191               class DistanceMap, class P, class T, class R>
 192     bool bellman_dispatch(EdgeListGraph& g, Size N,
 193                           WeightMap weight, DistanceMap distance,
 194                           const bgl_named_params<P, T, R>& params)
 195     {
 196       dummy_property_map dummy_pred;
 197       return
 198         detail::bellman_dispatch2
 199           (g,
 200            get_param(params, root_vertex_t()),
 201            N, weight,
 202            choose_param(get_param(params, vertex_predecessor), dummy_pred),
 203            distance,
 204            params);
 205     }
 206   } // namespace detail
 207
 208   template <class EdgeListGraph, class Size, class P, class T, class R>
 209   bool bellman_ford_shortest_paths
 210     (EdgeListGraph& g, Size N,
 211      const bgl_named_params<P, T, R>& params)
 212   {
 213     return detail::bellman_dispatch
 214       (g, N,
 215        choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
 216        choose_pmap(get_param(params, vertex_distance), g, vertex_distance),
 217        params);
 218   }
 219
 220   template <class EdgeListGraph, class Size>
 221   bool bellman_ford_shortest_paths(EdgeListGraph& g, Size N)
 222   {
 223     bgl_named_params<int,int> params(0);
 224     return bellman_ford_shortest_paths(g, N, params);
 225   }
 226
 227   template <class VertexAndEdgeListGraph, class P, class T, class R>
 228   bool bellman_ford_shortest_paths
 229     (VertexAndEdgeListGraph& g,
 230      const bgl_named_params<P, T, R>& params)
 231   {
 232     function_requires<VertexListGraphConcept<VertexAndEdgeListGraph> >();
 233     return detail::bellman_dispatch
 234       (g, num_vertices(g),
 235        choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
 236        choose_pmap(get_param(params, vertex_distance), g, vertex_distance),
 237        params);
 238   }
 239 } // namespace boost
 240
 241 #endif // BOOST_GRAPH_BELLMAN_FORD_SHORTEST_PATHS_HPP