Traits class + named parameters for MinMeanCycle (#179)
authorPeter Kovacs <kpeter@inf.elte.hu>
Thu, 06 Aug 2009 20:28:28 +0200
changeset 7615795860737f5
parent 760 83ce7ce39f21
child 762 03887b5e0f6f
Traits class + named parameters for MinMeanCycle (#179)

- Add a Traits class defining LargeValue, Tolerance, Path types.
LargeValue is used for internal computations, it is 'long long'
if the length type is integer, otherwise it is 'double'.
- Add named template parameters for LargeValue and Path types.
- Improve numerical stability: remove divisions from the internal
computations. If the arc lengths are integers, then all used
values are integers (except for the cycleMean() query function,
of course).
lemon/min_mean_cycle.h
     1.1 --- a/lemon/min_mean_cycle.h	Thu Aug 06 20:12:43 2009 +0200
     1.2 +++ b/lemon/min_mean_cycle.h	Thu Aug 06 20:28:28 2009 +0200
     1.3 @@ -32,6 +32,63 @@
     1.4  
     1.5  namespace lemon {
     1.6  
     1.7 +  /// \brief Default traits class of MinMeanCycle class.
     1.8 +  ///
     1.9 +  /// Default traits class of MinMeanCycle class.
    1.10 +  /// \tparam GR The type of the digraph.
    1.11 +  /// \tparam LEN The type of the length map.
    1.12 +  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    1.13 +#ifdef DOXYGEN
    1.14 +  template <typename GR, typename LEN>
    1.15 +#else
    1.16 +  template <typename GR, typename LEN,
    1.17 +    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
    1.18 +#endif
    1.19 +  struct MinMeanCycleDefaultTraits
    1.20 +  {
    1.21 +    /// The type of the digraph
    1.22 +    typedef GR Digraph;
    1.23 +    /// The type of the length map
    1.24 +    typedef LEN LengthMap;
    1.25 +    /// The type of the arc lengths
    1.26 +    typedef typename LengthMap::Value Value;
    1.27 +
    1.28 +    /// \brief The large value type used for internal computations
    1.29 +    ///
    1.30 +    /// The large value type used for internal computations.
    1.31 +    /// It is \c long \c long if the \c Value type is integer,
    1.32 +    /// otherwise it is \c double.
    1.33 +    /// \c Value must be convertible to \c LargeValue.
    1.34 +    typedef double LargeValue;
    1.35 +
    1.36 +    /// The tolerance type used for internal computations
    1.37 +    typedef lemon::Tolerance<LargeValue> Tolerance;
    1.38 +
    1.39 +    /// \brief The path type of the found cycles
    1.40 +    ///
    1.41 +    /// The path type of the found cycles.
    1.42 +    /// It must conform to the \ref lemon::concepts::Path "Path" concept
    1.43 +    /// and it must have an \c addBack() function.
    1.44 +    typedef lemon::Path<Digraph> Path;
    1.45 +  };
    1.46 +
    1.47 +  // Default traits class for integer value types
    1.48 +  template <typename GR, typename LEN>
    1.49 +  struct MinMeanCycleDefaultTraits<GR, LEN, true>
    1.50 +  {
    1.51 +    typedef GR Digraph;
    1.52 +    typedef LEN LengthMap;
    1.53 +    typedef typename LengthMap::Value Value;
    1.54 +#ifdef LEMON_HAVE_LONG_LONG
    1.55 +    typedef long long LargeValue;
    1.56 +#else
    1.57 +    typedef long LargeValue;
    1.58 +#endif
    1.59 +    typedef lemon::Tolerance<LargeValue> Tolerance;
    1.60 +    typedef lemon::Path<Digraph> Path;
    1.61 +  };
    1.62 +
    1.63 +
    1.64    /// \addtogroup shortest_path
    1.65    /// @{
    1.66  
    1.67 @@ -44,26 +101,44 @@
    1.68    /// \tparam GR The type of the digraph the algorithm runs on.
    1.69    /// \tparam LEN The type of the length map. The default
    1.70    /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    1.71 -  ///
    1.72 -  /// \warning \c LEN::Value must be convertible to \c double.
    1.73  #ifdef DOXYGEN
    1.74 -  template <typename GR, typename LEN>
    1.75 +  template <typename GR, typename LEN, typename TR>
    1.76  #else
    1.77    template < typename GR,
    1.78 -             typename LEN = typename GR::template ArcMap<int> >
    1.79 +             typename LEN = typename GR::template ArcMap<int>,
    1.80 +             typename TR = MinMeanCycleDefaultTraits<GR, LEN> >
    1.81  #endif
    1.82    class MinMeanCycle
    1.83    {
    1.84    public:
    1.85    
    1.86 -    /// The type of the digraph the algorithm runs on
    1.87 -    typedef GR Digraph;
    1.88 +    /// The type of the digraph
    1.89 +    typedef typename TR::Digraph Digraph;
    1.90      /// The type of the length map
    1.91 -    typedef LEN LengthMap;
    1.92 +    typedef typename TR::LengthMap LengthMap;
    1.93      /// The type of the arc lengths
    1.94 -    typedef typename LengthMap::Value Value;
    1.95 -    /// The type of the paths
    1.96 -    typedef lemon::Path<Digraph> Path;
    1.97 +    typedef typename TR::Value Value;
    1.98 +
    1.99 +    /// \brief The large value type
   1.100 +    ///
   1.101 +    /// The large value type used for internal computations.
   1.102 +    /// Using the \ref MinMeanCycleDefaultTraits "default traits class",
   1.103 +    /// it is \c long \c long if the \c Value type is integer,
   1.104 +    /// otherwise it is \c double.
   1.105 +    typedef typename TR::LargeValue LargeValue;
   1.106 +
   1.107 +    /// The tolerance type
   1.108 +    typedef typename TR::Tolerance Tolerance;
   1.109 +
   1.110 +    /// \brief The path type of the found cycles
   1.111 +    ///
   1.112 +    /// The path type of the found cycles.
   1.113 +    /// Using the \ref MinMeanCycleDefaultTraits "default traits class",
   1.114 +    /// it is \ref lemon::Path "Path<Digraph>".
   1.115 +    typedef typename TR::Path Path;
   1.116 +
   1.117 +    /// The \ref MinMeanCycleDefaultTraits "traits class" of the algorithm
   1.118 +    typedef TR Traits;
   1.119  
   1.120    private:
   1.121  
   1.122 @@ -76,7 +151,7 @@
   1.123  
   1.124      // Data for the found cycles
   1.125      bool _curr_found, _best_found;
   1.126 -    Value _curr_length, _best_length;
   1.127 +    LargeValue _curr_length, _best_length;
   1.128      int _curr_size, _best_size;
   1.129      Node _curr_node, _best_node;
   1.130  
   1.131 @@ -87,7 +162,7 @@
   1.132      typename Digraph::template NodeMap<Arc> _policy;
   1.133      typename Digraph::template NodeMap<bool> _reached;
   1.134      typename Digraph::template NodeMap<int> _level;
   1.135 -    typename Digraph::template NodeMap<double> _dist;
   1.136 +    typename Digraph::template NodeMap<LargeValue> _dist;
   1.137  
   1.138      // Data for storing the strongly connected components
   1.139      int _comp_num;
   1.140 @@ -99,8 +174,50 @@
   1.141      // Queue used for BFS search
   1.142      std::vector<Node> _queue;
   1.143      int _qfront, _qback;
   1.144 +
   1.145 +    Tolerance _tolerance;
   1.146 +  
   1.147 +  public:
   1.148 +  
   1.149 +    /// \name Named Template Parameters
   1.150 +    /// @{
   1.151 +
   1.152 +    template <typename T>
   1.153 +    struct SetLargeValueTraits : public Traits {
   1.154 +      typedef T LargeValue;
   1.155 +      typedef lemon::Tolerance<T> Tolerance;
   1.156 +    };
   1.157 +
   1.158 +    /// \brief \ref named-templ-param "Named parameter" for setting
   1.159 +    /// \c LargeValue type.
   1.160 +    ///
   1.161 +    /// \ref named-templ-param "Named parameter" for setting \c LargeValue
   1.162 +    /// type. It is used for internal computations in the algorithm.
   1.163 +    template <typename T>
   1.164 +    struct SetLargeValue
   1.165 +      : public MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > {
   1.166 +      typedef MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > Create;
   1.167 +    };
   1.168 +
   1.169 +    template <typename T>
   1.170 +    struct SetPathTraits : public Traits {
   1.171 +      typedef T Path;
   1.172 +    };
   1.173 +
   1.174 +    /// \brief \ref named-templ-param "Named parameter" for setting
   1.175 +    /// \c %Path type.
   1.176 +    ///
   1.177 +    /// \ref named-templ-param "Named parameter" for setting the \c %Path
   1.178 +    /// type of the found cycles.
   1.179 +    /// It must conform to the \ref lemon::concepts::Path "Path" concept
   1.180 +    /// and it must have an \c addBack() function.
   1.181 +    template <typename T>
   1.182 +    struct SetPath
   1.183 +      : public MinMeanCycle<GR, LEN, SetPathTraits<T> > {
   1.184 +      typedef MinMeanCycle<GR, LEN, SetPathTraits<T> > Create;
   1.185 +    };
   1.186      
   1.187 -    Tolerance<double> _tol;
   1.188 +    /// @}
   1.189  
   1.190    public:
   1.191  
   1.192 @@ -235,7 +352,7 @@
   1.193      ///
   1.194      /// \pre \ref run() or \ref findMinMean() must be called before
   1.195      /// using this function.
   1.196 -    Value cycleLength() const {
   1.197 +    LargeValue cycleLength() const {
   1.198        return _best_length;
   1.199      }
   1.200  
   1.201 @@ -284,7 +401,6 @@
   1.202  
   1.203      // Initialize
   1.204      void init() {
   1.205 -      _tol.epsilon(1e-6);
   1.206        if (!_cycle_path) {
   1.207          _local_path = true;
   1.208          _cycle_path = new Path;
   1.209 @@ -333,7 +449,7 @@
   1.210          return false;
   1.211        }
   1.212        for (int i = 0; i < int(_nodes->size()); ++i) {
   1.213 -        _dist[(*_nodes)[i]] = std::numeric_limits<double>::max();
   1.214 +        _dist[(*_nodes)[i]] = std::numeric_limits<LargeValue>::max();
   1.215        }
   1.216        Node u, v;
   1.217        Arc e;
   1.218 @@ -356,7 +472,7 @@
   1.219        for (int i = 0; i < int(_nodes->size()); ++i) {
   1.220          _level[(*_nodes)[i]] = -1;
   1.221        }
   1.222 -      Value clength;
   1.223 +      LargeValue clength;
   1.224        int csize;
   1.225        Node u, v;
   1.226        _curr_found = false;
   1.227 @@ -392,7 +508,6 @@
   1.228        for (int i = 0; i < int(_nodes->size()); ++i) {
   1.229          _reached[(*_nodes)[i]] = false;
   1.230        }
   1.231 -      double curr_mean = double(_curr_length) / _curr_size;
   1.232        _qfront = _qback = 0;
   1.233        _queue[0] = _curr_node;
   1.234        _reached[_curr_node] = true;
   1.235 @@ -406,7 +521,7 @@
   1.236            u = _gr.source(e);
   1.237            if (_policy[u] == e && !_reached[u]) {
   1.238              _reached[u] = true;
   1.239 -            _dist[u] = _dist[v] + _length[e] - curr_mean;
   1.240 +            _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
   1.241              _queue[++_qback] = u;
   1.242            }
   1.243          }
   1.244 @@ -423,7 +538,7 @@
   1.245            if (!_reached[u]) {
   1.246              _reached[u] = true;
   1.247              _policy[u] = e;
   1.248 -            _dist[u] = _dist[v] + _length[e] - curr_mean;
   1.249 +            _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
   1.250              _queue[++_qback] = u;
   1.251            }
   1.252          }
   1.253 @@ -436,8 +551,8 @@
   1.254          for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
   1.255            e = _in_arcs[v][j];
   1.256            u = _gr.source(e);
   1.257 -          double delta = _dist[v] + _length[e] - curr_mean;
   1.258 -          if (_tol.less(delta, _dist[u])) {
   1.259 +          LargeValue delta = _dist[v] + _length[e] * _curr_size - _curr_length;
   1.260 +          if (_tolerance.less(delta, _dist[u])) {
   1.261              _dist[u] = delta;
   1.262              _policy[u] = e;
   1.263              improved = true;