COIN-OR::LEMON - Graph Library

Changeset 808:5795860737f5 in lemon


Ignore:
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:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/min_mean_cycle.h

    r807 r808  
    3333namespace lemon {
    3434
     35  /// \brief Default traits class of MinMeanCycle class.
     36  ///
     37  /// Default traits class of MinMeanCycle class.
     38  /// \tparam GR The type of the digraph.
     39  /// \tparam LEN The type of the length map.
     40  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
     41#ifdef DOXYGEN
     42  template <typename GR, typename LEN>
     43#else
     44  template <typename GR, typename LEN,
     45    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
     46#endif
     47  struct MinMeanCycleDefaultTraits
     48  {
     49    /// The type of the digraph
     50    typedef GR Digraph;
     51    /// The type of the length map
     52    typedef LEN LengthMap;
     53    /// The type of the arc lengths
     54    typedef typename LengthMap::Value Value;
     55
     56    /// \brief The large value type used for internal computations
     57    ///
     58    /// The large value type used for internal computations.
     59    /// It is \c long \c long if the \c Value type is integer,
     60    /// otherwise it is \c double.
     61    /// \c Value must be convertible to \c LargeValue.
     62    typedef double LargeValue;
     63
     64    /// The tolerance type used for internal computations
     65    typedef lemon::Tolerance<LargeValue> Tolerance;
     66
     67    /// \brief The path type of the found cycles
     68    ///
     69    /// The path type of the found cycles.
     70    /// It must conform to the \ref lemon::concepts::Path "Path" concept
     71    /// and it must have an \c addBack() function.
     72    typedef lemon::Path<Digraph> Path;
     73  };
     74
     75  // Default traits class for integer value types
     76  template <typename GR, typename LEN>
     77  struct MinMeanCycleDefaultTraits<GR, LEN, true>
     78  {
     79    typedef GR Digraph;
     80    typedef LEN LengthMap;
     81    typedef typename LengthMap::Value Value;
     82#ifdef LEMON_HAVE_LONG_LONG
     83    typedef long long LargeValue;
     84#else
     85    typedef long LargeValue;
     86#endif
     87    typedef lemon::Tolerance<LargeValue> Tolerance;
     88    typedef lemon::Path<Digraph> Path;
     89  };
     90
     91
    3592  /// \addtogroup shortest_path
    3693  /// @{
     
    45102  /// \tparam LEN The type of the length map. The default
    46103  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    47   ///
    48   /// \warning \c LEN::Value must be convertible to \c double.
    49104#ifdef DOXYGEN
    50   template <typename GR, typename LEN>
     105  template <typename GR, typename LEN, typename TR>
    51106#else
    52107  template < typename GR,
    53              typename LEN = typename GR::template ArcMap<int> >
     108             typename LEN = typename GR::template ArcMap<int>,
     109             typename TR = MinMeanCycleDefaultTraits<GR, LEN> >
    54110#endif
    55111  class MinMeanCycle
     
    57113  public:
    58114 
    59     /// The type of the digraph the algorithm runs on
    60     typedef GR Digraph;
     115    /// The type of the digraph
     116    typedef typename TR::Digraph Digraph;
    61117    /// The type of the length map
    62     typedef LEN LengthMap;
     118    typedef typename TR::LengthMap LengthMap;
    63119    /// The type of the arc lengths
    64     typedef typename LengthMap::Value Value;
    65     /// The type of the paths
    66     typedef lemon::Path<Digraph> Path;
     120    typedef typename TR::Value Value;
     121
     122    /// \brief The large value type
     123    ///
     124    /// The large value type used for internal computations.
     125    /// Using the \ref MinMeanCycleDefaultTraits "default traits class",
     126    /// it is \c long \c long if the \c Value type is integer,
     127    /// otherwise it is \c double.
     128    typedef typename TR::LargeValue LargeValue;
     129
     130    /// The tolerance type
     131    typedef typename TR::Tolerance Tolerance;
     132
     133    /// \brief The path type of the found cycles
     134    ///
     135    /// The path type of the found cycles.
     136    /// Using the \ref MinMeanCycleDefaultTraits "default traits class",
     137    /// it is \ref lemon::Path "Path<Digraph>".
     138    typedef typename TR::Path Path;
     139
     140    /// The \ref MinMeanCycleDefaultTraits "traits class" of the algorithm
     141    typedef TR Traits;
    67142
    68143  private:
     
    77152    // Data for the found cycles
    78153    bool _curr_found, _best_found;
    79     Value _curr_length, _best_length;
     154    LargeValue _curr_length, _best_length;
    80155    int _curr_size, _best_size;
    81156    Node _curr_node, _best_node;
     
    88163    typename Digraph::template NodeMap<bool> _reached;
    89164    typename Digraph::template NodeMap<int> _level;
    90     typename Digraph::template NodeMap<double> _dist;
     165    typename Digraph::template NodeMap<LargeValue> _dist;
    91166
    92167    // Data for storing the strongly connected components
     
    100175    std::vector<Node> _queue;
    101176    int _qfront, _qback;
     177
     178    Tolerance _tolerance;
     179 
     180  public:
     181 
     182    /// \name Named Template Parameters
     183    /// @{
     184
     185    template <typename T>
     186    struct SetLargeValueTraits : public Traits {
     187      typedef T LargeValue;
     188      typedef lemon::Tolerance<T> Tolerance;
     189    };
     190
     191    /// \brief \ref named-templ-param "Named parameter" for setting
     192    /// \c LargeValue type.
     193    ///
     194    /// \ref named-templ-param "Named parameter" for setting \c LargeValue
     195    /// type. It is used for internal computations in the algorithm.
     196    template <typename T>
     197    struct SetLargeValue
     198      : public MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > {
     199      typedef MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > Create;
     200    };
     201
     202    template <typename T>
     203    struct SetPathTraits : public Traits {
     204      typedef T Path;
     205    };
     206
     207    /// \brief \ref named-templ-param "Named parameter" for setting
     208    /// \c %Path type.
     209    ///
     210    /// \ref named-templ-param "Named parameter" for setting the \c %Path
     211    /// type of the found cycles.
     212    /// It must conform to the \ref lemon::concepts::Path "Path" concept
     213    /// and it must have an \c addBack() function.
     214    template <typename T>
     215    struct SetPath
     216      : public MinMeanCycle<GR, LEN, SetPathTraits<T> > {
     217      typedef MinMeanCycle<GR, LEN, SetPathTraits<T> > Create;
     218    };
    102219   
    103     Tolerance<double> _tol;
     220    /// @}
    104221
    105222  public:
     
    236353    /// \pre \ref run() or \ref findMinMean() must be called before
    237354    /// using this function.
    238     Value cycleLength() const {
     355    LargeValue cycleLength() const {
    239356      return _best_length;
    240357    }
     
    285402    // Initialize
    286403    void init() {
    287       _tol.epsilon(1e-6);
    288404      if (!_cycle_path) {
    289405        _local_path = true;
     
    334450      }
    335451      for (int i = 0; i < int(_nodes->size()); ++i) {
    336         _dist[(*_nodes)[i]] = std::numeric_limits<double>::max();
     452        _dist[(*_nodes)[i]] = std::numeric_limits<LargeValue>::max();
    337453      }
    338454      Node u, v;
     
    357473        _level[(*_nodes)[i]] = -1;
    358474      }
    359       Value clength;
     475      LargeValue clength;
    360476      int csize;
    361477      Node u, v;
     
    393509        _reached[(*_nodes)[i]] = false;
    394510      }
    395       double curr_mean = double(_curr_length) / _curr_size;
    396511      _qfront = _qback = 0;
    397512      _queue[0] = _curr_node;
     
    407522          if (_policy[u] == e && !_reached[u]) {
    408523            _reached[u] = true;
    409             _dist[u] = _dist[v] + _length[e] - curr_mean;
     524            _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
    410525            _queue[++_qback] = u;
    411526          }
     
    424539            _reached[u] = true;
    425540            _policy[u] = e;
    426             _dist[u] = _dist[v] + _length[e] - curr_mean;
     541            _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
    427542            _queue[++_qback] = u;
    428543          }
     
    437552          e = _in_arcs[v][j];
    438553          u = _gr.source(e);
    439           double delta = _dist[v] + _length[e] - curr_mean;
    440           if (_tol.less(delta, _dist[u])) {
     554          LargeValue delta = _dist[v] + _length[e] * _curr_size - _curr_length;
     555          if (_tolerance.less(delta, _dist[u])) {
    441556            _dist[u] = delta;
    442557            _policy[u] = e;
Note: See TracChangeset for help on using the changeset viewer.