epoc32/include/stdapis/boost/graph/relax.hpp
author William Roberts <williamr@symbian.org>
Tue, 16 Mar 2010 16:12:26 +0000
branchSymbian2
changeset 2 2fe1408b6811
permissions -rw-r--r--
Final list of Symbian^2 public API header files
williamr@2
     1
//=======================================================================
williamr@2
     2
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
williamr@2
     3
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
williamr@2
     4
//
williamr@2
     5
// Distributed under the Boost Software License, Version 1.0. (See
williamr@2
     6
// accompanying file LICENSE_1_0.txt or copy at
williamr@2
     7
// http://www.boost.org/LICENSE_1_0.txt)
williamr@2
     8
//=======================================================================
williamr@2
     9
#ifndef BOOST_GRAPH_RELAX_HPP
williamr@2
    10
#define BOOST_GRAPH_RELAX_HPP
williamr@2
    11
williamr@2
    12
#include <functional>
williamr@2
    13
#include <boost/limits.hpp> // for numeric limits
williamr@2
    14
#include <boost/graph/graph_traits.hpp>
williamr@2
    15
#include <boost/property_map.hpp>
williamr@2
    16
williamr@2
    17
namespace boost {
williamr@2
    18
williamr@2
    19
    // The following version of the plus functor prevents
williamr@2
    20
    // problems due to overflow at positive infinity.
williamr@2
    21
williamr@2
    22
    template <class T>
williamr@2
    23
    struct closed_plus
williamr@2
    24
    {
williamr@2
    25
      // std::abs just isn't portable :(
williamr@2
    26
      template <class X>
williamr@2
    27
      inline X my_abs(const X& x) const { return x < 0 ? -x : x; }
williamr@2
    28
williamr@2
    29
      T operator()(const T& a, const T& b) const {
williamr@2
    30
        using namespace std;
williamr@2
    31
        T inf = (numeric_limits<T>::max)();
williamr@2
    32
        if (b > 0 && my_abs(inf - a) < b)
williamr@2
    33
          return inf;
williamr@2
    34
        return a + b;
williamr@2
    35
      }
williamr@2
    36
    };
williamr@2
    37
    
williamr@2
    38
    template <class Graph, class WeightMap, 
williamr@2
    39
            class PredecessorMap, class DistanceMap, 
williamr@2
    40
            class BinaryFunction, class BinaryPredicate>
williamr@2
    41
    bool relax(typename graph_traits<Graph>::edge_descriptor e, 
williamr@2
    42
               const Graph& g, const WeightMap& w, 
williamr@2
    43
               PredecessorMap& p, DistanceMap& d, 
williamr@2
    44
               const BinaryFunction& combine, const BinaryPredicate& compare)
williamr@2
    45
    {
williamr@2
    46
      typedef typename graph_traits<Graph>::directed_category DirCat;
williamr@2
    47
      bool is_undirected = is_same<DirCat, undirected_tag>::value;
williamr@2
    48
      typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
williamr@2
    49
      Vertex u = source(e, g), v = target(e, g);
williamr@2
    50
      typedef typename property_traits<DistanceMap>::value_type D;
williamr@2
    51
      typedef typename property_traits<WeightMap>::value_type W;
williamr@2
    52
      D d_u = get(d, u), d_v = get(d, v);
williamr@2
    53
      W w_e = get(w, e);
williamr@2
    54
      
williamr@2
    55
      if ( compare(combine(d_u, w_e), d_v) ) {
williamr@2
    56
        put(d, v, combine(d_u, w_e));
williamr@2
    57
        put(p, v, u);
williamr@2
    58
        return true;
williamr@2
    59
      } else if (is_undirected && compare(combine(d_v, w_e), d_u)) {
williamr@2
    60
        put(d, u, combine(d_v, w_e));
williamr@2
    61
        put(p, u, v);
williamr@2
    62
        return true;
williamr@2
    63
      } else
williamr@2
    64
        return false;
williamr@2
    65
    }
williamr@2
    66
    
williamr@2
    67
    template <class Graph, class WeightMap, 
williamr@2
    68
      class PredecessorMap, class DistanceMap>
williamr@2
    69
    bool relax(typename graph_traits<Graph>::edge_descriptor e,
williamr@2
    70
               const Graph& g, WeightMap w, PredecessorMap p, DistanceMap d)
williamr@2
    71
    {
williamr@2
    72
      typedef typename property_traits<DistanceMap>::value_type D;
williamr@2
    73
      typedef closed_plus<D> Combine;
williamr@2
    74
      typedef std::less<D> Compare;
williamr@2
    75
      return relax(e, g, w, p, d, Combine(), Compare());
williamr@2
    76
    }
williamr@2
    77
williamr@2
    78
} // namespace boost
williamr@2
    79
williamr@2
    80
#endif /* BOOST_GRAPH_RELAX_HPP */