[857] | 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
|
---|