Changeset 808:5795860737f5 in lemon

Timestamp:

08/06/09 20:28:28 (15 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

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).

File:

• lemon/min_mean_cycle.h (modified) (14 diffs)

lemon/min_mean_cycle.h

@@ -33 +33 @@
 namespace lemon {
 
+  /// \brief Default traits class of MinMeanCycle class.
+  ///
+  /// Default traits class of MinMeanCycle class.
+  /// \tparam GR The type of the digraph.
+  /// \tparam LEN The type of the length map.
+  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
+#ifdef DOXYGEN
+  template <typename GR, typename LEN>
+#else
+  template <typename GR, typename LEN,
+    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
+#endif
+  struct MinMeanCycleDefaultTraits
+  {
+    /// The type of the digraph
+    typedef GR Digraph;
+    /// The type of the length map
+    typedef LEN LengthMap;
+    /// The type of the arc lengths
+    typedef typename LengthMap::Value Value;
+
+    /// \brief The large value type used for internal computations
+    ///
+    /// The large value type used for internal computations.
+    /// It is \c long \c long if the \c Value type is integer,
+    /// otherwise it is \c double.
+    /// \c Value must be convertible to \c LargeValue.
+    typedef double LargeValue;
+
+    /// The tolerance type used for internal computations
+    typedef lemon::Tolerance<LargeValue> Tolerance;
+
+    /// \brief The path type of the found cycles
+    ///
+    /// The path type of the found cycles.
+    /// It must conform to the \ref lemon::concepts::Path "Path" concept
+    /// and it must have an \c addBack() function.
+    typedef lemon::Path<Digraph> Path;
+  };
+
+  // Default traits class for integer value types
+  template <typename GR, typename LEN>
+  struct MinMeanCycleDefaultTraits<GR, LEN, true>
+  {
+    typedef GR Digraph;
+    typedef LEN LengthMap;
+    typedef typename LengthMap::Value Value;
+#ifdef LEMON_HAVE_LONG_LONG
+    typedef long long LargeValue;
+#else
+    typedef long LargeValue;
+#endif
+    typedef lemon::Tolerance<LargeValue> Tolerance;
+    typedef lemon::Path<Digraph> Path;
+  };
+
+
   /// \addtogroup shortest_path
   /// @{
@@ -45 +102 @@
   /// \tparam LEN The type of the length map. The default
   /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
-  ///
-  /// \warning \c LEN::Value must be convertible to \c double.
 #ifdef DOXYGEN
-  template <typename GR, typename LEN>
+  template <typename GR, typename LEN, typename TR>
 #else
   template < typename GR,
-             typename LEN = typename GR::template ArcMap<int> >
+             typename LEN = typename GR::template ArcMap<int>,
+             typename TR = MinMeanCycleDefaultTraits<GR, LEN> >
 #endif
   class MinMeanCycle
@@ -57 +113 @@
   public:
   
-    /// The type of the digraph the algorithm runs on
-    typedef GR Digraph;
+    /// The type of the digraph
+    typedef typename TR::Digraph Digraph;
     /// The type of the length map
-    typedef LEN LengthMap;
+    typedef typename TR::LengthMap LengthMap;
     /// The type of the arc lengths
-    typedef typename LengthMap::Value Value;
-    /// The type of the paths
-    typedef lemon::Path<Digraph> Path;
+    typedef typename TR::Value Value;
+
+    /// \brief The large value type
+    ///
+    /// The large value type used for internal computations.
+    /// Using the \ref MinMeanCycleDefaultTraits "default traits class",
+    /// it is \c long \c long if the \c Value type is integer,
+    /// otherwise it is \c double.
+    typedef typename TR::LargeValue LargeValue;
+
+    /// The tolerance type
+    typedef typename TR::Tolerance Tolerance;
+
+    /// \brief The path type of the found cycles
+    ///
+    /// The path type of the found cycles.
+    /// Using the \ref MinMeanCycleDefaultTraits "default traits class",
+    /// it is \ref lemon::Path "Path<Digraph>".
+    typedef typename TR::Path Path;
+
+    /// The \ref MinMeanCycleDefaultTraits "traits class" of the algorithm
+    typedef TR Traits;
 
   private:
@@ -77 +152 @@
     // Data for the found cycles
     bool _curr_found, _best_found;
-    Value _curr_length, _best_length;
+    LargeValue _curr_length, _best_length;
     int _curr_size, _best_size;
     Node _curr_node, _best_node;
@@ -88 +163 @@
     typename Digraph::template NodeMap<bool> _reached;
     typename Digraph::template NodeMap<int> _level;
-    typename Digraph::template NodeMap<double> _dist;
+    typename Digraph::template NodeMap<LargeValue> _dist;
 
     // Data for storing the strongly connected components
@@ -100 +175 @@
     std::vector<Node> _queue;
     int _qfront, _qback;
+
+    Tolerance _tolerance;
+  
+  public:
+  
+    /// \name Named Template Parameters
+    /// @{
+
+    template <typename T>
+    struct SetLargeValueTraits : public Traits {
+      typedef T LargeValue;
+      typedef lemon::Tolerance<T> Tolerance;
+    };
+
+    /// \brief \ref named-templ-param "Named parameter" for setting
+    /// \c LargeValue type.
+    ///
+    /// \ref named-templ-param "Named parameter" for setting \c LargeValue
+    /// type. It is used for internal computations in the algorithm.
+    template <typename T>
+    struct SetLargeValue
+      : public MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > {
+      typedef MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > Create;
+    };
+
+    template <typename T>
+    struct SetPathTraits : public Traits {
+      typedef T Path;
+    };
+
+    /// \brief \ref named-templ-param "Named parameter" for setting
+    /// \c %Path type.
+    ///
+    /// \ref named-templ-param "Named parameter" for setting the \c %Path
+    /// type of the found cycles.
+    /// It must conform to the \ref lemon::concepts::Path "Path" concept
+    /// and it must have an \c addBack() function.
+    template <typename T>
+    struct SetPath
+      : public MinMeanCycle<GR, LEN, SetPathTraits<T> > {
+      typedef MinMeanCycle<GR, LEN, SetPathTraits<T> > Create;
+    };
     
-    Tolerance<double> _tol;
+    /// @}
 
   public:
@@ -236 +353 @@
     /// \pre \ref run() or \ref findMinMean() must be called before
     /// using this function.
-    Value cycleLength() const {
+    LargeValue cycleLength() const {
       return _best_length;
     }
@@ -285 +402 @@
     // Initialize
     void init() {
-      _tol.epsilon(1e-6);
       if (!_cycle_path) {
         _local_path = true;
@@ -334 +450 @@
       }
       for (int i = 0; i < int(_nodes->size()); ++i) {
-        _dist[(*_nodes)[i]] = std::numeric_limits<double>::max();
+        _dist[(*_nodes)[i]] = std::numeric_limits<LargeValue>::max();
       }
       Node u, v;
@@ -357 +473 @@
         _level[(*_nodes)[i]] = -1;
       }
-      Value clength;
+      LargeValue clength;
       int csize;
       Node u, v;
@@ -393 +509 @@
         _reached[(*_nodes)[i]] = false;
       }
-      double curr_mean = double(_curr_length) / _curr_size;
       _qfront = _qback = 0;
       _queue[0] = _curr_node;
@@ -407 +522 @@
           if (_policy[u] == e && !_reached[u]) {
             _reached[u] = true;
-            _dist[u] = _dist[v] + _length[e] - curr_mean;
+            _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
             _queue[++_qback] = u;
           }
@@ -424 +539 @@
             _reached[u] = true;
             _policy[u] = e;
-            _dist[u] = _dist[v] + _length[e] - curr_mean;
+            _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
             _queue[++_qback] = u;
           }
@@ -437 +552 @@
           e = _in_arcs[v][j];
           u = _gr.source(e);
-          double delta = _dist[v] + _length[e] - curr_mean;
-          if (_tol.less(delta, _dist[u])) {
+          LargeValue delta = _dist[v] + _length[e] * _curr_size - _curr_length;
+          if (_tolerance.less(delta, _dist[u])) {
             _dist[u] = delta;
             _policy[u] = e;