COIN-OR::LEMON - Graph Library

Changeset 811:1fac515a59c1 in lemon


Ignore:
Timestamp:
08/10/09 14:50:57 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Rename MinMeanCycle? to Howard (#179)

Files:
2 edited
1 moved

Legend:

Unmodified
Added
Removed
  • lemon/Makefile.am

    r805 r811  
    8484        lemon/graph_to_eps.h \
    8585        lemon/grid_graph.h \
     86        lemon/howard.h \
    8687        lemon/hypercube_graph.h \
    8788        lemon/kruskal.h \
     
    9899        lemon/math.h \
    99100        lemon/min_cost_arborescence.h \
    100         lemon/min_mean_cycle.h \
    101101        lemon/nauty_reader.h \
    102102        lemon/network_simplex.h \
  • lemon/howard.h

    r810 r811  
    1717 */
    1818
    19 #ifndef LEMON_MIN_MEAN_CYCLE_H
    20 #define LEMON_MIN_MEAN_CYCLE_H
     19#ifndef LEMON_HOWARD_H
     20#define LEMON_HOWARD_H
    2121
    2222/// \ingroup shortest_path
     
    3434namespace lemon {
    3535
    36   /// \brief Default traits class of MinMeanCycle class.
     36  /// \brief Default traits class of Howard class.
    3737  ///
    38   /// Default traits class of MinMeanCycle class.
     38  /// Default traits class of Howard class.
    3939  /// \tparam GR The type of the digraph.
    4040  /// \tparam LEN The type of the length map.
     
    4646    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
    4747#endif
    48   struct MinMeanCycleDefaultTraits
     48  struct HowardDefaultTraits
    4949  {
    5050    /// The type of the digraph
     
    7676  // Default traits class for integer value types
    7777  template <typename GR, typename LEN>
    78   struct MinMeanCycleDefaultTraits<GR, LEN, true>
     78  struct HowardDefaultTraits<GR, LEN, true>
    7979  {
    8080    typedef GR Digraph;
     
    9797  /// mean cycle.
    9898  ///
    99   /// \ref MinMeanCycle implements Howard's algorithm for finding a
    100   /// directed cycle of minimum mean length (cost) in a digraph.
     99  /// This class implements Howard's policy iteration algorithm for finding
     100  /// a directed cycle of minimum mean length (cost) in a digraph.
    101101  ///
    102102  /// \tparam GR The type of the digraph the algorithm runs on.
     
    108108  template < typename GR,
    109109             typename LEN = typename GR::template ArcMap<int>,
    110              typename TR = MinMeanCycleDefaultTraits<GR, LEN> >
     110             typename TR = HowardDefaultTraits<GR, LEN> >
    111111#endif
    112   class MinMeanCycle
     112  class Howard
    113113  {
    114114  public:
     
    124124    ///
    125125    /// The large value type used for internal computations.
    126     /// Using the \ref MinMeanCycleDefaultTraits "default traits class",
     126    /// Using the \ref HowardDefaultTraits "default traits class",
    127127    /// it is \c long \c long if the \c Value type is integer,
    128128    /// otherwise it is \c double.
     
    135135    ///
    136136    /// The path type of the found cycles.
    137     /// Using the \ref MinMeanCycleDefaultTraits "default traits class",
     137    /// Using the \ref HowardDefaultTraits "default traits class",
    138138    /// it is \ref lemon::Path "Path<Digraph>".
    139139    typedef typename TR::Path Path;
    140140
    141     /// The \ref MinMeanCycleDefaultTraits "traits class" of the algorithm
     141    /// The \ref HowardDefaultTraits "traits class" of the algorithm
    142142    typedef TR Traits;
    143143
     
    197197    template <typename T>
    198198    struct SetLargeValue
    199       : public MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > {
    200       typedef MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > Create;
     199      : public Howard<GR, LEN, SetLargeValueTraits<T> > {
     200      typedef Howard<GR, LEN, SetLargeValueTraits<T> > Create;
    201201    };
    202202
     
    215215    template <typename T>
    216216    struct SetPath
    217       : public MinMeanCycle<GR, LEN, SetPathTraits<T> > {
    218       typedef MinMeanCycle<GR, LEN, SetPathTraits<T> > Create;
     217      : public Howard<GR, LEN, SetPathTraits<T> > {
     218      typedef Howard<GR, LEN, SetPathTraits<T> > Create;
    219219    };
    220220   
     
    229229    /// \param digraph The digraph the algorithm runs on.
    230230    /// \param length The lengths (costs) of the arcs.
    231     MinMeanCycle( const Digraph &digraph,
    232                   const LengthMap &length ) :
     231    Howard( const Digraph &digraph,
     232            const LengthMap &length ) :
    233233      _gr(digraph), _length(length), _cycle_path(NULL), _local_path(false),
    234234      _policy(digraph), _reached(digraph), _level(digraph), _dist(digraph),
     
    237237
    238238    /// Destructor.
    239     ~MinMeanCycle() {
     239    ~Howard() {
    240240      if (_local_path) delete _cycle_path;
    241241    }
     
    255255    ///
    256256    /// \return <tt>(*this)</tt>
    257     MinMeanCycle& cycle(Path &path) {
     257    Howard& cycle(Path &path) {
    258258      if (_local_path) {
    259259        delete _cycle_path;
     
    560560    }
    561561
    562   }; //class MinMeanCycle
     562  }; //class Howard
    563563
    564564  ///@}
     
    566566} //namespace lemon
    567567
    568 #endif //LEMON_MIN_MEAN_CYCLE_H
     568#endif //LEMON_HOWARD_H
  • test/min_mean_cycle_test.cc

    r810 r811  
    2222#include <lemon/smart_graph.h>
    2323#include <lemon/lgf_reader.h>
    24 #include <lemon/min_mean_cycle.h>
     24#include <lemon/howard.h>
    2525#include <lemon/path.h>
    2626#include <lemon/concepts/digraph.h>
     
    142142  {
    143143    typedef concepts::Digraph GR;
    144     typedef MinMeanCycle<GR, concepts::ReadMap<GR::Arc, int> > IntMmcAlg;
    145     typedef MinMeanCycle<GR, concepts::ReadMap<GR::Arc, float> > FloatMmcAlg;
     144    typedef Howard<GR, concepts::ReadMap<GR::Arc, int> > IntMmcAlg;
     145    typedef Howard<GR, concepts::ReadMap<GR::Arc, float> > FloatMmcAlg;
    146146   
    147147    checkConcept<MmcClassConcept<GR, int>, IntMmcAlg>();
     
    175175      run();
    176176
    177     checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l1, c1,  6, 3);
    178     checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l2, c2,  5, 2);
    179     checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l3, c3,  0, 1);
    180     checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l4, c4, -1, 1);
     177    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l1, c1,  6, 3);
     178    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l2, c2,  5, 2);
     179    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l3, c3,  0, 1);
     180    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l4, c4, -1, 1);
    181181  }
    182182
Note: See TracChangeset for help on using the changeset viewer.