boost/graph/bellman_ford_shortest_paths.hpp

0001 //
0002 //=======================================================================
0003 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0004 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See
0007 // accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009 //=======================================================================
0010 //
0011
0012 /*
0013   This file implements the function
0014
0015   template <class EdgeListGraph, class Size, class P, class T, class R>
0016   bool bellman_ford_shortest_paths(EdgeListGraph& g, Size N,
0017      const bgl_named_params<P, T, R>& params)
0018
0019  */
0020
0021 #ifndef BOOST_GRAPH_BELLMAN_FORD_SHORTEST_PATHS_HPP
0022 #define BOOST_GRAPH_BELLMAN_FORD_SHORTEST_PATHS_HPP
0023
0024 #include <boost/config.hpp>
0025 #include <boost/graph/graph_traits.hpp>
0026 #include <boost/graph/graph_concepts.hpp>
0027 #include <boost/graph/properties.hpp>
0028 #include <boost/graph/relax.hpp>
0029 #include <boost/graph/visitors.hpp>
0030 #include <boost/graph/named_function_params.hpp>
0031 #include <boost/concept/assert.hpp>
0032
0033 namespace boost
0034 {
0035
0036 template < class Visitor, class Graph > struct BellmanFordVisitorConcept
0037 {
0038     void constraints()
0039     {
0040         BOOST_CONCEPT_ASSERT((CopyConstructibleConcept< Visitor >));
0041         vis.examine_edge(e, g);
0042         vis.edge_relaxed(e, g);
0043         vis.edge_not_relaxed(e, g);
0044         vis.edge_minimized(e, g);
0045         vis.edge_not_minimized(e, g);
0046     }
0047     Visitor vis;
0048     Graph g;
0049     typename graph_traits< Graph >::edge_descriptor e;
0050 };
0051
0052 template < class Visitors = null_visitor > class bellman_visitor
0053 {
0054 public:
0055     bellman_visitor() {}
0056     bellman_visitor(Visitors vis) : m_vis(vis) {}
0057
0058     template < class Edge, class Graph > void examine_edge(Edge u, Graph& g)
0059     {
0060         invoke_visitors(m_vis, u, g, on_examine_edge());
0061     }
0062     template < class Edge, class Graph > void edge_relaxed(Edge u, Graph& g)
0063     {
0064         invoke_visitors(m_vis, u, g, on_edge_relaxed());
0065     }
0066     template < class Edge, class Graph > void edge_not_relaxed(Edge u, Graph& g)
0067     {
0068         invoke_visitors(m_vis, u, g, on_edge_not_relaxed());
0069     }
0070     template < class Edge, class Graph > void edge_minimized(Edge u, Graph& g)
0071     {
0072         invoke_visitors(m_vis, u, g, on_edge_minimized());
0073     }
0074     template < class Edge, class Graph >
0075     void edge_not_minimized(Edge u, Graph& g)
0076     {
0077         invoke_visitors(m_vis, u, g, on_edge_not_minimized());
0078     }
0079
0080 protected:
0081     Visitors m_vis;
0082 };
0083 template < class Visitors >
0084 bellman_visitor< Visitors > make_bellman_visitor(Visitors vis)
0085 {
0086     return bellman_visitor< Visitors >(vis);
0087 }
0088 typedef bellman_visitor<> default_bellman_visitor;
0089
0090 template < class EdgeListGraph, class Size, class WeightMap,
0091     class PredecessorMap, class DistanceMap, class BinaryFunction,
0092     class BinaryPredicate, class BellmanFordVisitor >
0093 bool bellman_ford_shortest_paths(EdgeListGraph& g, Size N, WeightMap weight,
0094     PredecessorMap pred, DistanceMap distance, BinaryFunction combine,
0095     BinaryPredicate compare, BellmanFordVisitor v)
0096 {
0097     BOOST_CONCEPT_ASSERT((EdgeListGraphConcept< EdgeListGraph >));
0098     typedef graph_traits< EdgeListGraph > GTraits;
0099     typedef typename GTraits::edge_descriptor Edge;
0100     typedef typename GTraits::vertex_descriptor Vertex;
0101     BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept< DistanceMap, Vertex >));
0102     BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< WeightMap, Edge >));
0103
0104     typename GTraits::edge_iterator i, end;
0105
0106     for (Size k = 0; k < N; ++k)
0107     {
0108         bool at_least_one_edge_relaxed = false;
0109         for (boost::tie(i, end) = edges(g); i != end; ++i)
0110         {
0111             v.examine_edge(*i, g);
0112             if (relax(*i, g, weight, pred, distance, combine, compare))
0113             {
0114                 at_least_one_edge_relaxed = true;
0115                 v.edge_relaxed(*i, g);
0116             }
0117             else
0118                 v.edge_not_relaxed(*i, g);
0119         }
0120         if (!at_least_one_edge_relaxed)
0121             break;
0122     }
0123
0124     for (boost::tie(i, end) = edges(g); i != end; ++i)
0125         if (compare(combine(get(distance, source(*i, g)), get(weight, *i)),
0126                 get(distance, target(*i, g))))
0127         {
0128             v.edge_not_minimized(*i, g);
0129             return false;
0130         }
0131         else
0132             v.edge_minimized(*i, g);
0133
0134     return true;
0135 }
0136
0137 namespace detail
0138 {
0139
0140     template < typename VertexAndEdgeListGraph, typename Size,
0141         typename WeightMap, typename PredecessorMap, typename DistanceMap,
0142         typename P, typename T, typename R >
0143     bool bellman_dispatch2(VertexAndEdgeListGraph& g,
0144         typename graph_traits< VertexAndEdgeListGraph >::vertex_descriptor s,
0145         Size N, WeightMap weight, PredecessorMap pred, DistanceMap distance,
0146         const bgl_named_params< P, T, R >& params)
0147     {
0148         typedef typename property_traits< DistanceMap >::value_type D;
0149         bellman_visitor<> null_vis;
0150         typedef typename property_traits< WeightMap >::value_type weight_type;
0151         typename graph_traits< VertexAndEdgeListGraph >::vertex_iterator v,
0152             v_end;
0153         for (boost::tie(v, v_end) = vertices(g); v != v_end; ++v)
0154         {
0155             put(distance, *v, (std::numeric_limits< weight_type >::max)());
0156             put(pred, *v, *v);
0157         }
0158         put(distance, s, weight_type(0));
0159         return bellman_ford_shortest_paths(g, N, weight, pred, distance,
0160             choose_param(
0161                 get_param(params, distance_combine_t()), closed_plus< D >()),
0162             choose_param(
0163                 get_param(params, distance_compare_t()), std::less< D >()),
0164             choose_param(get_param(params, graph_visitor), null_vis));
0165     }
0166
0167     template < typename VertexAndEdgeListGraph, typename Size,
0168         typename WeightMap, typename PredecessorMap, typename DistanceMap,
0169         typename P, typename T, typename R >
0170     bool bellman_dispatch2(VertexAndEdgeListGraph& g, param_not_found, Size N,
0171         WeightMap weight, PredecessorMap pred, DistanceMap distance,
0172         const bgl_named_params< P, T, R >& params)
0173     {
0174         typedef typename property_traits< DistanceMap >::value_type D;
0175         bellman_visitor<> null_vis;
0176         return bellman_ford_shortest_paths(g, N, weight, pred, distance,
0177             choose_param(
0178                 get_param(params, distance_combine_t()), closed_plus< D >()),
0179             choose_param(
0180                 get_param(params, distance_compare_t()), std::less< D >()),
0181             choose_param(get_param(params, graph_visitor), null_vis));
0182     }
0183
0184     template < class EdgeListGraph, class Size, class WeightMap,
0185         class DistanceMap, class P, class T, class R >
0186     bool bellman_dispatch(EdgeListGraph& g, Size N, WeightMap weight,
0187         DistanceMap distance, const bgl_named_params< P, T, R >& params)
0188     {
0189         dummy_property_map dummy_pred;
0190         return detail::bellman_dispatch2(g, get_param(params, root_vertex_t()),
0191             N, weight,
0192             choose_param(get_param(params, vertex_predecessor), dummy_pred),
0193             distance, params);
0194     }
0195 } // namespace detail
0196
0197 template < class EdgeListGraph, class Size, class P, class T, class R >
0198 bool bellman_ford_shortest_paths(
0199     EdgeListGraph& g, Size N, const bgl_named_params< P, T, R >& params)
0200 {
0201     return detail::bellman_dispatch(g, N,
0202         choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
0203         choose_pmap(get_param(params, vertex_distance), g, vertex_distance),
0204         params);
0205 }
0206
0207 template < class EdgeListGraph, class Size >
0208 bool bellman_ford_shortest_paths(EdgeListGraph& g, Size N)
0209 {
0210     bgl_named_params< int, int > params(0);
0211     return bellman_ford_shortest_paths(g, N, params);
0212 }
0213
0214 template < class VertexAndEdgeListGraph, class P, class T, class R >
0215 bool bellman_ford_shortest_paths(
0216     VertexAndEdgeListGraph& g, const bgl_named_params< P, T, R >& params)
0217 {
0218     BOOST_CONCEPT_ASSERT((VertexListGraphConcept< VertexAndEdgeListGraph >));
0219     return detail::bellman_dispatch(g, num_vertices(g),
0220         choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
0221         choose_pmap(get_param(params, vertex_distance), g, vertex_distance),
0222         params);
0223 }
0224 } // namespace boost
0225
0226 #endif // BOOST_GRAPH_BELLMAN_FORD_SHORTEST_PATHS_HPP