lemon: comparison lemon/howard.h

equal deleted inserted replaced

-:db135d96ebc8
+:f3d6f5830730
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */
-#ifndef LEMON_MIN_MEAN_CYCLE_H
+#ifndef LEMON_HOWARD_H
-#define LEMON_MIN_MEAN_CYCLE_H
+#define LEMON_HOWARD_H
 /// \ingroup shortest_path
 ///
 /// \file
 /// \brief Howard's algorithm for finding a minimum mean cycle.
 #include <lemon/tolerance.h>
 #include <lemon/connectivity.h>
 namespace lemon {
-/// \brief Default traits class of MinMeanCycle class.
+/// \brief Default traits class of Howard class.
 ///
-/// Default traits class of MinMeanCycle class.
+/// Default traits class of Howard class.
 /// \tparam GR The type of the digraph.
 /// \tparam LEN The type of the length map.
 /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 #ifdef DOXYGEN
 template <typename GR, typename LEN>
 #else
 template <typename GR, typename LEN,
 bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
 #endif
-struct MinMeanCycleDefaultTraits
+struct HowardDefaultTraits
 {
 /// The type of the digraph
 typedef GR Digraph;
 /// The type of the length map
 typedef LEN LengthMap;
 typedef lemon::Path<Digraph> Path;
 };
 // Default traits class for integer value types
 template <typename GR, typename LEN>
-struct MinMeanCycleDefaultTraits<GR, LEN, true>
+struct HowardDefaultTraits<GR, LEN, true>
 {
 typedef GR Digraph;
 typedef LEN LengthMap;
 typedef typename LengthMap::Value Value;
 #ifdef LEMON_HAVE_LONG_LONG
 /// @{
 /// \brief Implementation of Howard's algorithm for finding a minimum
 /// mean cycle.
 ///
-/// \ref MinMeanCycle implements Howard's algorithm for finding a
+/// This class implements Howard's policy iteration algorithm for finding
-/// directed cycle of minimum mean length (cost) in a digraph.
+/// a directed cycle of minimum mean length (cost) in a digraph.
 ///
 /// \tparam GR The type of the digraph the algorithm runs on.
 /// \tparam LEN The type of the length map. The default
 /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 #ifdef DOXYGEN
 template <typename GR, typename LEN, typename TR>
 #else
 template < typename GR,
 typename LEN = typename GR::template ArcMap<int>,
-typename TR = MinMeanCycleDefaultTraits<GR, LEN> >
+typename TR = HowardDefaultTraits<GR, LEN> >
 #endif
-class MinMeanCycle
+class Howard
 {
 public:
 /// The type of the digraph
 typedef typename TR::Digraph Digraph;
 typedef typename TR::Value Value;
 /// \brief The large value type
 ///
 /// The large value type used for internal computations.
-/// Using the \ref MinMeanCycleDefaultTraits "default traits class",
+/// Using the \ref HowardDefaultTraits "default traits class",
 /// it is \c long \c long if the \c Value type is integer,
 /// otherwise it is \c double.
 typedef typename TR::LargeValue LargeValue;
 /// The tolerance type
 typedef typename TR::Tolerance Tolerance;
 /// \brief The path type of the found cycles
 ///
 /// The path type of the found cycles.
-/// Using the \ref MinMeanCycleDefaultTraits "default traits class",
+/// Using the \ref HowardDefaultTraits "default traits class",
 /// it is \ref lemon::Path "Path<Digraph>".
 typedef typename TR::Path Path;
-/// The \ref MinMeanCycleDefaultTraits "traits class" of the algorithm
+/// The \ref HowardDefaultTraits "traits class" of the algorithm
 typedef TR Traits;
 private:
 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 ///
 /// \ref named-templ-param "Named parameter" for setting \c LargeValue
 /// type. It is used for internal computations in the algorithm.
 template <typename T>
 struct SetLargeValue
-: public MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > {
+: public Howard<GR, LEN, SetLargeValueTraits<T> > {
-typedef MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > Create;
+typedef Howard<GR, LEN, SetLargeValueTraits<T> > Create;
 };
 template <typename T>
 struct SetPathTraits : public Traits {
 typedef T Path;
 /// type of the found cycles.
 /// It must conform to the \ref lemon::concepts::Path "Path" concept
 /// and it must have an \c addBack() function.
 template <typename T>
 struct SetPath
-: public MinMeanCycle<GR, LEN, SetPathTraits<T> > {
+: public Howard<GR, LEN, SetPathTraits<T> > {
-typedef MinMeanCycle<GR, LEN, SetPathTraits<T> > Create;
+typedef Howard<GR, LEN, SetPathTraits<T> > Create;
 };
 /// @}
 public:
 ///
 /// The constructor of the class.
 ///
 /// \param digraph The digraph the algorithm runs on.
 /// \param length The lengths (costs) of the arcs.
-MinMeanCycle( const Digraph &digraph,
+Howard( const Digraph &digraph,
 const LengthMap &length ) :
 _gr(digraph), _length(length), _cycle_path(NULL), _local_path(false),
 _policy(digraph), _reached(digraph), _level(digraph), _dist(digraph),
 _comp(digraph), _in_arcs(digraph)
 {}
 /// Destructor.
-~MinMeanCycle() {
+~Howard() {
 if (_local_path) delete _cycle_path;
 }
 /// \brief Set the path structure for storing the found cycle.
 ///
 ///
 /// \note The algorithm calls only the \ref lemon::Path::addBack()
 /// "addBack()" function of the given path structure.
 ///
 /// \return <tt>(*this)</tt>
-MinMeanCycle& cycle(Path &path) {
+Howard& cycle(Path &path) {
 if (_local_path) {
 delete _cycle_path;
 _local_path = false;
 }
 _cycle_path = &path;
 }
 }
 return improved;
 }
-}; //class MinMeanCycle
+}; //class Howard
 ///@}
 } //namespace lemon
-#endif //LEMON_MIN_MEAN_CYCLE_H
+#endif //LEMON_HOWARD_H

changeset 811	1fac515a59c1
parent 810	93cd93e82f9b
child 814	11c946fa8d13