LEMON/LEMON-main Changeset - r864:d3ea191c3412

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r864:d3ea191c3412

« 863:a93f1a

865:d48d79 »

r864:d3ea191c3412

Sat, 13 Mar 2010 22:01:38

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

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: - Karp --> KarpMmc - HartmannOrlin --> HartmannOrlinMmc - Howard --> HowardMmc The renamed members: - cycleLength() --> cycleCost() - cycleArcNum() --> cycleSize() - findMinMean() --> findCycleMean() - Value --> Cost - LargeValue --> LargeCost - SetLargeValue --> SetLargeCost

3 3 3

default

9 files changed with 386 insertions and 386 deletions:

lemon/Makefile.am

lemon/cycle_canceling.h

lemon/hartmann_orlin_mmc.h

115

lemon/howard_mmc.h

109

lemon/karp_mmc.h

111

test/min_mean_cycle_test.cc

↑ Collapse diff ↑

lemon/Makefile.am

Show inline comments

@@ -91,6 +91,6 @@
 			lemon/grid_graph.h \
 			lemon/hartmann_orlin.h \
 			lemon/howard.h \
 			lemon/hartmann_orlin_mmc.h \
 			lemon/howard_mmc.h \
 			lemon/hypercube_graph.h \
-			lemon/karp.h \
+			lemon/karp_mmc.h \
 			lemon/kruskal.h \

lemon/cycle_canceling.h

Show inline comments

@@ -36,3 +36,3 @@
 		#include <lemon/bellman_ford.h>
-		#include <lemon/howard.h>
+		#include <lemon/howard_mmc.h>
@@ -926,3 +926,3 @@
 		      typedef typename SPath::ArcIt SPathArcIt;
-		      typedef typename Howard<StaticDigraph, CostArcMap>
+		      typedef typename HowardMmc<StaticDigraph, CostArcMap>
 		        ::template SetPath<SPath>::Create MMC;
@@ -933,3 +933,3 @@
 		      buildResidualNetwork();
-		      while (mmc.findMinMean() && mmc.cycleLength() < 0) {
+		      while (mmc.findCycleMean() && mmc.cycleCost() < 0) {
 		        // Find the cycle
@@ -1134,3 +1134,3 @@
 		        } else {
-		          typedef Howard<StaticDigraph, CostArcMap> MMC;
+		          typedef HowardMmc<StaticDigraph, CostArcMap> MMC;
 		          typedef typename BellmanFord<StaticDigraph, CostArcMap>
@@ -1141,6 +1141,6 @@
 		          MMC mmc(_sgr, _cost_map);
-		          mmc.findMinMean();
+		          mmc.findCycleMean();
 		          epsilon = -mmc.cycleMean();
 		          Cost cycle_cost = mmc.cycleLength();
 		          int cycle_size = mmc.cycleArcNum();
 		          Cost cycle_cost = mmc.cycleCost();
 		          int cycle_size = mmc.cycleSize();

lemon/hartmann_orlin_mmc.h

Show inline comments

@@ -18,4 +18,4 @@
 		#ifndef LEMON_HARTMANN_ORLIN_H
 		#define LEMON_HARTMANN_ORLIN_H
 		#ifndef LEMON_HARTMANN_ORLIN_MMC_H
 		#define LEMON_HARTMANN_ORLIN_MMC_H
@@ -35,15 +35,15 @@
-		  /// \brief Default traits class of HartmannOrlin algorithm.
+		  /// \brief Default traits class of HartmannOrlinMmc class.
 		  ///
-		  /// Default traits class of HartmannOrlin algorithm.
+		  /// Default traits class of HartmannOrlinMmc class.
 		  /// \tparam GR The type of the digraph.
-		  /// \tparam LEN The type of the length map.
+		  /// \tparam CM The type of the cost map.
 		  /// It must conform to the \ref concepts::Rea_data "Rea_data" concept.
 		#ifdef DOXYGEN
-		  template <typename GR, typename LEN>
+		  template <typename GR, typename CM>
 		#else
 		  template <typename GR, typename LEN,
 		    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
 		  template <typename GR, typename CM,
 		    bool integer = std::numeric_limits<typename CM::Value>::is_integer>
 		#endif
-		  struct HartmannOrlinDefaultTraits
+		  struct HartmannOrlinMmcDefaultTraits
+		  {
@@ -51,17 +51,17 @@
 		    typedef GR Digraph;
 		    /// The type of the length map
 		    typedef LEN LengthMap;
 		    /// The type of the arc lengths
 		    typedef typename LengthMap::Value Value;
 		    /// The type of the cost map
 		    typedef CM CostMap;
 		    /// The type of the arc costs
 		    typedef typename CostMap::Value Cost;
-		    /// \brief The large value type used for internal computations
+		    /// \brief The large cost 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,
 		    /// The large cost type used for internal computations.
 		    /// It is \c long \c long if the \c Cost type is integer,
 		    /// otherwise it is \c double.
 		    /// \c Value must be convertible to \c LargeValue.
 		    typedef double LargeValue;
 		    /// \c Cost must be convertible to \c LargeCost.
 		    typedef double LargeCost;
 		    /// The tolerance type used for internal computations
-		    typedef lemon::Tolerance<LargeValue> Tolerance;
+		    typedef lemon::Tolerance<LargeCost> Tolerance;
@@ -75,15 +75,15 @@
 		  // Default traits class for integer value types
 		  template <typename GR, typename LEN>
-		  struct HartmannOrlinDefaultTraits<GR, LEN, true>
+		  // Default traits class for integer cost types
 		  template <typename GR, typename CM>
 		  struct HartmannOrlinMmcDefaultTraits<GR, CM, true>
+		  {
 		    typedef GR Digraph;
 		    typedef LEN LengthMap;
 		    typedef typename LengthMap::Value Value;
 		    typedef CM CostMap;
 		    typedef typename CostMap::Value Cost;
 		#ifdef LEMON_HAVE_LONG_LONG
-		    typedef long long LargeValue;
+		    typedef long long LargeCost;
 		#else
-		    typedef long LargeValue;
+		    typedef long LargeCost;
 		#endif
-		    typedef lemon::Tolerance<LargeValue> Tolerance;
+		    typedef lemon::Tolerance<LargeCost> Tolerance;
 		    typedef lemon::Path<Digraph> Path;
@@ -99,3 +99,3 @@
 		  /// This class implements the Hartmann-Orlin algorithm for finding
-		  /// a directed cycle of minimum mean length (cost) in a digraph
 		  /// a directed cycle of minimum mean cost in a digraph
 		  /// \ref amo93networkflows, \ref dasdan98minmeancycle.
@@ -106,7 +106,7 @@
 		  /// \tparam GR The type of the digraph the algorithm runs on.
-		  /// \tparam LEN The type of the length map. The default
+		  /// \tparam CM The type of the cost map. The default
 		  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref HartmannOrlinDefaultTraits
 		  /// "HartmannOrlinDefaultTraits<GR, LEN>".
 		  /// algorithm. By default, it is \ref HartmannOrlinMmcDefaultTraits
 		  /// "HartmannOrlinMmcDefaultTraits<GR, CM>".
 		  /// In most cases, this parameter should not be set directly,
@@ -114,9 +114,9 @@
 		#ifdef DOXYGEN
-		  template <typename GR, typename LEN, typename TR>
+		  template <typename GR, typename CM, typename TR>
 		#else
 		  template < typename GR,
 		             typename LEN = typename GR::template ArcMap<int>,
 		             typename TR = HartmannOrlinDefaultTraits<GR, LEN> >
 		             typename CM = typename GR::template ArcMap<int>,
 		             typename TR = HartmannOrlinMmcDefaultTraits<GR, CM> >
 		#endif
-		  class HartmannOrlin
+		  class HartmannOrlinMmc
+		  {
@@ -126,13 +126,13 @@
 		    typedef typename TR::Digraph Digraph;
 		    /// The type of the length map
 		    typedef typename TR::LengthMap LengthMap;
 		    /// The type of the arc lengths
 		    typedef typename TR::Value Value;
 		    /// The type of the cost map
 		    typedef typename TR::CostMap CostMap;
 		    /// The type of the arc costs
 		    typedef typename TR::Cost Cost;
-		    /// \brief The large value type
+		    /// \brief The large cost type
 		    ///
 		    /// The large value type used for internal computations.
 		    /// By default, it is \c long \c long if the \c Value type is integer,
 		    /// The large cost type used for internal computations.
 		    /// By default, it is \c long \c long if the \c Cost type is integer,
 		    /// otherwise it is \c double.
-		    typedef typename TR::LargeValue LargeValue;
+		    typedef typename TR::LargeCost LargeCost;
@@ -144,3 +144,3 @@
 		    /// The path type of the found cycles.
-		    /// Using the \ref HartmannOrlinDefaultTraits "default traits class",
+		    /// Using the \ref HartmannOrlinMmcDefaultTraits "default traits class",
 		    /// it is \ref lemon::Path "Path<Digraph>".
@@ -148,3 +148,3 @@
-		    /// The \ref HartmannOrlinDefaultTraits "traits class" of the algorithm
+		    /// The \ref HartmannOrlinMmcDefaultTraits "traits class" of the algorithm
 		    typedef TR Traits;
@@ -158,5 +158,5 @@
+		    {
-		      LargeValue dist;
+		      LargeCost dist;
 		      Arc pred;
-		      PathData(LargeValue d, Arc p = INVALID) :
+		      PathData(LargeCost d, Arc p = INVALID) :
 		        dist(d), pred(p) {}
@@ -171,4 +171,4 @@
 		    const Digraph &_gr;
 		    // The length of the arcs
 		    const LengthMap &_length;
 		    // The cost of the arcs
 		    const CostMap &_cost;
@@ -183,3 +183,3 @@
 		    bool _curr_found, _best_found;
-		    LargeValue _curr_length, _best_length;
+		    LargeCost _curr_cost, _best_cost;
 		    int _curr_size, _best_size;
@@ -199,3 +199,3 @@
 		    // Infinite constant
-		    const LargeValue INF;
+		    const LargeCost INF;
@@ -207,4 +207,4 @@
 		    template <typename T>
 		    struct SetLargeValueTraits : public Traits {
 		      typedef T LargeValue;
 		    struct SetLargeCostTraits : public Traits {
 		      typedef T LargeCost;
 		      typedef lemon::Tolerance<T> Tolerance;
@@ -213,10 +213,10 @@
 		    /// \brief \ref named-templ-param "Named parameter" for setting
-		    /// \c LargeValue type.
+		    /// \c LargeCost type.
 		    ///
-		    /// \ref named-templ-param "Named parameter" for setting \c LargeValue
+		    /// \ref named-templ-param "Named parameter" for setting \c LargeCost
 		    /// type. It is used for internal computations in the algorithm.
 		    template <typename T>
 		    struct SetLargeValue
 		      : public HartmannOrlin<GR, LEN, SetLargeValueTraits<T> > {
-		      typedef HartmannOrlin<GR, LEN, SetLargeValueTraits<T> > Create;
+		    struct SetLargeCost
 		      : public HartmannOrlinMmc<GR, CM, SetLargeCostTraits<T> > {
 		      typedef HartmannOrlinMmc<GR, CM, SetLargeCostTraits<T> > Create;
 		    };
@@ -237,4 +237,4 @@
 		    struct SetPath
 		      : public HartmannOrlin<GR, LEN, SetPathTraits<T> > {
 		      typedef HartmannOrlin<GR, LEN, SetPathTraits<T> > Create;
 		      : public HartmannOrlinMmc<GR, CM, SetPathTraits<T> > {
 		      typedef HartmannOrlinMmc<GR, CM, SetPathTraits<T> > Create;
 		    };
@@ -245,3 +245,3 @@
-		    HartmannOrlin() {}
+		    HartmannOrlinMmc() {}
@@ -254,11 +254,11 @@
 		    /// \param digraph The digraph the algorithm runs on.
 		    /// \param length The lengths (costs) of the arcs.
 		    HartmannOrlin( const Digraph &digraph,
 		                   const LengthMap &length ) :
 		      _gr(digraph), _length(length), _comp(digraph), _out_arcs(digraph),
-		      _best_found(false), _best_length(0), _best_size(1),
+		    /// \param cost The costs of the arcs.
 		    HartmannOrlinMmc( const Digraph &digraph,
 		                      const CostMap &cost ) :
 		      _gr(digraph), _cost(cost), _comp(digraph), _out_arcs(digraph),
 		      _best_found(false), _best_cost(0), _best_size(1),
 		      _cycle_path(NULL), _local_path(false), _data(digraph),
 		      INF(std::numeric_limits<LargeValue>::has_infinity ?
 		          std::numeric_limits<LargeValue>::infinity() :
-		          std::numeric_limits<LargeValue>::max())
+		      INF(std::numeric_limits<LargeCost>::has_infinity ?
 		          std::numeric_limits<LargeCost>::infinity() :
 		          std::numeric_limits<LargeCost>::max())
 		    {}
@@ -266,3 +266,3 @@
 		    /// Destructor.
-		    ~HartmannOrlin() {
+		    ~HartmannOrlinMmc() {
 		      if (_local_path) delete _cycle_path;
@@ -276,3 +276,3 @@
 		    /// If you don't call this function before calling \ref run() or
-		    /// \ref findMinMean(), it will allocate a local \ref Path "path"
+		    /// \ref findCycleMean(), it will allocate a local \ref Path "path"
 		    /// structure. The destuctor deallocates this automatically
@@ -284,3 +284,3 @@
 		    /// \return <tt>(*this)</tt>
-		    HartmannOrlin& cycle(Path &path) {
+		    HartmannOrlinMmc& cycle(Path &path) {
 		      if (_local_path) {
@@ -298,3 +298,3 @@
 		    /// \return <tt>(*this)</tt>
-		    HartmannOrlin& tolerance(const Tolerance& tolerance) {
+		    HartmannOrlinMmc& tolerance(const Tolerance& tolerance) {
 		      _tolerance = tolerance;
@@ -314,4 +314,4 @@
 		    /// function.\n
 		    /// If you only need the minimum mean length, you may call
 		    /// \ref findMinMean().
 		    /// If you only need the minimum mean cost, you may call
 		    /// \ref findCycleMean().
@@ -323,3 +323,3 @@
 		    /// It can be called more than once (e.g. if the underlying digraph
-		    /// and/or the arc lengths have been modified).
+		    /// and/or the arc costs have been modified).
 		    ///
@@ -329,6 +329,6 @@
 		    /// \code
-		    ///   return mmc.findMinMean() && mmc.findCycle();
+		    ///   return mmc.findCycleMean() && mmc.findCycle();
 		    /// \endcode
 		    bool run() {
-		      return findMinMean() && findCycle();
+		      return findCycleMean() && findCycle();
+		    }
@@ -337,3 +337,3 @@
 		    ///
-		    /// This function finds the minimum mean length of the directed
+		    /// This function finds the minimum mean cost of the directed
 		    /// cycles in the digraph.
@@ -341,3 +341,3 @@
 		    /// \return \c true if a directed cycle exists in the digraph.
-		    bool findMinMean() {
+		    bool findCycleMean() {
 		      // Initialization and find strongly connected components
@@ -353,5 +353,5 @@
 		        if ( _curr_found && (!_best_found ||
-		             _curr_length * _best_size < _best_length * _curr_size) ) {
+		             _curr_cost * _best_size < _best_cost * _curr_size) ) {
 		          _best_found = true;
-		          _best_length = _curr_length;
+		          _best_cost = _curr_cost;
 		          _best_size = _curr_size;
@@ -366,4 +366,4 @@
 		    ///
 		    /// This function finds a directed cycle of minimum mean length
 		    /// in the digraph using the data computed by findMinMean().
 		    /// This function finds a directed cycle of minimum mean cost
 		    /// in the digraph using the data computed by findCycleMean().
 		    ///
@@ -371,3 +371,3 @@
 		    ///
-		    /// \pre \ref findMinMean() must be called before using this function.
+		    /// \pre \ref findCycleMean() must be called before using this function.
 		    bool findCycle() {
@@ -384,3 +384,3 @@
 		      _cycle_path->addFront(e);
-		      _best_length = _length[e];
+		      _best_cost = _cost[e];
 		      _best_size = 1;
@@ -390,3 +390,3 @@
 		        _cycle_path->addFront(e);
-		        _best_length += _length[e];
+		        _best_cost += _cost[e];
 		        ++_best_size;
@@ -405,10 +405,10 @@
-		    /// \brief Return the total length of the found cycle.
+		    /// \brief Return the total cost of the found cycle.
 		    ///
-		    /// This function returns the total length of the found cycle.
+		    /// This function returns the total cost of the found cycle.
 		    ///
-		    /// \pre \ref run() or \ref findMinMean() must be called before
+		    /// \pre \ref run() or \ref findCycleMean() must be called before
 		    /// using this function.
 		    Value cycleLength() const {
 		      return static_cast<Value>(_best_length);
 		    Cost cycleCost() const {
 		      return static_cast<Cost>(_best_cost);
+		    }
@@ -419,5 +419,5 @@
 		    ///
-		    /// \pre \ref run() or \ref findMinMean() must be called before
+		    /// \pre \ref run() or \ref findCycleMean() must be called before
 		    /// using this function.
-		    int cycleArcNum() const {
+		    int cycleSize() const {
 		      return _best_size;
@@ -425,5 +425,5 @@
-		    /// \brief Return the mean length of the found cycle.
+		    /// \brief Return the mean cost of the found cycle.
 		    ///
-		    /// This function returns the mean length of the found cycle.
+		    /// This function returns the mean cost of the found cycle.
 		    ///
@@ -432,9 +432,9 @@
 		    /// \code
-		    ///   return static_cast<double>(alg.cycleLength()) / alg.cycleArcNum();
+		    ///   return static_cast<double>(alg.cycleCost()) / alg.cycleSize();
 		    /// \endcode
 		    ///
-		    /// \pre \ref run() or \ref findMinMean() must be called before
+		    /// \pre \ref run() or \ref findCycleMean() must be called before
 		    /// using this function.
 		    double cycleMean() const {
-		      return static_cast<double>(_best_length) / _best_size;
+		      return static_cast<double>(_best_cost) / _best_size;
+		    }
@@ -464,3 +464,3 @@
 		      _best_found = false;
-		      _best_length = 0;
+		      _best_cost = 0;
 		      _best_size = 1;
@@ -513,3 +513,3 @@
 		    // Process all rounds of computing path data for the current component.
-		    // _data[v][k] is the length of a shortest directed walk from the root
+		    // _data[v][k] is the cost of a shortest directed walk from the root
 		    // node to node v containing exactly k arcs.
@@ -545,3 +545,3 @@
 		      Arc e;
-		      LargeValue d;
+		      LargeCost d;
 		      for (int i = 0; i < int(_process.size()); ++i) {
@@ -551,3 +551,3 @@
 		          v = _gr.target(e);
-		          d = _data[u][k-1].dist + _length[e];
+		          d = _data[u][k-1].dist + _cost[e];
 		          if (_tolerance.less(d, _data[v][k].dist)) {
@@ -565,3 +565,3 @@
 		      Arc e;
-		      LargeValue d;
+		      LargeCost d;
 		      for (int i = 0; i < int(_nodes->size()); ++i) {
@@ -571,3 +571,3 @@
 		          v = _gr.target(e);
-		          d = _data[u][k-1].dist + _length[e];
+		          d = _data[u][k-1].dist + _cost[e];
 		          if (_tolerance.less(d, _data[v][k].dist)) {
@@ -583,5 +583,5 @@
 		      typename GR::template NodeMap<Pair> level(_gr, Pair(-1, 0));
-		      typename GR::template NodeMap<LargeValue> pi(_gr);
+		      typename GR::template NodeMap<LargeCost> pi(_gr);
 		      int n = _nodes->size();
-		      LargeValue length;
+		      LargeCost cost;
 		      int size;
@@ -597,6 +597,6 @@
 		            // A cycle is found
-		            length = _data[u][level[u].second].dist - _data[u][j].dist;
+		            cost = _data[u][level[u].second].dist - _data[u][j].dist;
 		            size = level[u].second - j;
 		            if (!_curr_found || length * _curr_size < _curr_length * size) {
 		              _curr_length = length;
 		            if (!_curr_found || cost * _curr_size < _curr_cost * size) {
 		              _curr_cost = cost;
 		              _curr_size = size;
@@ -615,3 +615,3 @@
 		      // If at least one cycle is found, check the optimality condition
-		      LargeValue d;
+		      LargeCost d;
 		      if (_curr_found && k < n) {
@@ -623,3 +623,3 @@
 		            if (_data[u][j].dist < INF) {
-		              d = _data[u][j].dist * _curr_size - j * _curr_length;
+		              d = _data[u][j].dist * _curr_size - j * _curr_cost;
 		              if (_tolerance.less(d, pi[u])) pi[u] = d;
@@ -632,3 +632,3 @@
 		        for (ArcIt a(_gr); a != INVALID; ++a) {
-		          if (_tolerance.less(_length[a] * _curr_size - _curr_length,
+		          if (_tolerance.less(_cost[a] * _curr_size - _curr_cost,
 		                              pi[_gr.target(a)] - pi[_gr.source(a)]) ) {
@@ -643,3 +643,3 @@
-		  }; //class HartmannOrlin
+		  }; //class HartmannOrlinMmc
@@ -649,2 +649,2 @@
-		#endif //LEMON_HARTMANN_ORLIN_H
+		#endif //LEMON_HARTMANN_ORLIN_MMC_H

lemon/howard_mmc.h

Show inline comments

@@ -18,4 +18,4 @@
 		#ifndef LEMON_HOWARD_H
 		#define LEMON_HOWARD_H
 		#ifndef LEMON_HOWARD_MMC_H
 		#define LEMON_HOWARD_MMC_H
@@ -35,15 +35,15 @@
-		  /// \brief Default traits class of Howard class.
+		  /// \brief Default traits class of HowardMmc class.
 		  ///
-		  /// Default traits class of Howard class.
+		  /// Default traits class of HowardMmc class.
 		  /// \tparam GR The type of the digraph.
-		  /// \tparam LEN The type of the length map.
+		  /// \tparam CM The type of the cost map.
 		  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		#ifdef DOXYGEN
-		  template <typename GR, typename LEN>
+		  template <typename GR, typename CM>
 		#else
 		  template <typename GR, typename LEN,
 		    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
 		  template <typename GR, typename CM,
 		    bool integer = std::numeric_limits<typename CM::Value>::is_integer>
 		#endif
-		  struct HowardDefaultTraits
+		  struct HowardMmcDefaultTraits
+		  {
@@ -51,17 +51,17 @@
 		    typedef GR Digraph;
 		    /// The type of the length map
 		    typedef LEN LengthMap;
 		    /// The type of the arc lengths
 		    typedef typename LengthMap::Value Value;
 		    /// The type of the cost map
 		    typedef CM CostMap;
 		    /// The type of the arc costs
 		    typedef typename CostMap::Value Cost;
-		    /// \brief The large value type used for internal computations
+		    /// \brief The large cost 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,
 		    /// The large cost type used for internal computations.
 		    /// It is \c long \c long if the \c Cost type is integer,
 		    /// otherwise it is \c double.
 		    /// \c Value must be convertible to \c LargeValue.
 		    typedef double LargeValue;
 		    /// \c Cost must be convertible to \c LargeCost.
 		    typedef double LargeCost;
 		    /// The tolerance type used for internal computations
-		    typedef lemon::Tolerance<LargeValue> Tolerance;
+		    typedef lemon::Tolerance<LargeCost> Tolerance;
@@ -75,15 +75,15 @@
 		  // Default traits class for integer value types
 		  template <typename GR, typename LEN>
-		  struct HowardDefaultTraits<GR, LEN, true>
+		  // Default traits class for integer cost types
 		  template <typename GR, typename CM>
 		  struct HowardMmcDefaultTraits<GR, CM, true>
+		  {
 		    typedef GR Digraph;
 		    typedef LEN LengthMap;
 		    typedef typename LengthMap::Value Value;
 		    typedef CM CostMap;
 		    typedef typename CostMap::Value Cost;
 		#ifdef LEMON_HAVE_LONG_LONG
-		    typedef long long LargeValue;
+		    typedef long long LargeCost;
 		#else
-		    typedef long LargeValue;
+		    typedef long LargeCost;
 		#endif
-		    typedef lemon::Tolerance<LargeValue> Tolerance;
+		    typedef lemon::Tolerance<LargeCost> Tolerance;
 		    typedef lemon::Path<Digraph> Path;
@@ -99,3 +99,3 @@
 		  /// This class implements Howard's policy iteration algorithm for finding
-		  /// a directed cycle of minimum mean length (cost) in a digraph
 		  /// a directed cycle of minimum mean cost in a digraph
 		  /// \ref amo93networkflows, \ref dasdan98minmeancycle.
@@ -106,7 +106,7 @@
 		  /// \tparam GR The type of the digraph the algorithm runs on.
-		  /// \tparam LEN The type of the length map. The default
+		  /// \tparam CM The type of the cost map. The default
 		  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref HowardDefaultTraits
 		  /// "HowardDefaultTraits<GR, LEN>".
 		  /// algorithm. By default, it is \ref HowardMmcDefaultTraits
 		  /// "HowardMmcDefaultTraits<GR, CM>".
 		  /// In most cases, this parameter should not be set directly,
@@ -114,9 +114,9 @@
 		#ifdef DOXYGEN
-		  template <typename GR, typename LEN, typename TR>
+		  template <typename GR, typename CM, typename TR>
 		#else
 		  template < typename GR,
 		             typename LEN = typename GR::template ArcMap<int>,
 		             typename TR = HowardDefaultTraits<GR, LEN> >
 		             typename CM = typename GR::template ArcMap<int>,
 		             typename TR = HowardMmcDefaultTraits<GR, CM> >
 		#endif
-		  class Howard
+		  class HowardMmc
+		  {
@@ -126,13 +126,13 @@
 		    typedef typename TR::Digraph Digraph;
 		    /// The type of the length map
 		    typedef typename TR::LengthMap LengthMap;
 		    /// The type of the arc lengths
 		    typedef typename TR::Value Value;
 		    /// The type of the cost map
 		    typedef typename TR::CostMap CostMap;
 		    /// The type of the arc costs
 		    typedef typename TR::Cost Cost;
-		    /// \brief The large value type
+		    /// \brief The large cost type
 		    ///
 		    /// The large value type used for internal computations.
 		    /// By default, it is \c long \c long if the \c Value type is integer,
 		    /// The large cost type used for internal computations.
 		    /// By default, it is \c long \c long if the \c Cost type is integer,
 		    /// otherwise it is \c double.
-		    typedef typename TR::LargeValue LargeValue;
+		    typedef typename TR::LargeCost LargeCost;
@@ -144,3 +144,3 @@
 		    /// The path type of the found cycles.
-		    /// Using the \ref HowardDefaultTraits "default traits class",
+		    /// Using the \ref HowardMmcDefaultTraits "default traits class",
 		    /// it is \ref lemon::Path "Path<Digraph>".
@@ -148,3 +148,3 @@
-		    /// The \ref HowardDefaultTraits "traits class" of the algorithm
+		    /// The \ref HowardMmcDefaultTraits "traits class" of the algorithm
 		    typedef TR Traits;
@@ -157,4 +157,4 @@
 		    const Digraph &_gr;
 		    // The length of the arcs
 		    const LengthMap &_length;
 		    // The cost of the arcs
 		    const CostMap &_cost;
@@ -162,3 +162,3 @@
 		    bool _curr_found, _best_found;
-		    LargeValue _curr_length, _best_length;
+		    LargeCost _curr_cost, _best_cost;
 		    int _curr_size, _best_size;
@@ -173,3 +173,3 @@
 		    typename Digraph::template NodeMap<int> _level;
-		    typename Digraph::template NodeMap<LargeValue> _dist;
+		    typename Digraph::template NodeMap<LargeCost> _dist;
@@ -189,3 +189,3 @@
 		    // Infinite constant
-		    const LargeValue INF;
+		    const LargeCost INF;
@@ -197,4 +197,4 @@
 		    template <typename T>
 		    struct SetLargeValueTraits : public Traits {
 		      typedef T LargeValue;
 		    struct SetLargeCostTraits : public Traits {
 		      typedef T LargeCost;
 		      typedef lemon::Tolerance<T> Tolerance;
@@ -203,10 +203,10 @@
 		    /// \brief \ref named-templ-param "Named parameter" for setting
-		    /// \c LargeValue type.
+		    /// \c LargeCost type.
 		    ///
-		    /// \ref named-templ-param "Named parameter" for setting \c LargeValue
+		    /// \ref named-templ-param "Named parameter" for setting \c LargeCost
 		    /// type. It is used for internal computations in the algorithm.
 		    template <typename T>
 		    struct SetLargeValue
 		      : public Howard<GR, LEN, SetLargeValueTraits<T> > {
-		      typedef Howard<GR, LEN, SetLargeValueTraits<T> > Create;
+		    struct SetLargeCost
 		      : public HowardMmc<GR, CM, SetLargeCostTraits<T> > {
 		      typedef HowardMmc<GR, CM, SetLargeCostTraits<T> > Create;
 		    };
@@ -227,4 +227,4 @@
 		    struct SetPath
 		      : public Howard<GR, LEN, SetPathTraits<T> > {
 		      typedef Howard<GR, LEN, SetPathTraits<T> > Create;
 		      : public HowardMmc<GR, CM, SetPathTraits<T> > {
 		      typedef HowardMmc<GR, CM, SetPathTraits<T> > Create;
 		    };
@@ -235,3 +235,3 @@
-		    Howard() {}
+		    HowardMmc() {}
@@ -244,12 +244,12 @@
 		    /// \param digraph The digraph the algorithm runs on.
 		    /// \param length The lengths (costs) of the arcs.
 		    Howard( const Digraph &digraph,
 		            const LengthMap &length ) :
 		      _gr(digraph), _length(length), _best_found(false),
-		      _best_length(0), _best_size(1), _cycle_path(NULL), _local_path(false),
+		    /// \param cost The costs of the arcs.
 		    HowardMmc( const Digraph &digraph,
 		               const CostMap &cost ) :
 		      _gr(digraph), _cost(cost), _best_found(false),
 		      _best_cost(0), _best_size(1), _cycle_path(NULL), _local_path(false),
 		      _policy(digraph), _reached(digraph), _level(digraph), _dist(digraph),
 		      _comp(digraph), _in_arcs(digraph),
 		      INF(std::numeric_limits<LargeValue>::has_infinity ?
 		          std::numeric_limits<LargeValue>::infinity() :
-		          std::numeric_limits<LargeValue>::max())
+		      INF(std::numeric_limits<LargeCost>::has_infinity ?
 		          std::numeric_limits<LargeCost>::infinity() :
 		          std::numeric_limits<LargeCost>::max())
 		    {}
@@ -257,3 +257,3 @@
 		    /// Destructor.
-		    ~Howard() {
+		    ~HowardMmc() {
 		      if (_local_path) delete _cycle_path;
@@ -267,3 +267,3 @@
 		    /// If you don't call this function before calling \ref run() or
-		    /// \ref findMinMean(), it will allocate a local \ref Path "path"
+		    /// \ref findCycleMean(), it will allocate a local \ref Path "path"
 		    /// structure. The destuctor deallocates this automatically
@@ -275,3 +275,3 @@
 		    /// \return <tt>(*this)</tt>
-		    Howard& cycle(Path &path) {
+		    HowardMmc& cycle(Path &path) {
 		      if (_local_path) {
@@ -289,3 +289,3 @@
 		    /// \return <tt>(*this)</tt>
-		    Howard& tolerance(const Tolerance& tolerance) {
+		    HowardMmc& tolerance(const Tolerance& tolerance) {
 		      _tolerance = tolerance;
@@ -305,4 +305,4 @@
 		    /// function.\n
 		    /// If you only need the minimum mean length, you may call
 		    /// \ref findMinMean().
 		    /// If you only need the minimum mean cost, you may call
 		    /// \ref findCycleMean().
@@ -314,3 +314,3 @@
 		    /// It can be called more than once (e.g. if the underlying digraph
-		    /// and/or the arc lengths have been modified).
+		    /// and/or the arc costs have been modified).
 		    ///
@@ -320,6 +320,6 @@
 		    /// \code
-		    ///   return mmc.findMinMean() && mmc.findCycle();
+		    ///   return mmc.findCycleMean() && mmc.findCycle();
 		    /// \endcode
 		    bool run() {
-		      return findMinMean() && findCycle();
+		      return findCycleMean() && findCycle();
+		    }
@@ -328,3 +328,3 @@
 		    ///
-		    /// This function finds the minimum mean length of the directed
+		    /// This function finds the minimum mean cost of the directed
 		    /// cycles in the digraph.
@@ -332,3 +332,3 @@
 		    /// \return \c true if a directed cycle exists in the digraph.
-		    bool findMinMean() {
+		    bool findCycleMean() {
 		      // Initialize and find strongly connected components
@@ -347,5 +347,5 @@
 		        if ( _curr_found && (!_best_found ||
-		             _curr_length * _best_size < _best_length * _curr_size) ) {
+		             _curr_cost * _best_size < _best_cost * _curr_size) ) {
 		          _best_found = true;
-		          _best_length = _curr_length;
+		          _best_cost = _curr_cost;
 		          _best_size = _curr_size;
@@ -359,4 +359,4 @@
 		    ///
 		    /// This function finds a directed cycle of minimum mean length
 		    /// in the digraph using the data computed by findMinMean().
 		    /// This function finds a directed cycle of minimum mean cost
 		    /// in the digraph using the data computed by findCycleMean().
 		    ///
@@ -364,3 +364,3 @@
 		    ///
-		    /// \pre \ref findMinMean() must be called before using this function.
+		    /// \pre \ref findCycleMean() must be called before using this function.
 		    bool findCycle() {
@@ -384,10 +384,10 @@
-		    /// \brief Return the total length of the found cycle.
+		    /// \brief Return the total cost of the found cycle.
 		    ///
-		    /// This function returns the total length of the found cycle.
+		    /// This function returns the total cost of the found cycle.
 		    ///
-		    /// \pre \ref run() or \ref findMinMean() must be called before
+		    /// \pre \ref run() or \ref findCycleMean() must be called before
 		    /// using this function.
 		    Value cycleLength() const {
 		      return static_cast<Value>(_best_length);
 		    Cost cycleCost() const {
 		      return static_cast<Cost>(_best_cost);
+		    }
@@ -398,5 +398,5 @@
 		    ///
-		    /// \pre \ref run() or \ref findMinMean() must be called before
+		    /// \pre \ref run() or \ref findCycleMean() must be called before
 		    /// using this function.
-		    int cycleArcNum() const {
+		    int cycleSize() const {
 		      return _best_size;
@@ -404,5 +404,5 @@
-		    /// \brief Return the mean length of the found cycle.
+		    /// \brief Return the mean cost of the found cycle.
 		    ///
-		    /// This function returns the mean length of the found cycle.
+		    /// This function returns the mean cost of the found cycle.
 		    ///
@@ -411,9 +411,9 @@
 		    /// \code
-		    ///   return static_cast<double>(alg.cycleLength()) / alg.cycleArcNum();
+		    ///   return static_cast<double>(alg.cycleCost()) / alg.cycleSize();
 		    /// \endcode
 		    ///
-		    /// \pre \ref run() or \ref findMinMean() must be called before
+		    /// \pre \ref run() or \ref findCycleMean() must be called before
 		    /// using this function.
 		    double cycleMean() const {
-		      return static_cast<double>(_best_length) / _best_size;
+		      return static_cast<double>(_best_cost) / _best_size;
+		    }
@@ -443,3 +443,3 @@
 		      _best_found = false;
-		      _best_length = 0;
+		      _best_cost = 0;
 		      _best_size = 1;
@@ -494,4 +494,4 @@
 		          u = _gr.source(e);
 		          if (_length[e] < _dist[u]) {
 		            _dist[u] = _length[e];
 		          if (_cost[e] < _dist[u]) {
 		            _dist[u] = _cost[e];
 		            _policy[u] = e;
@@ -508,3 +508,3 @@
+		      }
-		      LargeValue clength;
+		      LargeCost ccost;
 		      int csize;
@@ -520,6 +520,6 @@
 		          // A cycle is found
-		          clength = _length[_policy[u]];
+		          ccost = _cost[_policy[u]];
 		          csize = 1;
 		          for (v = u; (v = _gr.target(_policy[v])) != u; ) {
-		            clength += _length[_policy[v]];
+		            ccost += _cost[_policy[v]];
 		            ++csize;
@@ -527,5 +527,5 @@
 		          if ( !_curr_found ||
-		               (clength * _curr_size < _curr_length * csize) ) {
+		               (ccost * _curr_size < _curr_cost * csize) ) {
 		            _curr_found = true;
-		            _curr_length = clength;
+		            _curr_cost = ccost;
 		            _curr_size = csize;
@@ -557,3 +557,3 @@
 		            _reached[u] = true;
-		            _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
+		            _dist[u] = _dist[v] + _cost[e] * _curr_size - _curr_cost;
 		            _queue[++_qback] = u;
@@ -574,3 +574,3 @@
 		            _policy[u] = e;
-		            _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
+		            _dist[u] = _dist[v] + _cost[e] * _curr_size - _curr_cost;
 		            _queue[++_qback] = u;
@@ -587,3 +587,3 @@
 		          u = _gr.source(e);
-		          LargeValue delta = _dist[v] + _length[e] * _curr_size - _curr_length;
+		          LargeCost delta = _dist[v] + _cost[e] * _curr_size - _curr_cost;
 		          if (_tolerance.less(delta, _dist[u])) {
@@ -598,3 +598,3 @@
-		  }; //class Howard
+		  }; //class HowardMmc
@@ -604,2 +604,2 @@
-		#endif //LEMON_HOWARD_H
+		#endif //LEMON_HOWARD_MMC_H

lemon/karp_mmc.h

Show inline comments

@@ -18,4 +18,4 @@
 		#ifndef LEMON_KARP_H
 		#define LEMON_KARP_H
 		#ifndef LEMON_KARP_MMC_H
 		#define LEMON_KARP_MMC_H
@@ -35,15 +35,15 @@
-		  /// \brief Default traits class of Karp algorithm.
+		  /// \brief Default traits class of KarpMmc class.
 		  ///
-		  /// Default traits class of Karp algorithm.
+		  /// Default traits class of KarpMmc class.
 		  /// \tparam GR The type of the digraph.
-		  /// \tparam LEN The type of the length map.
+		  /// \tparam CM The type of the cost map.
 		  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		#ifdef DOXYGEN
-		  template <typename GR, typename LEN>
+		  template <typename GR, typename CM>
 		#else
 		  template <typename GR, typename LEN,
 		    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
 		  template <typename GR, typename CM,
 		    bool integer = std::numeric_limits<typename CM::Value>::is_integer>
 		#endif
-		  struct KarpDefaultTraits
+		  struct KarpMmcDefaultTraits
+		  {
@@ -51,17 +51,17 @@
 		    typedef GR Digraph;
 		    /// The type of the length map
 		    typedef LEN LengthMap;
 		    /// The type of the arc lengths
 		    typedef typename LengthMap::Value Value;
 		    /// The type of the cost map
 		    typedef CM CostMap;
 		    /// The type of the arc costs
 		    typedef typename CostMap::Value Cost;
-		    /// \brief The large value type used for internal computations
+		    /// \brief The large cost 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,
 		    /// The large cost type used for internal computations.
 		    /// It is \c long \c long if the \c Cost type is integer,
 		    /// otherwise it is \c double.
 		    /// \c Value must be convertible to \c LargeValue.
 		    typedef double LargeValue;
 		    /// \c Cost must be convertible to \c LargeCost.
 		    typedef double LargeCost;
 		    /// The tolerance type used for internal computations
-		    typedef lemon::Tolerance<LargeValue> Tolerance;
+		    typedef lemon::Tolerance<LargeCost> Tolerance;
@@ -75,15 +75,15 @@
 		  // Default traits class for integer value types
 		  template <typename GR, typename LEN>
-		  struct KarpDefaultTraits<GR, LEN, true>
+		  // Default traits class for integer cost types
 		  template <typename GR, typename CM>
 		  struct KarpMmcDefaultTraits<GR, CM, true>
+		  {
 		    typedef GR Digraph;
 		    typedef LEN LengthMap;
 		    typedef typename LengthMap::Value Value;
 		    typedef CM CostMap;
 		    typedef typename CostMap::Value Cost;
 		#ifdef LEMON_HAVE_LONG_LONG
-		    typedef long long LargeValue;
+		    typedef long long LargeCost;
 		#else
-		    typedef long LargeValue;
+		    typedef long LargeCost;
 		#endif
-		    typedef lemon::Tolerance<LargeValue> Tolerance;
+		    typedef lemon::Tolerance<LargeCost> Tolerance;
 		    typedef lemon::Path<Digraph> Path;
@@ -99,3 +99,3 @@
 		  /// This class implements Karp's algorithm for finding a directed
-		  /// cycle of minimum mean length (cost) in a digraph
 		  /// cycle of minimum mean cost in a digraph
 		  /// \ref amo93networkflows, \ref dasdan98minmeancycle.
@@ -104,7 +104,7 @@
 		  /// \tparam GR The type of the digraph the algorithm runs on.
-		  /// \tparam LEN The type of the length map. The default
+		  /// \tparam CM The type of the cost map. The default
 		  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref KarpDefaultTraits
 		  /// "KarpDefaultTraits<GR, LEN>".
 		  /// algorithm. By default, it is \ref KarpMmcDefaultTraits
 		  /// "KarpMmcDefaultTraits<GR, CM>".
 		  /// In most cases, this parameter should not be set directly,
@@ -112,9 +112,9 @@
 		#ifdef DOXYGEN
-		  template <typename GR, typename LEN, typename TR>
+		  template <typename GR, typename CM, typename TR>
 		#else
 		  template < typename GR,
 		             typename LEN = typename GR::template ArcMap<int>,
 		             typename TR = KarpDefaultTraits<GR, LEN> >
 		             typename CM = typename GR::template ArcMap<int>,
 		             typename TR = KarpMmcDefaultTraits<GR, CM> >
 		#endif
-		  class Karp
+		  class KarpMmc
+		  {
@@ -124,13 +124,13 @@
 		    typedef typename TR::Digraph Digraph;
 		    /// The type of the length map
 		    typedef typename TR::LengthMap LengthMap;
 		    /// The type of the arc lengths
 		    typedef typename TR::Value Value;
 		    /// The type of the cost map
 		    typedef typename TR::CostMap CostMap;
 		    /// The type of the arc costs
 		    typedef typename TR::Cost Cost;
-		    /// \brief The large value type
+		    /// \brief The large cost type
 		    ///
 		    /// The large value type used for internal computations.
 		    /// By default, it is \c long \c long if the \c Value type is integer,
 		    /// The large cost type used for internal computations.
 		    /// By default, it is \c long \c long if the \c Cost type is integer,
 		    /// otherwise it is \c double.
-		    typedef typename TR::LargeValue LargeValue;
+		    typedef typename TR::LargeCost LargeCost;
@@ -142,3 +142,3 @@
 		    /// The path type of the found cycles.
-		    /// Using the \ref KarpDefaultTraits "default traits class",
+		    /// Using the \ref KarpMmcDefaultTraits "default traits class",
 		    /// it is \ref lemon::Path "Path<Digraph>".
@@ -146,3 +146,3 @@
-		    /// The \ref KarpDefaultTraits "traits class" of the algorithm
+		    /// The \ref KarpMmcDefaultTraits "traits class" of the algorithm
 		    typedef TR Traits;
@@ -156,5 +156,5 @@
+		    {
-		      LargeValue dist;
+		      LargeCost dist;
 		      Arc pred;
-		      PathData(LargeValue d, Arc p = INVALID) :
+		      PathData(LargeCost d, Arc p = INVALID) :
 		        dist(d), pred(p) {}
@@ -169,4 +169,4 @@
 		    const Digraph &_gr;
 		    // The length of the arcs
 		    const LengthMap &_length;
 		    // The cost of the arcs
 		    const CostMap &_cost;
@@ -180,3 +180,3 @@
 		    // Data for the found cycle
-		    LargeValue _cycle_length;
+		    LargeCost _cycle_cost;
 		    int _cycle_size;
@@ -195,3 +195,3 @@
 		    // Infinite constant
-		    const LargeValue INF;
+		    const LargeCost INF;
@@ -203,4 +203,4 @@
 		    template <typename T>
 		    struct SetLargeValueTraits : public Traits {
 		      typedef T LargeValue;
 		    struct SetLargeCostTraits : public Traits {
 		      typedef T LargeCost;
 		      typedef lemon::Tolerance<T> Tolerance;
@@ -209,10 +209,10 @@
 		    /// \brief \ref named-templ-param "Named parameter" for setting
-		    /// \c LargeValue type.
+		    /// \c LargeCost type.
 		    ///
-		    /// \ref named-templ-param "Named parameter" for setting \c LargeValue
+		    /// \ref named-templ-param "Named parameter" for setting \c LargeCost
 		    /// type. It is used for internal computations in the algorithm.
 		    template <typename T>
 		    struct SetLargeValue
 		      : public Karp<GR, LEN, SetLargeValueTraits<T> > {
-		      typedef Karp<GR, LEN, SetLargeValueTraits<T> > Create;
+		    struct SetLargeCost
 		      : public KarpMmc<GR, CM, SetLargeCostTraits<T> > {
 		      typedef KarpMmc<GR, CM, SetLargeCostTraits<T> > Create;
 		    };
@@ -233,4 +233,4 @@
 		    struct SetPath
 		      : public Karp<GR, LEN, SetPathTraits<T> > {
 		      typedef Karp<GR, LEN, SetPathTraits<T> > Create;
 		      : public KarpMmc<GR, CM, SetPathTraits<T> > {
 		      typedef KarpMmc<GR, CM, SetPathTraits<T> > Create;
 		    };
@@ -241,3 +241,3 @@
-		    Karp() {}
+		    KarpMmc() {}
@@ -250,11 +250,11 @@
 		    /// \param digraph The digraph the algorithm runs on.
 		    /// \param length The lengths (costs) of the arcs.
 		    Karp( const Digraph &digraph,
 		          const LengthMap &length ) :
 		      _gr(digraph), _length(length), _comp(digraph), _out_arcs(digraph),
-		      _cycle_length(0), _cycle_size(1), _cycle_node(INVALID),
+		    /// \param cost The costs of the arcs.
 		    KarpMmc( const Digraph &digraph,
 		             const CostMap &cost ) :
 		      _gr(digraph), _cost(cost), _comp(digraph), _out_arcs(digraph),
 		      _cycle_cost(0), _cycle_size(1), _cycle_node(INVALID),
 		      _cycle_path(NULL), _local_path(false), _data(digraph),
 		      INF(std::numeric_limits<LargeValue>::has_infinity ?
 		          std::numeric_limits<LargeValue>::infinity() :
-		          std::numeric_limits<LargeValue>::max())
+		      INF(std::numeric_limits<LargeCost>::has_infinity ?
 		          std::numeric_limits<LargeCost>::infinity() :
 		          std::numeric_limits<LargeCost>::max())
 		    {}
@@ -262,3 +262,3 @@
 		    /// Destructor.
-		    ~Karp() {
+		    ~KarpMmc() {
 		      if (_local_path) delete _cycle_path;
@@ -272,3 +272,3 @@
 		    /// If you don't call this function before calling \ref run() or
-		    /// \ref findMinMean(), it will allocate a local \ref Path "path"
+		    /// \ref findCycleMean(), it will allocate a local \ref Path "path"
 		    /// structure. The destuctor deallocates this automatically
@@ -280,3 +280,3 @@
 		    /// \return <tt>(*this)</tt>
-		    Karp& cycle(Path &path) {
+		    KarpMmc& cycle(Path &path) {
 		      if (_local_path) {
@@ -294,3 +294,3 @@
 		    /// \return <tt>(*this)</tt>
-		    Karp& tolerance(const Tolerance& tolerance) {
+		    KarpMmc& tolerance(const Tolerance& tolerance) {
 		      _tolerance = tolerance;
@@ -310,4 +310,4 @@
 		    /// function.\n
 		    /// If you only need the minimum mean length, you may call
 		    /// \ref findMinMean().
 		    /// If you only need the minimum mean cost, you may call
 		    /// \ref findCycleMean().
@@ -319,3 +319,3 @@
 		    /// It can be called more than once (e.g. if the underlying digraph
-		    /// and/or the arc lengths have been modified).
+		    /// and/or the arc costs have been modified).
 		    ///
@@ -325,6 +325,6 @@
 		    /// \code
-		    ///   return mmc.findMinMean() && mmc.findCycle();
+		    ///   return mmc.findCycleMean() && mmc.findCycle();
 		    /// \endcode
 		    bool run() {
-		      return findMinMean() && findCycle();
+		      return findCycleMean() && findCycle();
+		    }
@@ -333,3 +333,3 @@
 		    ///
-		    /// This function finds the minimum mean length of the directed
+		    /// This function finds the minimum mean cost of the directed
 		    /// cycles in the digraph.
@@ -337,3 +337,3 @@
 		    /// \return \c true if a directed cycle exists in the digraph.
-		    bool findMinMean() {
+		    bool findCycleMean() {
 		      // Initialization and find strongly connected components
@@ -353,4 +353,4 @@
 		    ///
 		    /// This function finds a directed cycle of minimum mean length
 		    /// in the digraph using the data computed by findMinMean().
 		    /// This function finds a directed cycle of minimum mean cost
 		    /// in the digraph using the data computed by findCycleMean().
 		    ///
@@ -358,3 +358,3 @@
 		    ///
-		    /// \pre \ref findMinMean() must be called before using this function.
+		    /// \pre \ref findCycleMean() must be called before using this function.
 		    bool findCycle() {
@@ -371,3 +371,3 @@
 		      _cycle_path->addFront(e);
-		      _cycle_length = _length[e];
+		      _cycle_cost = _cost[e];
 		      _cycle_size = 1;
@@ -377,3 +377,3 @@
 		        _cycle_path->addFront(e);
-		        _cycle_length += _length[e];
+		        _cycle_cost += _cost[e];
 		        ++_cycle_size;
@@ -392,10 +392,10 @@
-		    /// \brief Return the total length of the found cycle.
+		    /// \brief Return the total cost of the found cycle.
 		    ///
-		    /// This function returns the total length of the found cycle.
+		    /// This function returns the total cost of the found cycle.
 		    ///
-		    /// \pre \ref run() or \ref findMinMean() must be called before
+		    /// \pre \ref run() or \ref findCycleMean() must be called before
 		    /// using this function.
 		    Value cycleLength() const {
 		      return static_cast<Value>(_cycle_length);
 		    Cost cycleCost() const {
 		      return static_cast<Cost>(_cycle_cost);
+		    }
@@ -406,5 +406,5 @@
 		    ///
-		    /// \pre \ref run() or \ref findMinMean() must be called before
+		    /// \pre \ref run() or \ref findCycleMean() must be called before
 		    /// using this function.
-		    int cycleArcNum() const {
+		    int cycleSize() const {
 		      return _cycle_size;
@@ -412,5 +412,5 @@
-		    /// \brief Return the mean length of the found cycle.
+		    /// \brief Return the mean cost of the found cycle.
 		    ///
-		    /// This function returns the mean length of the found cycle.
+		    /// This function returns the mean cost of the found cycle.
 		    ///
@@ -419,9 +419,9 @@
 		    /// \code
-		    ///   return static_cast<double>(alg.cycleLength()) / alg.cycleArcNum();
+		    ///   return static_cast<double>(alg.cycleCost()) / alg.cycleSize();
 		    /// \endcode
 		    ///
-		    /// \pre \ref run() or \ref findMinMean() must be called before
+		    /// \pre \ref run() or \ref findCycleMean() must be called before
 		    /// using this function.
 		    double cycleMean() const {
-		      return static_cast<double>(_cycle_length) / _cycle_size;
+		      return static_cast<double>(_cycle_cost) / _cycle_size;
+		    }
@@ -450,3 +450,3 @@
 		      _cycle_path->clear();
-		      _cycle_length = 0;
+		      _cycle_cost = 0;
 		      _cycle_size = 1;
@@ -499,3 +499,3 @@
 		    // Process all rounds of computing path data for the current component.
-		    // _data[v][k] is the length of a shortest directed walk from the root
+		    // _data[v][k] is the cost of a shortest directed walk from the root
 		    // node to node v containing exactly k arcs.
@@ -521,3 +521,3 @@
 		      Arc e;
-		      LargeValue d;
+		      LargeCost d;
 		      for (int i = 0; i < int(_process.size()); ++i) {
@@ -527,3 +527,3 @@
 		          v = _gr.target(e);
-		          d = _data[u][k-1].dist + _length[e];
+		          d = _data[u][k-1].dist + _cost[e];
 		          if (_tolerance.less(d, _data[v][k].dist)) {
@@ -541,3 +541,3 @@
 		      Arc e;
-		      LargeValue d;
+		      LargeCost d;
 		      for (int i = 0; i < int(_nodes->size()); ++i) {
@@ -547,3 +547,3 @@
 		          v = _gr.target(e);
-		          d = _data[u][k-1].dist + _length[e];
+		          d = _data[u][k-1].dist + _cost[e];
 		          if (_tolerance.less(d, _data[v][k].dist)) {
@@ -561,3 +561,3 @@
 		        if (_data[u][n].dist == INF) continue;
-		        LargeValue length, max_length = 0;
+		        LargeCost cost, max_cost = 0;
 		        int size, max_size = 1;
@@ -566,7 +566,7 @@
 		          if (_data[u][k].dist == INF) continue;
-		          length = _data[u][n].dist - _data[u][k].dist;
+		          cost = _data[u][n].dist - _data[u][k].dist;
 		          size = n - k;
-		          if (!found_curr || length * max_size > max_length * size) {
+		          if (!found_curr || cost * max_size > max_cost * size) {
 		            found_curr = true;
-		            max_length = length;
+		            max_cost = cost;
 		            max_size = size;
@@ -575,4 +575,4 @@
 		        if ( found_curr && (_cycle_node == INVALID ||
 		             max_length * _cycle_size < _cycle_length * max_size) ) {
 		          _cycle_length = max_length;
 		             max_cost * _cycle_size < _cycle_cost * max_size) ) {
 		          _cycle_cost = max_cost;
 		          _cycle_size = max_size;
@@ -583,3 +583,3 @@
-		  }; //class Karp
+		  }; //class KarpMmc
@@ -589,2 +589,2 @@
-		#endif //LEMON_KARP_H
+		#endif //LEMON_KARP_MMC_H

test/min_mean_cycle_test.cc

Show inline comments

@@ -27,5 +27,5 @@
 		#include <lemon/karp.h>
 		#include <lemon/hartmann_orlin.h>
-		#include <lemon/howard.h>
+		#include <lemon/karp_mmc.h>
 		#include <lemon/hartmann_orlin_mmc.h>
 		#include <lemon/howard_mmc.h>
@@ -65,3 +65,3 @@
 		// Check the interface of an MMC algorithm
-		template <typename GR, typename Value>
+		template <typename GR, typename Cost>
 		struct MmcClassConcept
@@ -75,5 +75,5 @@
 		        ::template SetPath<ListPath<GR> >
-		        ::template SetLargeValue<Value>
+		        ::template SetLargeCost<Cost>
 		        ::Create MmcAlg;
-		      MmcAlg mmc(me.g, me.length);
+		      MmcAlg mmc(me.g, me.cost);
 		      const MmcAlg& const_mmc = mmc;
@@ -84,7 +84,7 @@
 		      b = mmc.cycle(p).run();
-		      b = mmc.findMinMean();
+		      b = mmc.findCycleMean();
 		      b = mmc.findCycle();
 		      v = const_mmc.cycleLength();
 		      i = const_mmc.cycleArcNum();
 		      v = const_mmc.cycleCost();
 		      i = const_mmc.cycleSize();
 		      d = const_mmc.cycleMean();
@@ -93,8 +93,8 @@
-		    typedef concepts::ReadMap<typename GR::Arc, Value> LM;
+		    typedef concepts::ReadMap<typename GR::Arc, Cost> CM;
 		    GR g;
-		    LM length;
+		    CM cost;
 		    ListPath<GR> p;
-		    Value v;
+		    Cost v;
 		    int i;
@@ -110,9 +110,9 @@
 		                 const SmartDigraph::ArcMap<int>& cm,
-		                 int length, int size) {
+		                 int cost, int size) {
 		  MMC alg(gr, lm);
 		  alg.findMinMean();
 		  check(alg.cycleMean() == static_cast<double>(length) / size,
 		  alg.findCycleMean();
 		  check(alg.cycleMean() == static_cast<double>(cost) / size,
 		        "Wrong cycle mean");
 		  alg.findCycle();
-		  check(alg.cycleLength() == length && alg.cycleArcNum() == size,
+		  check(alg.cycleCost() == cost && alg.cycleSize() == size,
 		        "Wrong path");
@@ -150,24 +150,24 @@
-		    // Karp
+		    // KarpMmc
 		    checkConcept< MmcClassConcept<GR, int>,
-		                  Karp<GR, concepts::ReadMap<GR::Arc, int> > >();
+		                  KarpMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
 		    checkConcept< MmcClassConcept<GR, float>,
-		                  Karp<GR, concepts::ReadMap<GR::Arc, float> > >();
+		                  KarpMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
-		    // HartmannOrlin
+		    // HartmannOrlinMmc
 		    checkConcept< MmcClassConcept<GR, int>,
-		                  HartmannOrlin<GR, concepts::ReadMap<GR::Arc, int> > >();
+		                  HartmannOrlinMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
 		    checkConcept< MmcClassConcept<GR, float>,
-		                  HartmannOrlin<GR, concepts::ReadMap<GR::Arc, float> > >();
+		                  HartmannOrlinMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
-		    // Howard
+		    // HowardMmc
 		    checkConcept< MmcClassConcept<GR, int>,
-		                  Howard<GR, concepts::ReadMap<GR::Arc, int> > >();
+		                  HowardMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
 		    checkConcept< MmcClassConcept<GR, float>,
-		                  Howard<GR, concepts::ReadMap<GR::Arc, float> > >();
+		                  HowardMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
 		    if (IsSameType<Howard<GR, concepts::ReadMap<GR::Arc, int> >::LargeValue,
 		          long_int>::result == 0) check(false, "Wrong LargeValue type");
 		    if (IsSameType<Howard<GR, concepts::ReadMap<GR::Arc, float> >::LargeValue,
 		          double>::result == 0) check(false, "Wrong LargeValue type");
 		    check((IsSameType<HowardMmc<GR, concepts::ReadMap<GR::Arc, int> >
 		           ::LargeCost, long_int>::result == 1), "Wrong LargeCost type");
 		    check((IsSameType<HowardMmc<GR, concepts::ReadMap<GR::Arc, float> >
 		           ::LargeCost, double>::result == 1), "Wrong LargeCost type");
+		  }
@@ -196,18 +196,18 @@
 		    // Karp
 		    checkMmcAlg<Karp<GR, IntArcMap> >(gr, l1, c1,  6, 3);
 		    checkMmcAlg<Karp<GR, IntArcMap> >(gr, l2, c2,  5, 2);
 		    checkMmcAlg<Karp<GR, IntArcMap> >(gr, l3, c3,  0, 1);
 		    checkMmcAlg<Karp<GR, IntArcMap> >(gr, l4, c4, -1, 1);
 		    checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l1, c1,  6, 3);
 		    checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l2, c2,  5, 2);
 		    checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);
 		    checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
 		    // HartmannOrlin
 		    checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l1, c1,  6, 3);
 		    checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l2, c2,  5, 2);
 		    checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l3, c3,  0, 1);
 		    checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l4, c4, -1, 1);
 		    checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l1, c1,  6, 3);
 		    checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l2, c2,  5, 2);
 		    checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);
 		    checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
 		    // Howard
 		    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l1, c1,  6, 3);
 		    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l2, c2,  5, 2);
 		    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l3, c3,  0, 1);
 		    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l4, c4, -1, 1);
 		    checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l1, c1,  6, 3);
 		    checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l2, c2,  5, 2);
 		    checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);
 		    checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
+		  }

0 comments (0 inline)

RhodeCode

Login to your account