boost/graph/relax.hpp

0001 //=======================================================================
0002 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0003 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //=======================================================================
0009 #ifndef BOOST_GRAPH_RELAX_HPP
0010 #define BOOST_GRAPH_RELAX_HPP
0011
0012 #include <functional>
0013 #include <boost/limits.hpp> // for numeric limits
0014 #include <boost/graph/graph_traits.hpp>
0015 #include <boost/property_map/property_map.hpp>
0016
0017 namespace boost
0018 {
0019
0020 // The following version of the plus functor prevents
0021 // problems due to overflow at positive infinity.
0022
0023 template < class T > struct closed_plus
0024 {
0025     const T inf;
0026
0027     closed_plus() : inf((std::numeric_limits< T >::max)()) {}
0028     closed_plus(T inf) : inf(inf) {}
0029
0030     T operator()(const T& a, const T& b) const
0031     {
0032         using namespace std;
0033         if (a == inf)
0034             return inf;
0035         if (b == inf)
0036             return inf;
0037         return a + b;
0038     }
0039 };
0040
0041 template < class Graph, class WeightMap, class PredecessorMap,
0042     class DistanceMap, class BinaryFunction, class BinaryPredicate >
0043 bool relax(typename graph_traits< Graph >::edge_descriptor e, const Graph& g,
0044     const WeightMap& w, PredecessorMap& p, DistanceMap& d,
0045     const BinaryFunction& combine, const BinaryPredicate& compare)
0046 {
0047     typedef typename graph_traits< Graph >::directed_category DirCat;
0048     bool is_undirected = is_same< DirCat, undirected_tag >::value;
0049     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0050     Vertex u = source(e, g), v = target(e, g);
0051     typedef typename property_traits< DistanceMap >::value_type D;
0052     typedef typename property_traits< WeightMap >::value_type W;
0053     const D d_u = get(d, u);
0054     const D d_v = get(d, v);
0055     const W& w_e = get(w, e);
0056
0057     // The seemingly redundant comparisons after the distance puts are to
0058     // ensure that extra floating-point precision in x87 registers does not
0059     // lead to relax() returning true when the distance did not actually
0060     // change.
0061     if (compare(combine(d_u, w_e), d_v))
0062     {
0063         put(d, v, combine(d_u, w_e));
0064         if (compare(get(d, v), d_v))
0065         {
0066             put(p, v, u);
0067             return true;
0068         }
0069         else
0070         {
0071             return false;
0072         }
0073     }
0074     else if (is_undirected && compare(combine(d_v, w_e), d_u))
0075     {
0076         put(d, u, combine(d_v, w_e));
0077         if (compare(get(d, u), d_u))
0078         {
0079             put(p, u, v);
0080             return true;
0081         }
0082         else
0083         {
0084             return false;
0085         }
0086     }
0087     else
0088         return false;
0089 }
0090
0091 template < class Graph, class WeightMap, class PredecessorMap,
0092     class DistanceMap, class BinaryFunction, class BinaryPredicate >
0093 bool relax_target(typename graph_traits< Graph >::edge_descriptor e,
0094     const Graph& g, const WeightMap& w, PredecessorMap& p, DistanceMap& d,
0095     const BinaryFunction& combine, const BinaryPredicate& compare)
0096 {
0097     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0098     typedef typename property_traits< DistanceMap >::value_type D;
0099     typedef typename property_traits< WeightMap >::value_type W;
0100     const Vertex u = source(e, g);
0101     const Vertex v = target(e, g);
0102     const D d_u = get(d, u);
0103     const D d_v = get(d, v);
0104     const W& w_e = get(w, e);
0105
0106     // The seemingly redundant comparisons after the distance puts are to
0107     // ensure that extra floating-point precision in x87 registers does not
0108     // lead to relax() returning true when the distance did not actually
0109     // change.
0110     if (compare(combine(d_u, w_e), d_v))
0111     {
0112         put(d, v, combine(d_u, w_e));
0113         if (compare(get(d, v), d_v))
0114         {
0115             put(p, v, u);
0116             return true;
0117         }
0118     }
0119     return false;
0120 }
0121
0122 template < class Graph, class WeightMap, class PredecessorMap,
0123     class DistanceMap >
0124 bool relax(typename graph_traits< Graph >::edge_descriptor e, const Graph& g,
0125     WeightMap w, PredecessorMap p, DistanceMap d)
0126 {
0127     typedef typename property_traits< DistanceMap >::value_type D;
0128     typedef closed_plus< D > Combine;
0129     typedef std::less< D > Compare;
0130     return relax(e, g, w, p, d, Combine(), Compare());
0131 }
0132
0133 } // namespace boost
0134
0135 #endif /* BOOST_GRAPH_RELAX_HPP */