# Changes in /[942:2b6bffe0e7e8:943:a1fd7008a052] in lemon-1.2

Ignore:
Files:
7 edited

### Legend:

Unmodified
Removed

 r553 copyright/license. Copyright (C) 2003-2009 Egervary Jeno Kombinatorikus Optimalizalasi Copyright (C) 2003-2010 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport (Egervary Combinatorial Optimization Research Group, EGRES).

• ## doc/groups.dox

 r877 /** @defgroup matrices Matrices @ingroup datas \brief Two dimensional data storages implemented in LEMON. This group contains two dimensional data storages implemented in LEMON. */ /** @defgroup auxdat Auxiliary Data Structures @ingroup datas LEMON contains three algorithms for solving the minimum mean cycle problem: - \ref Karp "Karp"'s original algorithm \ref amo93networkflows, - \ref KarpMmc Karp's original algorithm \ref amo93networkflows, \ref dasdan98minmeancycle. - \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved version of Karp's algorithm \ref dasdan98minmeancycle. - \ref Howard "Howard"'s policy iteration algorithm - \ref HowardMmc Howard's policy iteration algorithm \ref dasdan98minmeancycle. In practice, the Howard algorithm proved to be by far the most efficient one, though the best known theoretical bound on its running time is exponential. Both Karp and HartmannOrlin algorithms run in time O(ne) and use space O(n2+e), but the latter one is typically faster due to the applied early termination scheme. In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the most efficient one, though the best known theoretical bound on its running time is exponential. Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms run in time O(ne) and use space O(n2+e), but the latter one is typically faster due to the applied early termination scheme. */
• ## lemon/arg_parser.h

 r877 ///Exception used by ArgParser ///Exception used by ArgParser. /// class ArgParserException : public Exception { public: /// Reasons for failure /// Reasons for failure. /// enum Reason { HELP,         /// --help option was given UNKNOWN_OPT,  /// Unknown option was given INVALID_OPT   /// Invalid combination of options HELP,         ///< --help option was given. UNKNOWN_OPT,  ///< Unknown option was given. INVALID_OPT   ///< Invalid combination of options. };
• ## lemon/bellman_ford.h

 r877 #include #include #include #include namespace lemon { /// \brief Default operation traits for the BellmanFord algorithm class. /// \brief Default OperationTraits for the BellmanFord algorithm class. /// /// This operation traits class defines all computational operations /// If the numeric type does not have infinity value, then the maximum /// value is used as extremal infinity value. /// /// \see BellmanFordToleranceOperationTraits template < typename V, bool has_inf = std::numeric_limits::has_infinity> struct BellmanFordDefaultOperationTraits { /// \brief Value type for the algorithm. /// \e typedef V Value; /// \brief Gives back the zero value of the type. static bool less(const Value& left, const Value& right) { return left < right; } }; /// \brief Operation traits for the BellmanFord algorithm class /// using tolerance. /// /// This operation traits class defines all computational operations /// and constants that are used in the Bellman-Ford algorithm. /// The only difference between this implementation and /// \ref BellmanFordDefaultOperationTraits is that this class uses /// the \ref Tolerance "tolerance technique" in its \ref less() /// function. /// /// \tparam V The value type. /// \tparam eps The epsilon value for the \ref less() function. /// By default, it is the epsilon value used by \ref Tolerance /// "Tolerance". /// /// \see BellmanFordDefaultOperationTraits #ifdef DOXYGEN template #else template < typename V, V eps = Tolerance::def_epsilon> #endif struct BellmanFordToleranceOperationTraits { /// \brief Value type for the algorithm. typedef V Value; /// \brief Gives back the zero value of the type. static Value zero() { return static_cast(0); } /// \brief Gives back the positive infinity value of the type. static Value infinity() { return std::numeric_limits::infinity(); } /// \brief Gives back the sum of the given two elements. static Value plus(const Value& left, const Value& right) { return left + right; } /// \brief Gives back \c true only if the first value is less than /// the second. static bool less(const Value& left, const Value& right) { return left + eps < right; } }; /// It defines the used operations and the infinity value for the /// given \c Value type. /// \see BellmanFordDefaultOperationTraits, /// BellmanFordToleranceOperationTraits /// \see BellmanFordDefaultOperationTraits typedef BellmanFordDefaultOperationTraits OperationTraits; /// It defines the used operations and the infinity value for the /// given \c Value type. /// \see BellmanFordDefaultOperationTraits, /// BellmanFordToleranceOperationTraits /// \see BellmanFordDefaultOperationTraits typedef BellmanFordDefaultOperationTraits OperationTraits;
• ## lemon/hartmann_orlin_mmc.h

 r877 /// \tparam GR The type of the digraph. /// \tparam CM The type of the cost map. /// It must conform to the \ref concepts::Rea_data "Rea_data" concept. /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. #ifdef DOXYGEN template /// a directed cycle of minimum mean cost in a digraph /// \ref amo93networkflows, \ref dasdan98minmeancycle. /// It is an improved version of \ref Karp "Karp"'s original algorithm, /// It is an improved version of \ref KarpMmc "Karp"'s original algorithm, /// it applies an efficient early termination scheme. /// It runs in time O(ne) and uses space O(n2+e).
• ## test/bellman_ford_test.cc

 r877 ::SetDistMap > ::SetOperationTraits > ::SetOperationTraits > ::Create bf_test(gr,length);
Note: See TracChangeset for help on using the changeset viewer.