COIN-OR::LEMON - Graph Library

Changeset 864:d3ea191c3412 in lemon-1.2 for lemon/howard_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/howard_mmc.h

    r863 r864  
    1717 */
    1818
    19 #ifndef LEMON_HOWARD_H
    20 #define LEMON_HOWARD_H
     19#ifndef LEMON_HOWARD_MMC_H
     20#define LEMON_HOWARD_MMC_H
    2121
    2222/// \ingroup min_mean_cycle
     
    3434namespace lemon {
    3535
    36   /// \brief Default traits class of Howard class.
     36  /// \brief Default traits class of HowardMmc class.
    3737  ///
    38   /// Default traits class of Howard class.
     38  /// Default traits class of HowardMmc 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::ReadMap "ReadMap" 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 HowardDefaultTraits
     48  struct HowardMmcDefaultTraits
    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 HowardDefaultTraits<GR, LEN, true>
     76  // Default traits class for integer cost types
     77  template <typename GR, typename CM>
     78  struct HowardMmcDefaultTraits<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 Howard's policy iteration 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  /// This class provides the most efficient algorithm for the
     
    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 HowardDefaultTraits
    111   /// "HowardDefaultTraits<GR, LEN>".
     110  /// algorithm. By default, it is \ref HowardMmcDefaultTraits
     111  /// "HowardMmcDefaultTraits<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 = HowardDefaultTraits<GR, LEN> >
     118             typename CM = typename GR::template ArcMap<int>,
     119             typename TR = HowardMmcDefaultTraits<GR, CM> >
    120120#endif
    121   class Howard
     121  class HowardMmc
    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 HowardDefaultTraits "default traits class",
     145    /// Using the \ref HowardMmcDefaultTraits "default traits class",
    146146    /// it is \ref lemon::Path "Path<Digraph>".
    147147    typedef typename TR::Path Path;
    148148
    149     /// The \ref HowardDefaultTraits "traits class" of the algorithm
     149    /// The \ref HowardMmcDefaultTraits "traits class" of the algorithm
    150150    typedef TR Traits;
    151151
     
    156156    // The digraph the algorithm runs on
    157157    const Digraph &_gr;
    158     // The length of the arcs
    159     const LengthMap &_length;
     158    // The cost of the arcs
     159    const CostMap &_cost;
    160160
    161161    // Data for the found cycles
    162162    bool _curr_found, _best_found;
    163     LargeValue _curr_length, _best_length;
     163    LargeCost _curr_cost, _best_cost;
    164164    int _curr_size, _best_size;
    165165    Node _curr_node, _best_node;
     
    172172    typename Digraph::template NodeMap<bool> _reached;
    173173    typename Digraph::template NodeMap<int> _level;
    174     typename Digraph::template NodeMap<LargeValue> _dist;
     174    typename Digraph::template NodeMap<LargeCost> _dist;
    175175
    176176    // Data for storing the strongly connected components
     
    188188 
    189189    // Infinite constant
    190     const LargeValue INF;
     190    const LargeCost INF;
    191191
    192192  public:
     
    196196
    197197    template <typename T>
    198     struct SetLargeValueTraits : public Traits {
    199       typedef T LargeValue;
     198    struct SetLargeCostTraits : public Traits {
     199      typedef T LargeCost;
    200200      typedef lemon::Tolerance<T> Tolerance;
    201201    };
    202202
    203203    /// \brief \ref named-templ-param "Named parameter" for setting
    204     /// \c LargeValue type.
    205     ///
    206     /// \ref named-templ-param "Named parameter" for setting \c LargeValue
     204    /// \c LargeCost type.
     205    ///
     206    /// \ref named-templ-param "Named parameter" for setting \c LargeCost
    207207    /// type. It is used for internal computations in the algorithm.
    208208    template <typename T>
    209     struct SetLargeValue
    210       : public Howard<GR, LEN, SetLargeValueTraits<T> > {
    211       typedef Howard<GR, LEN, SetLargeValueTraits<T> > Create;
     209    struct SetLargeCost
     210      : public HowardMmc<GR, CM, SetLargeCostTraits<T> > {
     211      typedef HowardMmc<GR, CM, SetLargeCostTraits<T> > Create;
    212212    };
    213213
     
    226226    template <typename T>
    227227    struct SetPath
    228       : public Howard<GR, LEN, SetPathTraits<T> > {
    229       typedef Howard<GR, LEN, SetPathTraits<T> > Create;
     228      : public HowardMmc<GR, CM, SetPathTraits<T> > {
     229      typedef HowardMmc<GR, CM, SetPathTraits<T> > Create;
    230230    };
    231231   
     
    234234  protected:
    235235
    236     Howard() {}
     236    HowardMmc() {}
    237237
    238238  public:
     
    243243    ///
    244244    /// \param digraph The digraph the algorithm runs on.
    245     /// \param length The lengths (costs) of the arcs.
    246     Howard( const Digraph &digraph,
    247             const LengthMap &length ) :
    248       _gr(digraph), _length(length), _best_found(false),
    249       _best_length(0), _best_size(1), _cycle_path(NULL), _local_path(false),
     245    /// \param cost The costs of the arcs.
     246    HowardMmc( const Digraph &digraph,
     247               const CostMap &cost ) :
     248      _gr(digraph), _cost(cost), _best_found(false),
     249      _best_cost(0), _best_size(1), _cycle_path(NULL), _local_path(false),
    250250      _policy(digraph), _reached(digraph), _level(digraph), _dist(digraph),
    251251      _comp(digraph), _in_arcs(digraph),
    252       INF(std::numeric_limits<LargeValue>::has_infinity ?
    253           std::numeric_limits<LargeValue>::infinity() :
    254           std::numeric_limits<LargeValue>::max())
     252      INF(std::numeric_limits<LargeCost>::has_infinity ?
     253          std::numeric_limits<LargeCost>::infinity() :
     254          std::numeric_limits<LargeCost>::max())
    255255    {}
    256256
    257257    /// Destructor.
    258     ~Howard() {
     258    ~HowardMmc() {
    259259      if (_local_path) delete _cycle_path;
    260260    }
     
    266266    ///
    267267    /// If you don't call this function before calling \ref run() or
    268     /// \ref findMinMean(), it will allocate a local \ref Path "path"
     268    /// \ref findCycleMean(), it will allocate a local \ref Path "path"
    269269    /// structure. The destuctor deallocates this automatically
    270270    /// allocated object, of course.
     
    274274    ///
    275275    /// \return <tt>(*this)</tt>
    276     Howard& cycle(Path &path) {
     276    HowardMmc& cycle(Path &path) {
    277277      if (_local_path) {
    278278        delete _cycle_path;
     
    288288    ///
    289289    /// \return <tt>(*this)</tt>
    290     Howard& tolerance(const Tolerance& tolerance) {
     290    HowardMmc& tolerance(const Tolerance& tolerance) {
    291291      _tolerance = tolerance;
    292292      return *this;
     
    304304    /// The simplest way to execute the algorithm is to call the \ref run()
    305305    /// function.\n
    306     /// If you only need the minimum mean length, you may call
    307     /// \ref findMinMean().
     306    /// If you only need the minimum mean cost, you may call
     307    /// \ref findCycleMean().
    308308
    309309    /// @{
     
    313313    /// This function runs the algorithm.
    314314    /// It can be called more than once (e.g. if the underlying digraph
    315     /// and/or the arc lengths have been modified).
     315    /// and/or the arc costs have been modified).
    316316    ///
    317317    /// \return \c true if a directed cycle exists in the digraph.
     
    319319    /// \note <tt>mmc.run()</tt> is just a shortcut of the following code.
    320320    /// \code
    321     ///   return mmc.findMinMean() && mmc.findCycle();
     321    ///   return mmc.findCycleMean() && mmc.findCycle();
    322322    /// \endcode
    323323    bool run() {
    324       return findMinMean() && findCycle();
     324      return findCycleMean() && findCycle();
    325325    }
    326326
    327327    /// \brief Find the minimum cycle mean.
    328328    ///
    329     /// This function finds the minimum mean length of the directed
     329    /// This function finds the minimum mean cost of the directed
    330330    /// cycles in the digraph.
    331331    ///
    332332    /// \return \c true if a directed cycle exists in the digraph.
    333     bool findMinMean() {
     333    bool findCycleMean() {
    334334      // Initialize and find strongly connected components
    335335      init();
     
    346346        // Update the best cycle (global minimum mean cycle)
    347347        if ( _curr_found && (!_best_found ||
    348              _curr_length * _best_size < _best_length * _curr_size) ) {
     348             _curr_cost * _best_size < _best_cost * _curr_size) ) {
    349349          _best_found = true;
    350           _best_length = _curr_length;
     350          _best_cost = _curr_cost;
    351351          _best_size = _curr_size;
    352352          _best_node = _curr_node;
     
    358358    /// \brief Find a minimum mean directed cycle.
    359359    ///
    360     /// This function finds a directed cycle of minimum mean length
    361     /// in the digraph using the data computed by findMinMean().
     360    /// This function finds a directed cycle of minimum mean cost
     361    /// in the digraph using the data computed by findCycleMean().
    362362    ///
    363363    /// \return \c true if a directed cycle exists in the digraph.
    364364    ///
    365     /// \pre \ref findMinMean() must be called before using this function.
     365    /// \pre \ref findCycleMean() must be called before using this function.
    366366    bool findCycle() {
    367367      if (!_best_found) return false;
     
    383383    /// @{
    384384
    385     /// \brief Return the total length of the found cycle.
    386     ///
    387     /// This function returns the total length of the found cycle.
    388     ///
    389     /// \pre \ref run() or \ref findMinMean() must be called before
     385    /// \brief Return the total cost of the found cycle.
     386    ///
     387    /// This function returns the total cost of the found cycle.
     388    ///
     389    /// \pre \ref run() or \ref findCycleMean() must be called before
    390390    /// using this function.
    391     Value cycleLength() const {
    392       return static_cast<Value>(_best_length);
     391    Cost cycleCost() const {
     392      return static_cast<Cost>(_best_cost);
    393393    }
    394394
     
    397397    /// This function returns the number of arcs on the found cycle.
    398398    ///
    399     /// \pre \ref run() or \ref findMinMean() must be called before
     399    /// \pre \ref run() or \ref findCycleMean() must be called before
    400400    /// using this function.
    401     int cycleArcNum() const {
     401    int cycleSize() const {
    402402      return _best_size;
    403403    }
    404404
    405     /// \brief Return the mean length of the found cycle.
    406     ///
    407     /// This function returns the mean length of the found cycle.
     405    /// \brief Return the mean cost of the found cycle.
     406    ///
     407    /// This function returns the mean cost of the found cycle.
    408408    ///
    409409    /// \note <tt>alg.cycleMean()</tt> is just a shortcut of the
    410410    /// following code.
    411411    /// \code
    412     ///   return static_cast<double>(alg.cycleLength()) / alg.cycleArcNum();
     412    ///   return static_cast<double>(alg.cycleCost()) / alg.cycleSize();
    413413    /// \endcode
    414414    ///
    415     /// \pre \ref run() or \ref findMinMean() must be called before
     415    /// \pre \ref run() or \ref findCycleMean() must be called before
    416416    /// using this function.
    417417    double cycleMean() const {
    418       return static_cast<double>(_best_length) / _best_size;
     418      return static_cast<double>(_best_cost) / _best_size;
    419419    }
    420420
     
    442442      _queue.resize(countNodes(_gr));
    443443      _best_found = false;
    444       _best_length = 0;
     444      _best_cost = 0;
    445445      _best_size = 1;
    446446      _cycle_path->clear();
     
    493493          e = _in_arcs[v][j];
    494494          u = _gr.source(e);
    495           if (_length[e] < _dist[u]) {
    496             _dist[u] = _length[e];
     495          if (_cost[e] < _dist[u]) {
     496            _dist[u] = _cost[e];
    497497            _policy[u] = e;
    498498          }
     
    507507        _level[(*_nodes)[i]] = -1;
    508508      }
    509       LargeValue clength;
     509      LargeCost ccost;
    510510      int csize;
    511511      Node u, v;
     
    519519        if (_level[u] == i) {
    520520          // A cycle is found
    521           clength = _length[_policy[u]];
     521          ccost = _cost[_policy[u]];
    522522          csize = 1;
    523523          for (v = u; (v = _gr.target(_policy[v])) != u; ) {
    524             clength += _length[_policy[v]];
     524            ccost += _cost[_policy[v]];
    525525            ++csize;
    526526          }
    527527          if ( !_curr_found ||
    528                (clength * _curr_size < _curr_length * csize) ) {
     528               (ccost * _curr_size < _curr_cost * csize) ) {
    529529            _curr_found = true;
    530             _curr_length = clength;
     530            _curr_cost = ccost;
    531531            _curr_size = csize;
    532532            _curr_node = u;
     
    556556          if (_policy[u] == e && !_reached[u]) {
    557557            _reached[u] = true;
    558             _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
     558            _dist[u] = _dist[v] + _cost[e] * _curr_size - _curr_cost;
    559559            _queue[++_qback] = u;
    560560          }
     
    573573            _reached[u] = true;
    574574            _policy[u] = e;
    575             _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
     575            _dist[u] = _dist[v] + _cost[e] * _curr_size - _curr_cost;
    576576            _queue[++_qback] = u;
    577577          }
     
    586586          e = _in_arcs[v][j];
    587587          u = _gr.source(e);
    588           LargeValue delta = _dist[v] + _length[e] * _curr_size - _curr_length;
     588          LargeCost delta = _dist[v] + _cost[e] * _curr_size - _curr_cost;
    589589          if (_tolerance.less(delta, _dist[u])) {
    590590            _dist[u] = delta;
     
    597597    }
    598598
    599   }; //class Howard
     599  }; //class HowardMmc
    600600
    601601  ///@}
     
    603603} //namespace lemon
    604604
    605 #endif //LEMON_HOWARD_H
     605#endif //LEMON_HOWARD_MMC_H
Note: See TracChangeset for help on using the changeset viewer.