COIN-OR::LEMON - Graph Library

Changeset 864:d3ea191c3412 in lemon-1.2 for lemon/hartmann_orlin_mmc.h


Ignore:
Timestamp:
03/13/10 22:01:38 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Rename min mean cycle classes and their members (#179)
with respect to the possible introduction of min ratio
cycle algorithms in the future.

The renamed classes:

The renamed members:

File:
1 moved

Legend:

Unmodified
Added
Removed
  • lemon/hartmann_orlin_mmc.h

    r863 r864  
    1717 */
    1818
    19 #ifndef LEMON_HARTMANN_ORLIN_H
    20 #define LEMON_HARTMANN_ORLIN_H
     19#ifndef LEMON_HARTMANN_ORLIN_MMC_H
     20#define LEMON_HARTMANN_ORLIN_MMC_H
    2121
    2222/// \ingroup min_mean_cycle
     
    3434namespace lemon {
    3535
    36   /// \brief Default traits class of HartmannOrlin algorithm.
     36  /// \brief Default traits class of HartmannOrlinMmc class.
    3737  ///
    38   /// Default traits class of HartmannOrlin algorithm.
     38  /// Default traits class of HartmannOrlinMmc class.
    3939  /// \tparam GR The type of the digraph.
    40   /// \tparam LEN The type of the length map.
     40  /// \tparam CM The type of the cost map.
    4141  /// It must conform to the \ref concepts::Rea_data "Rea_data" concept.
    4242#ifdef DOXYGEN
    43   template <typename GR, typename LEN>
     43  template <typename GR, typename CM>
    4444#else
    45   template <typename GR, typename LEN,
    46     bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
     45  template <typename GR, typename CM,
     46    bool integer = std::numeric_limits<typename CM::Value>::is_integer>
    4747#endif
    48   struct HartmannOrlinDefaultTraits
     48  struct HartmannOrlinMmcDefaultTraits
    4949  {
    5050    /// The type of the digraph
    5151    typedef GR Digraph;
    52     /// The type of the length map
    53     typedef LEN LengthMap;
    54     /// The type of the arc lengths
    55     typedef typename LengthMap::Value Value;
    56 
    57     /// \brief The large value type used for internal computations
    58     ///
    59     /// The large value type used for internal computations.
    60     /// It is \c long \c long if the \c Value type is integer,
     52    /// The type of the cost map
     53    typedef CM CostMap;
     54    /// The type of the arc costs
     55    typedef typename CostMap::Value Cost;
     56
     57    /// \brief The large cost type used for internal computations
     58    ///
     59    /// The large cost type used for internal computations.
     60    /// It is \c long \c long if the \c Cost type is integer,
    6161    /// otherwise it is \c double.
    62     /// \c Value must be convertible to \c LargeValue.
    63     typedef double LargeValue;
     62    /// \c Cost must be convertible to \c LargeCost.
     63    typedef double LargeCost;
    6464
    6565    /// The tolerance type used for internal computations
    66     typedef lemon::Tolerance<LargeValue> Tolerance;
     66    typedef lemon::Tolerance<LargeCost> Tolerance;
    6767
    6868    /// \brief The path type of the found cycles
     
    7474  };
    7575
    76   // Default traits class for integer value types
    77   template <typename GR, typename LEN>
    78   struct HartmannOrlinDefaultTraits<GR, LEN, true>
     76  // Default traits class for integer cost types
     77  template <typename GR, typename CM>
     78  struct HartmannOrlinMmcDefaultTraits<GR, CM, true>
    7979  {
    8080    typedef GR Digraph;
    81     typedef LEN LengthMap;
    82     typedef typename LengthMap::Value Value;
     81    typedef CM CostMap;
     82    typedef typename CostMap::Value Cost;
    8383#ifdef LEMON_HAVE_LONG_LONG
    84     typedef long long LargeValue;
     84    typedef long long LargeCost;
    8585#else
    86     typedef long LargeValue;
     86    typedef long LargeCost;
    8787#endif
    88     typedef lemon::Tolerance<LargeValue> Tolerance;
     88    typedef lemon::Tolerance<LargeCost> Tolerance;
    8989    typedef lemon::Path<Digraph> Path;
    9090  };
     
    9898  ///
    9999  /// This class implements the Hartmann-Orlin algorithm for finding
    100   /// a directed cycle of minimum mean length (cost) in a digraph
     100  /// a directed cycle of minimum mean cost in a digraph
    101101  /// \ref amo93networkflows, \ref dasdan98minmeancycle.
    102102  /// It is an improved version of \ref Karp "Karp"'s original algorithm,
     
    105105  ///
    106106  /// \tparam GR The type of the digraph the algorithm runs on.
    107   /// \tparam LEN The type of the length map. The default
     107  /// \tparam CM The type of the cost map. The default
    108108  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    109109  /// \tparam TR The traits class that defines various types used by the
    110   /// algorithm. By default, it is \ref HartmannOrlinDefaultTraits
    111   /// "HartmannOrlinDefaultTraits<GR, LEN>".
     110  /// algorithm. By default, it is \ref HartmannOrlinMmcDefaultTraits
     111  /// "HartmannOrlinMmcDefaultTraits<GR, CM>".
    112112  /// In most cases, this parameter should not be set directly,
    113113  /// consider to use the named template parameters instead.
    114114#ifdef DOXYGEN
    115   template <typename GR, typename LEN, typename TR>
     115  template <typename GR, typename CM, typename TR>
    116116#else
    117117  template < typename GR,
    118              typename LEN = typename GR::template ArcMap<int>,
    119              typename TR = HartmannOrlinDefaultTraits<GR, LEN> >
     118             typename CM = typename GR::template ArcMap<int>,
     119             typename TR = HartmannOrlinMmcDefaultTraits<GR, CM> >
    120120#endif
    121   class HartmannOrlin
     121  class HartmannOrlinMmc
    122122  {
    123123  public:
     
    125125    /// The type of the digraph
    126126    typedef typename TR::Digraph Digraph;
    127     /// The type of the length map
    128     typedef typename TR::LengthMap LengthMap;
    129     /// The type of the arc lengths
    130     typedef typename TR::Value Value;
    131 
    132     /// \brief The large value type
    133     ///
    134     /// The large value type used for internal computations.
    135     /// By default, it is \c long \c long if the \c Value type is integer,
     127    /// The type of the cost map
     128    typedef typename TR::CostMap CostMap;
     129    /// The type of the arc costs
     130    typedef typename TR::Cost Cost;
     131
     132    /// \brief The large cost type
     133    ///
     134    /// The large cost type used for internal computations.
     135    /// By default, it is \c long \c long if the \c Cost type is integer,
    136136    /// otherwise it is \c double.
    137     typedef typename TR::LargeValue LargeValue;
     137    typedef typename TR::LargeCost LargeCost;
    138138
    139139    /// The tolerance type
     
    143143    ///
    144144    /// The path type of the found cycles.
    145     /// Using the \ref HartmannOrlinDefaultTraits "default traits class",
     145    /// Using the \ref HartmannOrlinMmcDefaultTraits "default traits class",
    146146    /// it is \ref lemon::Path "Path<Digraph>".
    147147    typedef typename TR::Path Path;
    148148
    149     /// The \ref HartmannOrlinDefaultTraits "traits class" of the algorithm
     149    /// The \ref HartmannOrlinMmcDefaultTraits "traits class" of the algorithm
    150150    typedef TR Traits;
    151151
     
    157157    struct PathData
    158158    {
    159       LargeValue dist;
     159      LargeCost dist;
    160160      Arc pred;
    161       PathData(LargeValue d, Arc p = INVALID) :
     161      PathData(LargeCost d, Arc p = INVALID) :
    162162        dist(d), pred(p) {}
    163163    };
     
    170170    // The digraph the algorithm runs on
    171171    const Digraph &_gr;
    172     // The length of the arcs
    173     const LengthMap &_length;
     172    // The cost of the arcs
     173    const CostMap &_cost;
    174174
    175175    // Data for storing the strongly connected components
     
    182182    // Data for the found cycles
    183183    bool _curr_found, _best_found;
    184     LargeValue _curr_length, _best_length;
     184    LargeCost _curr_cost, _best_cost;
    185185    int _curr_size, _best_size;
    186186    Node _curr_node, _best_node;
     
    198198
    199199    // Infinite constant
    200     const LargeValue INF;
     200    const LargeCost INF;
    201201
    202202  public:
     
    206206
    207207    template <typename T>
    208     struct SetLargeValueTraits : public Traits {
    209       typedef T LargeValue;
     208    struct SetLargeCostTraits : public Traits {
     209      typedef T LargeCost;
    210210      typedef lemon::Tolerance<T> Tolerance;
    211211    };
    212212
    213213    /// \brief \ref named-templ-param "Named parameter" for setting
    214     /// \c LargeValue type.
    215     ///
    216     /// \ref named-templ-param "Named parameter" for setting \c LargeValue
     214    /// \c LargeCost type.
     215    ///
     216    /// \ref named-templ-param "Named parameter" for setting \c LargeCost
    217217    /// type. It is used for internal computations in the algorithm.
    218218    template <typename T>
    219     struct SetLargeValue
    220       : public HartmannOrlin<GR, LEN, SetLargeValueTraits<T> > {
    221       typedef HartmannOrlin<GR, LEN, SetLargeValueTraits<T> > Create;
     219    struct SetLargeCost
     220      : public HartmannOrlinMmc<GR, CM, SetLargeCostTraits<T> > {
     221      typedef HartmannOrlinMmc<GR, CM, SetLargeCostTraits<T> > Create;
    222222    };
    223223
     
    236236    template <typename T>
    237237    struct SetPath
    238       : public HartmannOrlin<GR, LEN, SetPathTraits<T> > {
    239       typedef HartmannOrlin<GR, LEN, SetPathTraits<T> > Create;
     238      : public HartmannOrlinMmc<GR, CM, SetPathTraits<T> > {
     239      typedef HartmannOrlinMmc<GR, CM, SetPathTraits<T> > Create;
    240240    };
    241241
     
    244244  protected:
    245245
    246     HartmannOrlin() {}
     246    HartmannOrlinMmc() {}
    247247
    248248  public:
     
    253253    ///
    254254    /// \param digraph The digraph the algorithm runs on.
    255     /// \param length The lengths (costs) of the arcs.
    256     HartmannOrlin( const Digraph &digraph,
    257                    const LengthMap &length ) :
    258       _gr(digraph), _length(length), _comp(digraph), _out_arcs(digraph),
    259       _best_found(false), _best_length(0), _best_size(1),
     255    /// \param cost The costs of the arcs.
     256    HartmannOrlinMmc( const Digraph &digraph,
     257                      const CostMap &cost ) :
     258      _gr(digraph), _cost(cost), _comp(digraph), _out_arcs(digraph),
     259      _best_found(false), _best_cost(0), _best_size(1),
    260260      _cycle_path(NULL), _local_path(false), _data(digraph),
    261       INF(std::numeric_limits<LargeValue>::has_infinity ?
    262           std::numeric_limits<LargeValue>::infinity() :
    263           std::numeric_limits<LargeValue>::max())
     261      INF(std::numeric_limits<LargeCost>::has_infinity ?
     262          std::numeric_limits<LargeCost>::infinity() :
     263          std::numeric_limits<LargeCost>::max())
    264264    {}
    265265
    266266    /// Destructor.
    267     ~HartmannOrlin() {
     267    ~HartmannOrlinMmc() {
    268268      if (_local_path) delete _cycle_path;
    269269    }
     
    275275    ///
    276276    /// If you don't call this function before calling \ref run() or
    277     /// \ref findMinMean(), it will allocate a local \ref Path "path"
     277    /// \ref findCycleMean(), it will allocate a local \ref Path "path"
    278278    /// structure. The destuctor deallocates this automatically
    279279    /// allocated object, of course.
     
    283283    ///
    284284    /// \return <tt>(*this)</tt>
    285     HartmannOrlin& cycle(Path &path) {
     285    HartmannOrlinMmc& cycle(Path &path) {
    286286      if (_local_path) {
    287287        delete _cycle_path;
     
    297297    ///
    298298    /// \return <tt>(*this)</tt>
    299     HartmannOrlin& tolerance(const Tolerance& tolerance) {
     299    HartmannOrlinMmc& tolerance(const Tolerance& tolerance) {
    300300      _tolerance = tolerance;
    301301      return *this;
     
    313313    /// The simplest way to execute the algorithm is to call the \ref run()
    314314    /// function.\n
    315     /// If you only need the minimum mean length, you may call
    316     /// \ref findMinMean().
     315    /// If you only need the minimum mean cost, you may call
     316    /// \ref findCycleMean().
    317317
    318318    /// @{
     
    322322    /// This function runs the algorithm.
    323323    /// It can be called more than once (e.g. if the underlying digraph
    324     /// and/or the arc lengths have been modified).
     324    /// and/or the arc costs have been modified).
    325325    ///
    326326    /// \return \c true if a directed cycle exists in the digraph.
     
    328328    /// \note <tt>mmc.run()</tt> is just a shortcut of the following code.
    329329    /// \code
    330     ///   return mmc.findMinMean() && mmc.findCycle();
     330    ///   return mmc.findCycleMean() && mmc.findCycle();
    331331    /// \endcode
    332332    bool run() {
    333       return findMinMean() && findCycle();
     333      return findCycleMean() && findCycle();
    334334    }
    335335
    336336    /// \brief Find the minimum cycle mean.
    337337    ///
    338     /// This function finds the minimum mean length of the directed
     338    /// This function finds the minimum mean cost of the directed
    339339    /// cycles in the digraph.
    340340    ///
    341341    /// \return \c true if a directed cycle exists in the digraph.
    342     bool findMinMean() {
     342    bool findCycleMean() {
    343343      // Initialization and find strongly connected components
    344344      init();
     
    352352        // Update the best cycle (global minimum mean cycle)
    353353        if ( _curr_found && (!_best_found ||
    354              _curr_length * _best_size < _best_length * _curr_size) ) {
     354             _curr_cost * _best_size < _best_cost * _curr_size) ) {
    355355          _best_found = true;
    356           _best_length = _curr_length;
     356          _best_cost = _curr_cost;
    357357          _best_size = _curr_size;
    358358          _best_node = _curr_node;
     
    365365    /// \brief Find a minimum mean directed cycle.
    366366    ///
    367     /// This function finds a directed cycle of minimum mean length
    368     /// in the digraph using the data computed by findMinMean().
     367    /// This function finds a directed cycle of minimum mean cost
     368    /// in the digraph using the data computed by findCycleMean().
    369369    ///
    370370    /// \return \c true if a directed cycle exists in the digraph.
    371371    ///
    372     /// \pre \ref findMinMean() must be called before using this function.
     372    /// \pre \ref findCycleMean() must be called before using this function.
    373373    bool findCycle() {
    374374      if (!_best_found) return false;
     
    383383      Arc e = _data[u][r].pred;
    384384      _cycle_path->addFront(e);
    385       _best_length = _length[e];
     385      _best_cost = _cost[e];
    386386      _best_size = 1;
    387387      Node v;
     
    389389        e = _data[v][--r].pred;
    390390        _cycle_path->addFront(e);
    391         _best_length += _length[e];
     391        _best_cost += _cost[e];
    392392        ++_best_size;
    393393      }
     
    404404    /// @{
    405405
    406     /// \brief Return the total length of the found cycle.
    407     ///
    408     /// This function returns the total length of the found cycle.
    409     ///
    410     /// \pre \ref run() or \ref findMinMean() must be called before
     406    /// \brief Return the total cost of the found cycle.
     407    ///
     408    /// This function returns the total cost of the found cycle.
     409    ///
     410    /// \pre \ref run() or \ref findCycleMean() must be called before
    411411    /// using this function.
    412     Value cycleLength() const {
    413       return static_cast<Value>(_best_length);
     412    Cost cycleCost() const {
     413      return static_cast<Cost>(_best_cost);
    414414    }
    415415
     
    418418    /// This function returns the number of arcs on the found cycle.
    419419    ///
    420     /// \pre \ref run() or \ref findMinMean() must be called before
     420    /// \pre \ref run() or \ref findCycleMean() must be called before
    421421    /// using this function.
    422     int cycleArcNum() const {
     422    int cycleSize() const {
    423423      return _best_size;
    424424    }
    425425
    426     /// \brief Return the mean length of the found cycle.
    427     ///
    428     /// This function returns the mean length of the found cycle.
     426    /// \brief Return the mean cost of the found cycle.
     427    ///
     428    /// This function returns the mean cost of the found cycle.
    429429    ///
    430430    /// \note <tt>alg.cycleMean()</tt> is just a shortcut of the
    431431    /// following code.
    432432    /// \code
    433     ///   return static_cast<double>(alg.cycleLength()) / alg.cycleArcNum();
     433    ///   return static_cast<double>(alg.cycleCost()) / alg.cycleSize();
    434434    /// \endcode
    435435    ///
    436     /// \pre \ref run() or \ref findMinMean() must be called before
     436    /// \pre \ref run() or \ref findCycleMean() must be called before
    437437    /// using this function.
    438438    double cycleMean() const {
    439       return static_cast<double>(_best_length) / _best_size;
     439      return static_cast<double>(_best_cost) / _best_size;
    440440    }
    441441
     
    463463      _cycle_path->clear();
    464464      _best_found = false;
    465       _best_length = 0;
     465      _best_cost = 0;
    466466      _best_size = 1;
    467467      _cycle_path->clear();
     
    512512
    513513    // Process all rounds of computing path data for the current component.
    514     // _data[v][k] is the length of a shortest directed walk from the root
     514    // _data[v][k] is the cost of a shortest directed walk from the root
    515515    // node to node v containing exactly k arcs.
    516516    void processRounds() {
     
    544544      Node u, v;
    545545      Arc e;
    546       LargeValue d;
     546      LargeCost d;
    547547      for (int i = 0; i < int(_process.size()); ++i) {
    548548        u = _process[i];
     
    550550          e = _out_arcs[u][j];
    551551          v = _gr.target(e);
    552           d = _data[u][k-1].dist + _length[e];
     552          d = _data[u][k-1].dist + _cost[e];
    553553          if (_tolerance.less(d, _data[v][k].dist)) {
    554554            if (_data[v][k].dist == INF) next.push_back(v);
     
    564564      Node u, v;
    565565      Arc e;
    566       LargeValue d;
     566      LargeCost d;
    567567      for (int i = 0; i < int(_nodes->size()); ++i) {
    568568        u = (*_nodes)[i];
     
    570570          e = _out_arcs[u][j];
    571571          v = _gr.target(e);
    572           d = _data[u][k-1].dist + _length[e];
     572          d = _data[u][k-1].dist + _cost[e];
    573573          if (_tolerance.less(d, _data[v][k].dist)) {
    574574            _data[v][k] = PathData(d, e);
     
    582582      typedef std::pair<int, int> Pair;
    583583      typename GR::template NodeMap<Pair> level(_gr, Pair(-1, 0));
    584       typename GR::template NodeMap<LargeValue> pi(_gr);
     584      typename GR::template NodeMap<LargeCost> pi(_gr);
    585585      int n = _nodes->size();
    586       LargeValue length;
     586      LargeCost cost;
    587587      int size;
    588588      Node u;
     
    596596          if (level[u].first == i && level[u].second > 0) {
    597597            // A cycle is found
    598             length = _data[u][level[u].second].dist - _data[u][j].dist;
     598            cost = _data[u][level[u].second].dist - _data[u][j].dist;
    599599            size = level[u].second - j;
    600             if (!_curr_found || length * _curr_size < _curr_length * size) {
    601               _curr_length = length;
     600            if (!_curr_found || cost * _curr_size < _curr_cost * size) {
     601              _curr_cost = cost;
    602602              _curr_size = size;
    603603              _curr_node = u;
     
    614614
    615615      // If at least one cycle is found, check the optimality condition
    616       LargeValue d;
     616      LargeCost d;
    617617      if (_curr_found && k < n) {
    618618        // Find node potentials
     
    622622          for (int j = 0; j <= k; ++j) {
    623623            if (_data[u][j].dist < INF) {
    624               d = _data[u][j].dist * _curr_size - j * _curr_length;
     624              d = _data[u][j].dist * _curr_size - j * _curr_cost;
    625625              if (_tolerance.less(d, pi[u])) pi[u] = d;
    626626            }
     
    631631        bool done = true;
    632632        for (ArcIt a(_gr); a != INVALID; ++a) {
    633           if (_tolerance.less(_length[a] * _curr_size - _curr_length,
     633          if (_tolerance.less(_cost[a] * _curr_size - _curr_cost,
    634634                              pi[_gr.target(a)] - pi[_gr.source(a)]) ) {
    635635            done = false;
     
    642642    }
    643643
    644   }; //class HartmannOrlin
     644  }; //class HartmannOrlinMmc
    645645
    646646  ///@}
     
    648648} //namespace lemon
    649649
    650 #endif //LEMON_HARTMANN_ORLIN_H
     650#endif //LEMON_HARTMANN_ORLIN_MMC_H
Note: See TracChangeset for help on using the changeset viewer.