Line data    Source code

       1             : //=======================================================================
       2             : // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
       3             : // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
       4             : //
       5             : // Distributed under the Boost Software License, Version 1.0. (See
       6             : // accompanying file LICENSE_1_0.txt or copy at
       7             : // http://www.boost.org/LICENSE_1_0.txt)
       8             : //=======================================================================
       9             : #ifndef BOOST_GRAPH_RELAX_HPP
      10             : #define BOOST_GRAPH_RELAX_HPP
      11             : 
      12             : #include <functional>
      13             : #include <boost/limits.hpp> // for numeric limits
      14             : #include <boost/graph/graph_traits.hpp>
      15             : #include <boost/property_map/property_map.hpp>
      16             : 
      17             : namespace boost {
      18             : 
      19             :     // The following version of the plus functor prevents
      20             :     // problems due to overflow at positive infinity.
      21             : 
      22             :     template <class T>
      23             :     struct closed_plus
      24             :     {
      25             :       const T inf;
      26             : 
      27             :       closed_plus() : inf((std::numeric_limits<T>::max)()) { }
      28             :       closed_plus(T inf) : inf(inf) { }
      29             : 
      30             :       T operator()(const T& a, const T& b) const {
      31             :         using namespace std;
      32             :        if (a == inf) return inf;
      33             :        if (b == inf) return inf;
      34             :        return a + b;
      35             :       }
      36             :     };
      37             :     
      38             :     template <class Graph, class WeightMap, 
      39             :             class PredecessorMap, class DistanceMap, 
      40             :             class BinaryFunction, class BinaryPredicate>
      41             :     bool relax(typename graph_traits<Graph>::edge_descriptor e, 
      42             :                const Graph& g, const WeightMap& w, 
      43             :                PredecessorMap& p, DistanceMap& d, 
      44             :                const BinaryFunction& combine, const BinaryPredicate& compare)
      45             :     {
      46             :       typedef typename graph_traits<Graph>::directed_category DirCat;
      47             :       bool is_undirected = is_same<DirCat, undirected_tag>::value;
      48             :       typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
      49             :       Vertex u = source(e, g), v = target(e, g);
      50             :       typedef typename property_traits<DistanceMap>::value_type D;
      51             :       typedef typename property_traits<WeightMap>::value_type W;
      52             :       const D d_u = get(d, u);
      53             :       const D d_v = get(d, v);
      54             :       const W& w_e = get(w, e);
      55             :       
      56             :       // The seemingly redundant comparisons after the distance puts are to
      57             :       // ensure that extra floating-point precision in x87 registers does not
      58             :       // lead to relax() returning true when the distance did not actually
      59             :       // change.
      60             :       if ( compare(combine(d_u, w_e), d_v) ) {
      61             :         put(d, v, combine(d_u, w_e));
      62             :         if (compare(get(d, v), d_v)) {
      63             :           put(p, v, u);
      64             :           return true;
      65             :         } else {
      66             :           return false;
      67             :         }
      68             :       } else if (is_undirected && compare(combine(d_v, w_e), d_u)) {
      69             :         put(d, u, combine(d_v, w_e));
      70             :         if (compare(get(d, u), d_u)) {
      71             :           put(p, u, v);
      72             :           return true;
      73             :         } else {
      74             :           return false;
      75             :         }
      76             :       } else
      77             :         return false;
      78             :     }
      79             : 
      80             :     template <class Graph, class WeightMap,
      81             :             class PredecessorMap, class DistanceMap,
      82             :             class BinaryFunction, class BinaryPredicate>
      83           0 :     bool relax_target(typename graph_traits<Graph>::edge_descriptor e,
      84             :                       const Graph& g, const WeightMap& w,
      85             :                       PredecessorMap& p, DistanceMap& d,
      86             :                       const BinaryFunction& combine, const BinaryPredicate& compare)
      87             :     {
      88             :       typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
      89             :       typedef typename property_traits<DistanceMap>::value_type D;
      90             :       typedef typename property_traits<WeightMap>::value_type W;
      91           0 :       const Vertex u = source(e, g);
      92           0 :       const Vertex v = target(e, g);
      93           0 :       const D d_u = get(d, u);
      94           0 :       const D d_v = get(d, v);
      95           0 :       const W& w_e = get(w, e);
      96             : 
      97             :       // The seemingly redundant comparisons after the distance puts are to
      98             :       // ensure that extra floating-point precision in x87 registers does not
      99             :       // lead to relax() returning true when the distance did not actually
     100             :       // change.
     101           0 :       if (compare(combine(d_u, w_e), d_v)) {
     102           0 :         put(d, v, combine(d_u, w_e));
     103           0 :         if (compare(get(d, v), d_v)) {
     104           0 :           put(p, v, u);
     105             :           return true;
     106             :         }
     107             :       }
     108             :       return false;
     109             :     }
     110             :     
     111             :     template <class Graph, class WeightMap, 
     112             :       class PredecessorMap, class DistanceMap>
     113             :     bool relax(typename graph_traits<Graph>::edge_descriptor e,
     114             :                const Graph& g, WeightMap w, PredecessorMap p, DistanceMap d)
     115             :     {
     116             :       typedef typename property_traits<DistanceMap>::value_type D;
     117             :       typedef closed_plus<D> Combine;
     118             :       typedef std::less<D> Compare;
     119             :       return relax(e, g, w, p, d, Combine(), Compare());
     120             :     }
     121             : 
     122             : } // namespace boost
     123             : 
     124             : #endif /* BOOST_GRAPH_RELAX_HPP */