COIN-OR::LEMON - Graph Library

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

    r863 r864  
    1717 */
    1818
    19 #ifndef LEMON_KARP_H
    20 #define LEMON_KARP_H
     19#ifndef LEMON_KARP_MMC_H
     20#define LEMON_KARP_MMC_H
    2121
    2222/// \ingroup min_mean_cycle
     
    3434namespace lemon {
    3535
    36   /// \brief Default traits class of Karp algorithm.
     36  /// \brief Default traits class of KarpMmc class.
    3737  ///
    38   /// Default traits class of Karp algorithm.
     38  /// Default traits class of KarpMmc 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 KarpDefaultTraits
     48  struct KarpMmcDefaultTraits
    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 KarpDefaultTraits<GR, LEN, true>
     76  // Default traits class for integer cost types
     77  template <typename GR, typename CM>
     78  struct KarpMmcDefaultTraits<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 Karp's algorithm for finding a directed
    100   /// cycle of minimum mean length (cost) in a digraph
     100  /// cycle of minimum mean cost in a digraph
    101101  /// \ref amo93networkflows, \ref dasdan98minmeancycle.
    102102  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
    103103  ///
    104104  /// \tparam GR The type of the digraph the algorithm runs on.
    105   /// \tparam LEN The type of the length map. The default
     105  /// \tparam CM The type of the cost map. The default
    106106  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    107107  /// \tparam TR The traits class that defines various types used by the
    108   /// algorithm. By default, it is \ref KarpDefaultTraits
    109   /// "KarpDefaultTraits<GR, LEN>".
     108  /// algorithm. By default, it is \ref KarpMmcDefaultTraits
     109  /// "KarpMmcDefaultTraits<GR, CM>".
    110110  /// In most cases, this parameter should not be set directly,
    111111  /// consider to use the named template parameters instead.
    112112#ifdef DOXYGEN
    113   template <typename GR, typename LEN, typename TR>
     113  template <typename GR, typename CM, typename TR>
    114114#else
    115115  template < typename GR,
    116              typename LEN = typename GR::template ArcMap<int>,
    117              typename TR = KarpDefaultTraits<GR, LEN> >
     116             typename CM = typename GR::template ArcMap<int>,
     117             typename TR = KarpMmcDefaultTraits<GR, CM> >
    118118#endif
    119   class Karp
     119  class KarpMmc
    120120  {
    121121  public:
     
    123123    /// The type of the digraph
    124124    typedef typename TR::Digraph Digraph;
    125     /// The type of the length map
    126     typedef typename TR::LengthMap LengthMap;
    127     /// The type of the arc lengths
    128     typedef typename TR::Value Value;
    129 
    130     /// \brief The large value type
    131     ///
    132     /// The large value type used for internal computations.
    133     /// By default, it is \c long \c long if the \c Value type is integer,
     125    /// The type of the cost map
     126    typedef typename TR::CostMap CostMap;
     127    /// The type of the arc costs
     128    typedef typename TR::Cost Cost;
     129
     130    /// \brief The large cost type
     131    ///
     132    /// The large cost type used for internal computations.
     133    /// By default, it is \c long \c long if the \c Cost type is integer,
    134134    /// otherwise it is \c double.
    135     typedef typename TR::LargeValue LargeValue;
     135    typedef typename TR::LargeCost LargeCost;
    136136
    137137    /// The tolerance type
     
    141141    ///
    142142    /// The path type of the found cycles.
    143     /// Using the \ref KarpDefaultTraits "default traits class",
     143    /// Using the \ref KarpMmcDefaultTraits "default traits class",
    144144    /// it is \ref lemon::Path "Path<Digraph>".
    145145    typedef typename TR::Path Path;
    146146
    147     /// The \ref KarpDefaultTraits "traits class" of the algorithm
     147    /// The \ref KarpMmcDefaultTraits "traits class" of the algorithm
    148148    typedef TR Traits;
    149149
     
    155155    struct PathData
    156156    {
    157       LargeValue dist;
     157      LargeCost dist;
    158158      Arc pred;
    159       PathData(LargeValue d, Arc p = INVALID) :
     159      PathData(LargeCost d, Arc p = INVALID) :
    160160        dist(d), pred(p) {}
    161161    };
     
    168168    // The digraph the algorithm runs on
    169169    const Digraph &_gr;
    170     // The length of the arcs
    171     const LengthMap &_length;
     170    // The cost of the arcs
     171    const CostMap &_cost;
    172172
    173173    // Data for storing the strongly connected components
     
    179179
    180180    // Data for the found cycle
    181     LargeValue _cycle_length;
     181    LargeCost _cycle_cost;
    182182    int _cycle_size;
    183183    Node _cycle_node;
     
    194194   
    195195    // Infinite constant
    196     const LargeValue INF;
     196    const LargeCost INF;
    197197
    198198  public:
     
    202202
    203203    template <typename T>
    204     struct SetLargeValueTraits : public Traits {
    205       typedef T LargeValue;
     204    struct SetLargeCostTraits : public Traits {
     205      typedef T LargeCost;
    206206      typedef lemon::Tolerance<T> Tolerance;
    207207    };
    208208
    209209    /// \brief \ref named-templ-param "Named parameter" for setting
    210     /// \c LargeValue type.
    211     ///
    212     /// \ref named-templ-param "Named parameter" for setting \c LargeValue
     210    /// \c LargeCost type.
     211    ///
     212    /// \ref named-templ-param "Named parameter" for setting \c LargeCost
    213213    /// type. It is used for internal computations in the algorithm.
    214214    template <typename T>
    215     struct SetLargeValue
    216       : public Karp<GR, LEN, SetLargeValueTraits<T> > {
    217       typedef Karp<GR, LEN, SetLargeValueTraits<T> > Create;
     215    struct SetLargeCost
     216      : public KarpMmc<GR, CM, SetLargeCostTraits<T> > {
     217      typedef KarpMmc<GR, CM, SetLargeCostTraits<T> > Create;
    218218    };
    219219
     
    232232    template <typename T>
    233233    struct SetPath
    234       : public Karp<GR, LEN, SetPathTraits<T> > {
    235       typedef Karp<GR, LEN, SetPathTraits<T> > Create;
     234      : public KarpMmc<GR, CM, SetPathTraits<T> > {
     235      typedef KarpMmc<GR, CM, SetPathTraits<T> > Create;
    236236    };
    237237
     
    240240  protected:
    241241
    242     Karp() {}
     242    KarpMmc() {}
    243243
    244244  public:
     
    249249    ///
    250250    /// \param digraph The digraph the algorithm runs on.
    251     /// \param length The lengths (costs) of the arcs.
    252     Karp( const Digraph &digraph,
    253           const LengthMap &length ) :
    254       _gr(digraph), _length(length), _comp(digraph), _out_arcs(digraph),
    255       _cycle_length(0), _cycle_size(1), _cycle_node(INVALID),
     251    /// \param cost The costs of the arcs.
     252    KarpMmc( const Digraph &digraph,
     253             const CostMap &cost ) :
     254      _gr(digraph), _cost(cost), _comp(digraph), _out_arcs(digraph),
     255      _cycle_cost(0), _cycle_size(1), _cycle_node(INVALID),
    256256      _cycle_path(NULL), _local_path(false), _data(digraph),
    257       INF(std::numeric_limits<LargeValue>::has_infinity ?
    258           std::numeric_limits<LargeValue>::infinity() :
    259           std::numeric_limits<LargeValue>::max())
     257      INF(std::numeric_limits<LargeCost>::has_infinity ?
     258          std::numeric_limits<LargeCost>::infinity() :
     259          std::numeric_limits<LargeCost>::max())
    260260    {}
    261261
    262262    /// Destructor.
    263     ~Karp() {
     263    ~KarpMmc() {
    264264      if (_local_path) delete _cycle_path;
    265265    }
     
    271271    ///
    272272    /// If you don't call this function before calling \ref run() or
    273     /// \ref findMinMean(), it will allocate a local \ref Path "path"
     273    /// \ref findCycleMean(), it will allocate a local \ref Path "path"
    274274    /// structure. The destuctor deallocates this automatically
    275275    /// allocated object, of course.
     
    279279    ///
    280280    /// \return <tt>(*this)</tt>
    281     Karp& cycle(Path &path) {
     281    KarpMmc& cycle(Path &path) {
    282282      if (_local_path) {
    283283        delete _cycle_path;
     
    293293    ///
    294294    /// \return <tt>(*this)</tt>
    295     Karp& tolerance(const Tolerance& tolerance) {
     295    KarpMmc& tolerance(const Tolerance& tolerance) {
    296296      _tolerance = tolerance;
    297297      return *this;
     
    309309    /// The simplest way to execute the algorithm is to call the \ref run()
    310310    /// function.\n
    311     /// If you only need the minimum mean length, you may call
    312     /// \ref findMinMean().
     311    /// If you only need the minimum mean cost, you may call
     312    /// \ref findCycleMean().
    313313
    314314    /// @{
     
    318318    /// This function runs the algorithm.
    319319    /// It can be called more than once (e.g. if the underlying digraph
    320     /// and/or the arc lengths have been modified).
     320    /// and/or the arc costs have been modified).
    321321    ///
    322322    /// \return \c true if a directed cycle exists in the digraph.
     
    324324    /// \note <tt>mmc.run()</tt> is just a shortcut of the following code.
    325325    /// \code
    326     ///   return mmc.findMinMean() && mmc.findCycle();
     326    ///   return mmc.findCycleMean() && mmc.findCycle();
    327327    /// \endcode
    328328    bool run() {
    329       return findMinMean() && findCycle();
     329      return findCycleMean() && findCycle();
    330330    }
    331331
    332332    /// \brief Find the minimum cycle mean.
    333333    ///
    334     /// This function finds the minimum mean length of the directed
     334    /// This function finds the minimum mean cost of the directed
    335335    /// cycles in the digraph.
    336336    ///
    337337    /// \return \c true if a directed cycle exists in the digraph.
    338     bool findMinMean() {
     338    bool findCycleMean() {
    339339      // Initialization and find strongly connected components
    340340      init();
     
    352352    /// \brief Find a minimum mean directed cycle.
    353353    ///
    354     /// This function finds a directed cycle of minimum mean length
    355     /// in the digraph using the data computed by findMinMean().
     354    /// This function finds a directed cycle of minimum mean cost
     355    /// in the digraph using the data computed by findCycleMean().
    356356    ///
    357357    /// \return \c true if a directed cycle exists in the digraph.
    358358    ///
    359     /// \pre \ref findMinMean() must be called before using this function.
     359    /// \pre \ref findCycleMean() must be called before using this function.
    360360    bool findCycle() {
    361361      if (_cycle_node == INVALID) return false;
     
    370370      Arc e = _data[u][r].pred;
    371371      _cycle_path->addFront(e);
    372       _cycle_length = _length[e];
     372      _cycle_cost = _cost[e];
    373373      _cycle_size = 1;
    374374      Node v;
     
    376376        e = _data[v][--r].pred;
    377377        _cycle_path->addFront(e);
    378         _cycle_length += _length[e];
     378        _cycle_cost += _cost[e];
    379379        ++_cycle_size;
    380380      }
     
    391391    /// @{
    392392
    393     /// \brief Return the total length of the found cycle.
    394     ///
    395     /// This function returns the total length of the found cycle.
    396     ///
    397     /// \pre \ref run() or \ref findMinMean() must be called before
     393    /// \brief Return the total cost of the found cycle.
     394    ///
     395    /// This function returns the total cost of the found cycle.
     396    ///
     397    /// \pre \ref run() or \ref findCycleMean() must be called before
    398398    /// using this function.
    399     Value cycleLength() const {
    400       return static_cast<Value>(_cycle_length);
     399    Cost cycleCost() const {
     400      return static_cast<Cost>(_cycle_cost);
    401401    }
    402402
     
    405405    /// This function returns the number of arcs on the found cycle.
    406406    ///
    407     /// \pre \ref run() or \ref findMinMean() must be called before
     407    /// \pre \ref run() or \ref findCycleMean() must be called before
    408408    /// using this function.
    409     int cycleArcNum() const {
     409    int cycleSize() const {
    410410      return _cycle_size;
    411411    }
    412412
    413     /// \brief Return the mean length of the found cycle.
    414     ///
    415     /// This function returns the mean length of the found cycle.
     413    /// \brief Return the mean cost of the found cycle.
     414    ///
     415    /// This function returns the mean cost of the found cycle.
    416416    ///
    417417    /// \note <tt>alg.cycleMean()</tt> is just a shortcut of the
    418418    /// following code.
    419419    /// \code
    420     ///   return static_cast<double>(alg.cycleLength()) / alg.cycleArcNum();
     420    ///   return static_cast<double>(alg.cycleCost()) / alg.cycleSize();
    421421    /// \endcode
    422422    ///
    423     /// \pre \ref run() or \ref findMinMean() must be called before
     423    /// \pre \ref run() or \ref findCycleMean() must be called before
    424424    /// using this function.
    425425    double cycleMean() const {
    426       return static_cast<double>(_cycle_length) / _cycle_size;
     426      return static_cast<double>(_cycle_cost) / _cycle_size;
    427427    }
    428428
     
    449449      }
    450450      _cycle_path->clear();
    451       _cycle_length = 0;
     451      _cycle_cost = 0;
    452452      _cycle_size = 1;
    453453      _cycle_node = INVALID;
     
    498498
    499499    // Process all rounds of computing path data for the current component.
    500     // _data[v][k] is the length of a shortest directed walk from the root
     500    // _data[v][k] is the cost of a shortest directed walk from the root
    501501    // node to node v containing exactly k arcs.
    502502    void processRounds() {
     
    520520      Node u, v;
    521521      Arc e;
    522       LargeValue d;
     522      LargeCost d;
    523523      for (int i = 0; i < int(_process.size()); ++i) {
    524524        u = _process[i];
     
    526526          e = _out_arcs[u][j];
    527527          v = _gr.target(e);
    528           d = _data[u][k-1].dist + _length[e];
     528          d = _data[u][k-1].dist + _cost[e];
    529529          if (_tolerance.less(d, _data[v][k].dist)) {
    530530            if (_data[v][k].dist == INF) next.push_back(v);
     
    540540      Node u, v;
    541541      Arc e;
    542       LargeValue d;
     542      LargeCost d;
    543543      for (int i = 0; i < int(_nodes->size()); ++i) {
    544544        u = (*_nodes)[i];
     
    546546          e = _out_arcs[u][j];
    547547          v = _gr.target(e);
    548           d = _data[u][k-1].dist + _length[e];
     548          d = _data[u][k-1].dist + _cost[e];
    549549          if (_tolerance.less(d, _data[v][k].dist)) {
    550550            _data[v][k] = PathData(d, e);
     
    560560        Node u = (*_nodes)[i];
    561561        if (_data[u][n].dist == INF) continue;
    562         LargeValue length, max_length = 0;
     562        LargeCost cost, max_cost = 0;
    563563        int size, max_size = 1;
    564564        bool found_curr = false;
    565565        for (int k = 0; k < n; ++k) {
    566566          if (_data[u][k].dist == INF) continue;
    567           length = _data[u][n].dist - _data[u][k].dist;
     567          cost = _data[u][n].dist - _data[u][k].dist;
    568568          size = n - k;
    569           if (!found_curr || length * max_size > max_length * size) {
     569          if (!found_curr || cost * max_size > max_cost * size) {
    570570            found_curr = true;
    571             max_length = length;
     571            max_cost = cost;
    572572            max_size = size;
    573573          }
    574574        }
    575575        if ( found_curr && (_cycle_node == INVALID ||
    576              max_length * _cycle_size < _cycle_length * max_size) ) {
    577           _cycle_length = max_length;
     576             max_cost * _cycle_size < _cycle_cost * max_size) ) {
     577          _cycle_cost = max_cost;
    578578          _cycle_size = max_size;
    579579          _cycle_node = u;
     
    582582    }
    583583
    584   }; //class Karp
     584  }; //class KarpMmc
    585585
    586586  ///@}
     
    588588} //namespace lemon
    589589
    590 #endif //LEMON_KARP_H
     590#endif //LEMON_KARP_MMC_H
Note: See TracChangeset for help on using the changeset viewer.