r879:38213abd2911
Thu, 18 Mar 2010 00:30:25
[Not Reviewed]
0 comments (0 inline)
0
4
0
| 1 | 1 |
LEMON code without an explicit copyright notice is covered by the following |
| 2 | 2 |
copyright/license. |
| 3 | 3 |
|
| 4 |
Copyright (C) 2003- |
|
| 4 |
Copyright (C) 2003-2010 Egervary Jeno Kombinatorikus Optimalizalasi |
|
| 5 | 5 |
Kutatocsoport (Egervary Combinatorial Optimization Research Group, |
| 6 | 6 |
EGRES). |
| 7 | 7 |
|
| 8 | 8 |
=========================================================================== |
| 9 | 9 |
Boost Software License, Version 1.0 |
| 10 | 10 |
=========================================================================== |
| ... | ... |
@@ -260,20 +260,12 @@ |
| 260 | 260 |
used easily in such algorithms. |
| 261 | 261 |
|
| 262 | 262 |
\sa \ref concepts::Heap "Heap concept" |
| 263 | 263 |
*/ |
| 264 | 264 |
|
| 265 | 265 |
/** |
| 266 |
@defgroup matrices Matrices |
|
| 267 |
@ingroup datas |
|
| 268 |
\brief Two dimensional data storages implemented in LEMON. |
|
| 269 |
|
|
| 270 |
This group contains two dimensional data storages implemented in LEMON. |
|
| 271 |
*/ |
|
| 272 |
|
|
| 273 |
/** |
|
| 274 | 266 |
@defgroup auxdat Auxiliary Data Structures |
| 275 | 267 |
@ingroup datas |
| 276 | 268 |
\brief Auxiliary data structures implemented in LEMON. |
| 277 | 269 |
|
| 278 | 270 |
This group contains some data structures implemented in LEMON in |
| 279 | 271 |
order to make it easier to implement combinatorial algorithms. |
| ... | ... |
@@ -469,25 +461,25 @@ |
| 469 | 461 |
length. For an arbitrary length function, the negative of the minimum |
| 470 | 462 |
cycle mean is the smallest \f$\epsilon\f$ value so that increasing the |
| 471 | 463 |
arc lengths uniformly by \f$\epsilon\f$ results in a conservative length |
| 472 | 464 |
function. |
| 473 | 465 |
|
| 474 | 466 |
LEMON contains three algorithms for solving the minimum mean cycle problem: |
| 475 |
- \ref |
|
| 467 |
- \ref KarpMmc Karp's original algorithm \ref amo93networkflows, |
|
| 476 | 468 |
\ref dasdan98minmeancycle. |
| 477 |
- \ref |
|
| 469 |
- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved |
|
| 478 | 470 |
version of Karp's algorithm \ref dasdan98minmeancycle. |
| 479 |
- \ref |
|
| 471 |
- \ref HowardMmc Howard's policy iteration algorithm |
|
| 480 | 472 |
\ref dasdan98minmeancycle. |
| 481 | 473 |
|
| 482 |
In practice, the Howard algorithm proved to be by far the most efficient |
|
| 483 |
one, though the best known theoretical bound on its running time is |
|
| 484 |
exponential. |
|
| 485 |
Both Karp and HartmannOrlin algorithms run in time O(ne) and use space |
|
| 486 |
O(n<sup>2</sup>+e), but the latter one is typically faster due to the |
|
| 487 |
applied early termination scheme. |
|
| 474 |
In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the |
|
| 475 |
most efficient one, though the best known theoretical bound on its running |
|
| 476 |
time is exponential. |
|
| 477 |
Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms |
|
| 478 |
run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is |
|
| 479 |
typically faster due to the applied early termination scheme. |
|
| 488 | 480 |
*/ |
| 489 | 481 |
|
| 490 | 482 |
/** |
| 491 | 483 |
@defgroup matching Matching Algorithms |
| 492 | 484 |
@ingroup algs |
| 493 | 485 |
\brief Algorithms for finding matchings in graphs and bipartite graphs. |
| ... | ... |
@@ -32,18 +32,25 @@ |
| 32 | 32 |
///\file |
| 33 | 33 |
///\brief A tool to parse command line arguments. |
| 34 | 34 |
|
| 35 | 35 |
namespace lemon {
|
| 36 | 36 |
|
| 37 | 37 |
///Exception used by ArgParser |
| 38 |
|
|
| 39 |
///Exception used by ArgParser. |
|
| 40 |
/// |
|
| 38 | 41 |
class ArgParserException : public Exception {
|
| 39 | 42 |
public: |
| 43 |
/// Reasons for failure |
|
| 44 |
|
|
| 45 |
/// Reasons for failure. |
|
| 46 |
/// |
|
| 40 | 47 |
enum Reason {
|
| 41 |
HELP, /// <tt>--help</tt> option was given |
|
| 42 |
UNKNOWN_OPT, /// Unknown option was given |
|
| 43 |
|
|
| 48 |
HELP, ///< <tt>--help</tt> option was given. |
|
| 49 |
UNKNOWN_OPT, ///< Unknown option was given. |
|
| 50 |
INVALID_OPT ///< Invalid combination of options. |
|
| 44 | 51 |
}; |
| 45 | 52 |
|
| 46 | 53 |
private: |
| 47 | 54 |
Reason _reason; |
| 48 | 55 |
|
| 49 | 56 |
public: |
| ... | ... |
@@ -35,13 +35,13 @@ |
| 35 | 35 |
|
| 36 | 36 |
/// \brief Default traits class of HartmannOrlinMmc class. |
| 37 | 37 |
/// |
| 38 | 38 |
/// Default traits class of HartmannOrlinMmc class. |
| 39 | 39 |
/// \tparam GR The type of the digraph. |
| 40 | 40 |
/// \tparam CM The type of the cost map. |
| 41 |
/// It must conform to the \ref concepts:: |
|
| 41 |
/// It must conform to the \ref concepts::ReadMap "ReadMap" concept. |
|
| 42 | 42 |
#ifdef DOXYGEN |
| 43 | 43 |
template <typename GR, typename CM> |
| 44 | 44 |
#else |
| 45 | 45 |
template <typename GR, typename CM, |
| 46 | 46 |
bool integer = std::numeric_limits<typename CM::Value>::is_integer> |
| 47 | 47 |
#endif |
| ... | ... |
@@ -96,13 +96,13 @@ |
| 96 | 96 |
/// \brief Implementation of the Hartmann-Orlin algorithm for finding |
| 97 | 97 |
/// a minimum mean cycle. |
| 98 | 98 |
/// |
| 99 | 99 |
/// This class implements the Hartmann-Orlin algorithm for finding |
| 100 | 100 |
/// a directed cycle of minimum mean cost in a digraph |
| 101 | 101 |
/// \ref amo93networkflows, \ref dasdan98minmeancycle. |
| 102 |
/// It is an improved version of \ref |
|
| 102 |
/// It is an improved version of \ref KarpMmc "Karp"'s original algorithm, |
|
| 103 | 103 |
/// it applies an efficient early termination scheme. |
| 104 | 104 |
/// It runs in time O(ne) and uses space O(n<sup>2</sup>+e). |
| 105 | 105 |
/// |
| 106 | 106 |
/// \tparam GR The type of the digraph the algorithm runs on. |
| 107 | 107 |
/// \tparam CM The type of the cost map. The default |
| 108 | 108 |
/// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". |
0 comments (0 inline)