source: NonGTP/Boost/boost/graph/relax.hpp @ 857

Revision 857, 3.7 KB checked in by igarcia, 19 years ago (diff)
RevLine 
[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// This file is part of the Boost Graph Library
7//
8// You should have received a copy of the License Agreement for the
9// Boost Graph Library along with the software; see the file LICENSE.
10// If not, contact Office of Research, University of Notre Dame, Notre
11// Dame, IN 46556.
12//
13// Permission to modify the code and to distribute modified code is
14// granted, provided the text of this NOTICE is retained, a notice that
15// the code was modified is included with the above COPYRIGHT NOTICE and
16// with the COPYRIGHT NOTICE in the LICENSE file, and that the LICENSE
17// file is distributed with the modified code.
18//
19// LICENSOR MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED.
20// By way of example, but not limitation, Licensor MAKES NO
21// REPRESENTATIONS OR WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY
22// PARTICULAR PURPOSE OR THAT THE USE OF THE LICENSED SOFTWARE COMPONENTS
23// OR DOCUMENTATION WILL NOT INFRINGE ANY PATENTS, COPYRIGHTS, TRADEMARKS
24// OR OTHER RIGHTS.
25//=======================================================================
26//
27
28#ifndef BOOST_GRAPH_RELAX_HPP
29#define BOOST_GRAPH_RELAX_HPP
30
31#include <functional>
32#include <boost/limits.hpp> // for numeric limits
33#include <boost/graph/graph_traits.hpp>
34#include <boost/property_map.hpp>
35
36namespace boost {
37
38    // The following version of the plus functor prevents
39    // problems due to overflow at positive infinity.
40
41    template <class T>
42    struct closed_plus
43    {
44      // std::abs just isn't portable :(
45      template <class X>
46      inline X my_abs(const X& x) const { return x < 0 ? -x : x; }
47
48      T operator()(const T& a, const T& b) const {
49        using namespace std;
50        T inf = (numeric_limits<T>::max)();
51        if (b > 0 && my_abs(inf - a) < b)
52          return inf;
53        return a + b;
54      }
55    };
56   
57    template <class Graph, class WeightMap,
58            class PredecessorMap, class DistanceMap,
59            class BinaryFunction, class BinaryPredicate>
60    bool relax(typename graph_traits<Graph>::edge_descriptor e,
61               const Graph& g, const WeightMap& w,
62               PredecessorMap& p, DistanceMap& d,
63               const BinaryFunction& combine, const BinaryPredicate& compare)
64    {
65      typedef typename graph_traits<Graph>::directed_category DirCat;
66      bool is_undirected = is_same<DirCat, undirected_tag>::value;
67      typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
68      Vertex u = source(e, g), v = target(e, g);
69      typedef typename property_traits<DistanceMap>::value_type D;
70      typedef typename property_traits<WeightMap>::value_type W;
71      D d_u = get(d, u), d_v = get(d, v);
72      W w_e = get(w, e);
73     
74      if ( compare(combine(d_u, w_e), d_v) ) {
75        put(d, v, combine(d_u, w_e));
76        put(p, v, u);
77        return true;
78      } else if (is_undirected && compare(combine(d_v, w_e), d_u)) {
79        put(d, u, combine(d_v, w_e));
80        put(p, u, v);
81        return true;
82      } else
83        return false;
84    }
85   
86    template <class Graph, class WeightMap,
87      class PredecessorMap, class DistanceMap>
88    bool relax(typename graph_traits<Graph>::edge_descriptor e,
89               const Graph& g, WeightMap w, PredecessorMap p, DistanceMap d)
90    {
91      typedef typename property_traits<DistanceMap>::value_type D;
92      typedef closed_plus<D> Combine;
93      typedef std::less<D> Compare;
94      return relax(e, g, w, p, d, Combine(), Compare());
95    }
96
97} // namespace boost
98
99#endif /* BOOST_GRAPH_RELAX_HPP */
Note: See TracBrowser for help on using the repository browser.