lemon/howard.h
changeset 766 97744b6dabf8
parent 763 93cd93e82f9b
child 767 11c946fa8d13
equal deleted inserted replaced
5:db135d96ebc8 0:f3d6f5830730
    14  * express or implied, and with no claim as to its suitability for any
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    15  * purpose.
    16  *
    16  *
    17  */
    17  */
    18 
    18 
    19 #ifndef LEMON_MIN_MEAN_CYCLE_H
    19 #ifndef LEMON_HOWARD_H
    20 #define LEMON_MIN_MEAN_CYCLE_H
    20 #define LEMON_HOWARD_H
    21 
    21 
    22 /// \ingroup shortest_path
    22 /// \ingroup shortest_path
    23 ///
    23 ///
    24 /// \file
    24 /// \file
    25 /// \brief Howard's algorithm for finding a minimum mean cycle.
    25 /// \brief Howard's algorithm for finding a minimum mean cycle.
    31 #include <lemon/tolerance.h>
    31 #include <lemon/tolerance.h>
    32 #include <lemon/connectivity.h>
    32 #include <lemon/connectivity.h>
    33 
    33 
    34 namespace lemon {
    34 namespace lemon {
    35 
    35 
    36   /// \brief Default traits class of MinMeanCycle class.
    36   /// \brief Default traits class of Howard class.
    37   ///
    37   ///
    38   /// Default traits class of MinMeanCycle class.
    38   /// Default traits class of Howard class.
    39   /// \tparam GR The type of the digraph.
    39   /// \tparam GR The type of the digraph.
    40   /// \tparam LEN The type of the length map.
    40   /// \tparam LEN The type of the length map.
    41   /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    41   /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    42 #ifdef DOXYGEN
    42 #ifdef DOXYGEN
    43   template <typename GR, typename LEN>
    43   template <typename GR, typename LEN>
    44 #else
    44 #else
    45   template <typename GR, typename LEN,
    45   template <typename GR, typename LEN,
    46     bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
    46     bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
    47 #endif
    47 #endif
    48   struct MinMeanCycleDefaultTraits
    48   struct HowardDefaultTraits
    49   {
    49   {
    50     /// The type of the digraph
    50     /// The type of the digraph
    51     typedef GR Digraph;
    51     typedef GR Digraph;
    52     /// The type of the length map
    52     /// The type of the length map
    53     typedef LEN LengthMap;
    53     typedef LEN LengthMap;
    73     typedef lemon::Path<Digraph> Path;
    73     typedef lemon::Path<Digraph> Path;
    74   };
    74   };
    75 
    75 
    76   // Default traits class for integer value types
    76   // Default traits class for integer value types
    77   template <typename GR, typename LEN>
    77   template <typename GR, typename LEN>
    78   struct MinMeanCycleDefaultTraits<GR, LEN, true>
    78   struct HowardDefaultTraits<GR, LEN, true>
    79   {
    79   {
    80     typedef GR Digraph;
    80     typedef GR Digraph;
    81     typedef LEN LengthMap;
    81     typedef LEN LengthMap;
    82     typedef typename LengthMap::Value Value;
    82     typedef typename LengthMap::Value Value;
    83 #ifdef LEMON_HAVE_LONG_LONG
    83 #ifdef LEMON_HAVE_LONG_LONG
    94   /// @{
    94   /// @{
    95 
    95 
    96   /// \brief Implementation of Howard's algorithm for finding a minimum
    96   /// \brief Implementation of Howard's algorithm for finding a minimum
    97   /// mean cycle.
    97   /// mean cycle.
    98   ///
    98   ///
    99   /// \ref MinMeanCycle implements Howard's algorithm for finding a
    99   /// This class implements Howard's policy iteration algorithm for finding
   100   /// directed cycle of minimum mean length (cost) in a digraph.
   100   /// a directed cycle of minimum mean length (cost) in a digraph.
   101   ///
   101   ///
   102   /// \tparam GR The type of the digraph the algorithm runs on.
   102   /// \tparam GR The type of the digraph the algorithm runs on.
   103   /// \tparam LEN The type of the length map. The default
   103   /// \tparam LEN The type of the length map. The default
   104   /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
   104   /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
   105 #ifdef DOXYGEN
   105 #ifdef DOXYGEN
   106   template <typename GR, typename LEN, typename TR>
   106   template <typename GR, typename LEN, typename TR>
   107 #else
   107 #else
   108   template < typename GR,
   108   template < typename GR,
   109              typename LEN = typename GR::template ArcMap<int>,
   109              typename LEN = typename GR::template ArcMap<int>,
   110              typename TR = MinMeanCycleDefaultTraits<GR, LEN> >
   110              typename TR = HowardDefaultTraits<GR, LEN> >
   111 #endif
   111 #endif
   112   class MinMeanCycle
   112   class Howard
   113   {
   113   {
   114   public:
   114   public:
   115   
   115   
   116     /// The type of the digraph
   116     /// The type of the digraph
   117     typedef typename TR::Digraph Digraph;
   117     typedef typename TR::Digraph Digraph;
   121     typedef typename TR::Value Value;
   121     typedef typename TR::Value Value;
   122 
   122 
   123     /// \brief The large value type
   123     /// \brief The large value type
   124     ///
   124     ///
   125     /// The large value type used for internal computations.
   125     /// The large value type used for internal computations.
   126     /// Using the \ref MinMeanCycleDefaultTraits "default traits class",
   126     /// Using the \ref HowardDefaultTraits "default traits class",
   127     /// it is \c long \c long if the \c Value type is integer,
   127     /// it is \c long \c long if the \c Value type is integer,
   128     /// otherwise it is \c double.
   128     /// otherwise it is \c double.
   129     typedef typename TR::LargeValue LargeValue;
   129     typedef typename TR::LargeValue LargeValue;
   130 
   130 
   131     /// The tolerance type
   131     /// The tolerance type
   132     typedef typename TR::Tolerance Tolerance;
   132     typedef typename TR::Tolerance Tolerance;
   133 
   133 
   134     /// \brief The path type of the found cycles
   134     /// \brief The path type of the found cycles
   135     ///
   135     ///
   136     /// The path type of the found cycles.
   136     /// The path type of the found cycles.
   137     /// Using the \ref MinMeanCycleDefaultTraits "default traits class",
   137     /// Using the \ref HowardDefaultTraits "default traits class",
   138     /// it is \ref lemon::Path "Path<Digraph>".
   138     /// it is \ref lemon::Path "Path<Digraph>".
   139     typedef typename TR::Path Path;
   139     typedef typename TR::Path Path;
   140 
   140 
   141     /// The \ref MinMeanCycleDefaultTraits "traits class" of the algorithm
   141     /// The \ref HowardDefaultTraits "traits class" of the algorithm
   142     typedef TR Traits;
   142     typedef TR Traits;
   143 
   143 
   144   private:
   144   private:
   145 
   145 
   146     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   146     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   194     ///
   194     ///
   195     /// \ref named-templ-param "Named parameter" for setting \c LargeValue
   195     /// \ref named-templ-param "Named parameter" for setting \c LargeValue
   196     /// type. It is used for internal computations in the algorithm.
   196     /// type. It is used for internal computations in the algorithm.
   197     template <typename T>
   197     template <typename T>
   198     struct SetLargeValue
   198     struct SetLargeValue
   199       : public MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > {
   199       : public Howard<GR, LEN, SetLargeValueTraits<T> > {
   200       typedef MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > Create;
   200       typedef Howard<GR, LEN, SetLargeValueTraits<T> > Create;
   201     };
   201     };
   202 
   202 
   203     template <typename T>
   203     template <typename T>
   204     struct SetPathTraits : public Traits {
   204     struct SetPathTraits : public Traits {
   205       typedef T Path;
   205       typedef T Path;
   212     /// type of the found cycles.
   212     /// type of the found cycles.
   213     /// It must conform to the \ref lemon::concepts::Path "Path" concept
   213     /// It must conform to the \ref lemon::concepts::Path "Path" concept
   214     /// and it must have an \c addBack() function.
   214     /// and it must have an \c addBack() function.
   215     template <typename T>
   215     template <typename T>
   216     struct SetPath
   216     struct SetPath
   217       : public MinMeanCycle<GR, LEN, SetPathTraits<T> > {
   217       : public Howard<GR, LEN, SetPathTraits<T> > {
   218       typedef MinMeanCycle<GR, LEN, SetPathTraits<T> > Create;
   218       typedef Howard<GR, LEN, SetPathTraits<T> > Create;
   219     };
   219     };
   220     
   220     
   221     /// @}
   221     /// @}
   222 
   222 
   223   public:
   223   public:
   226     ///
   226     ///
   227     /// The constructor of the class.
   227     /// The constructor of the class.
   228     ///
   228     ///
   229     /// \param digraph The digraph the algorithm runs on.
   229     /// \param digraph The digraph the algorithm runs on.
   230     /// \param length The lengths (costs) of the arcs.
   230     /// \param length The lengths (costs) of the arcs.
   231     MinMeanCycle( const Digraph &digraph,
   231     Howard( const Digraph &digraph,
   232                   const LengthMap &length ) :
   232             const LengthMap &length ) :
   233       _gr(digraph), _length(length), _cycle_path(NULL), _local_path(false),
   233       _gr(digraph), _length(length), _cycle_path(NULL), _local_path(false),
   234       _policy(digraph), _reached(digraph), _level(digraph), _dist(digraph),
   234       _policy(digraph), _reached(digraph), _level(digraph), _dist(digraph),
   235       _comp(digraph), _in_arcs(digraph)
   235       _comp(digraph), _in_arcs(digraph)
   236     {}
   236     {}
   237 
   237 
   238     /// Destructor.
   238     /// Destructor.
   239     ~MinMeanCycle() {
   239     ~Howard() {
   240       if (_local_path) delete _cycle_path;
   240       if (_local_path) delete _cycle_path;
   241     }
   241     }
   242 
   242 
   243     /// \brief Set the path structure for storing the found cycle.
   243     /// \brief Set the path structure for storing the found cycle.
   244     ///
   244     ///
   252     ///
   252     ///
   253     /// \note The algorithm calls only the \ref lemon::Path::addBack()
   253     /// \note The algorithm calls only the \ref lemon::Path::addBack()
   254     /// "addBack()" function of the given path structure.
   254     /// "addBack()" function of the given path structure.
   255     ///
   255     ///
   256     /// \return <tt>(*this)</tt>
   256     /// \return <tt>(*this)</tt>
   257     MinMeanCycle& cycle(Path &path) {
   257     Howard& cycle(Path &path) {
   258       if (_local_path) {
   258       if (_local_path) {
   259         delete _cycle_path;
   259         delete _cycle_path;
   260         _local_path = false;
   260         _local_path = false;
   261       }
   261       }
   262       _cycle_path = &path;
   262       _cycle_path = &path;
   557         }
   557         }
   558       }
   558       }
   559       return improved;
   559       return improved;
   560     }
   560     }
   561 
   561 
   562   }; //class MinMeanCycle
   562   }; //class Howard
   563 
   563 
   564   ///@}
   564   ///@}
   565 
   565 
   566 } //namespace lemon
   566 } //namespace lemon
   567 
   567 
   568 #endif //LEMON_MIN_MEAN_CYCLE_H
   568 #endif //LEMON_HOWARD_H