r1108:a1fd7008a052
Tue, 20 Dec 2011 18:15:38
[Not Reviewed]
0 comments (0 inline)
0
7
0
1
1
81
1
9
17
| 1 |
2010-03-19 Version 1.2 released |
|
| 2 |
|
|
| 3 |
This is major feature release |
|
| 4 |
|
|
| 5 |
* New algorithms |
|
| 6 |
* Bellman-Ford algorithm (#51) |
|
| 7 |
* Minimum mean cycle algorithms (#179) |
|
| 8 |
* Karp, Hartman-Orlin and Howard algorithms |
|
| 9 |
* New minimum cost flow algorithms (#180) |
|
| 10 |
* Cost Scaling algorithms |
|
| 11 |
* Capacity Scaling algorithm |
|
| 12 |
* Cycle-Canceling algorithms |
|
| 13 |
* Planarity related algorithms (#62) |
|
| 14 |
* Planarity checking algorithm |
|
| 15 |
* Planar embedding algorithm |
|
| 16 |
* Schnyder's planar drawing algorithm |
|
| 17 |
* Coloring planar graphs with five or six colors |
|
| 18 |
* Fractional matching algorithms (#314) |
|
| 19 |
* New data structures |
|
| 20 |
* StaticDigraph structure (#68) |
|
| 21 |
* Several new priority queue structures (#50, #301) |
|
| 22 |
* Fibonacci, Radix, Bucket, Pairing, Binomial |
|
| 23 |
D-ary and fourary heaps (#301) |
|
| 24 |
* Iterable map structures (#73) |
|
| 25 |
* Other new tools and functionality |
|
| 26 |
* Map utility functions (#320) |
|
| 27 |
* Reserve functions are added to ListGraph and SmartGraph (#311) |
|
| 28 |
* A resize() function is added to HypercubeGraph (#311) |
|
| 29 |
* A count() function is added to CrossRefMap (#302) |
|
| 30 |
* Support for multiple targets in Suurballe using fullInit() (#181) |
|
| 31 |
* Traits class and named parameters for Suurballe (#323) |
|
| 32 |
* Separate reset() and resetParams() functions in NetworkSimplex |
|
| 33 |
to handle graph changes (#327) |
|
| 34 |
* tolerance() functions are added to HaoOrlin (#306) |
|
| 35 |
* Implementation improvements |
|
| 36 |
* Improvements in weighted matching algorithms (#314) |
|
| 37 |
* Jumpstart initialization |
|
| 38 |
* ArcIt iteration is based on out-arc lists instead of in-arc lists |
|
| 39 |
in ListDigraph (#311) |
|
| 40 |
* Faster add row operation in CbcMip (#203) |
|
| 41 |
* Better implementation for split() in ListDigraph (#311) |
|
| 42 |
* ArgParser can also throw exception instead of exit(1) (#332) |
|
| 43 |
* Miscellaneous |
|
| 44 |
* A simple interactive bootstrap script |
|
| 45 |
* Doc improvements (#62,#180,#299,#302,#303,#304,#307,#311,#331,#315, |
|
| 46 |
#316,#319) |
|
| 47 |
* BibTeX references in the doc (#184) |
|
| 48 |
* Optionally use valgrind when running tests |
|
| 49 |
* Also check ReferenceMapTag in concept checks (#312) |
|
| 50 |
* dimacs-solver uses long long type by default. |
|
| 51 |
* Several bugfixes (compared to release 1.1): |
|
| 52 |
#295: Suppress MSVC warnings using pragmas |
|
| 53 |
----: Various CMAKE related improvements |
|
| 54 |
* Remove duplications from doc/CMakeLists.txt |
|
| 55 |
* Rename documentation install folder from 'docs' to 'html' |
|
| 56 |
* Add tools/CMakeLists.txt to the tarball |
|
| 57 |
* Generate and install LEMONConfig.cmake |
|
| 58 |
* Change the label of the html project in Visual Studio |
|
| 59 |
* Fix the check for the 'long long' type |
|
| 60 |
* Put the version string into config.h |
|
| 61 |
* Minor CMake improvements |
|
| 62 |
* Set the version to 'hg-tip' if everything fails |
|
| 63 |
#311: Add missing 'explicit' keywords |
|
| 64 |
#302: Fix the implementation and doc of CrossRefMap |
|
| 65 |
#308: Remove duplicate list_graph.h entry from source list |
|
| 66 |
#307: Bugfix in Preflow and Circulation |
|
| 67 |
#305: Bugfix and extension in the rename script |
|
| 68 |
#312: Also check ReferenceMapTag in concept checks |
|
| 69 |
#250: Bugfix in pathSource() and pathTarget() |
|
| 70 |
#321: Use pathCopy(from,to) instead of copyPath(to,from) |
|
| 71 |
#322: Distribure LEMONConfig.cmake.in |
|
| 72 |
#330: Bug fix in map_extender.h |
|
| 73 |
#336: Fix the date field comment of graphToEps() output |
|
| 74 |
#323: Bug fix in Suurballe |
|
| 75 |
#335: Fix clear() function in ExtendFindEnum |
|
| 76 |
#337: Use void* as the LPX object pointer |
|
| 77 |
#317: Fix (and improve) error message in mip_test.cc |
|
| 78 |
Remove unnecessary OsiCbc dependency |
|
| 79 |
#356: Allow multiple executions of weighted matching algorithms (#356) |
|
| 80 |
|
|
| 1 | 81 |
2009-05-13 Version 1.1 released |
| ... | ... |
@@ -74,3 +154,3 @@ |
| 74 | 154 |
#204: Compilation bug fixed in graph_to_eps.h with VS2005 |
| 75 |
#214,#215: windows.h should never be included by |
|
| 155 |
#214,#215: windows.h should never be included by LEMON headers |
|
| 76 | 156 |
#230: Build systems check the availability of 'long long' type |
| ... | ... |
@@ -265,10 +265,2 @@ |
| 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 |
| ... | ... |
@@ -474,15 +466,15 @@ |
| 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 |
*/ |
| ... | ... |
@@ -37,8 +37,15 @@ |
| 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 |
}; |
| ... | ... |
@@ -30,3 +30,2 @@ |
| 30 | 30 |
#include <lemon/maps.h> |
| 31 |
#include <lemon/tolerance.h> |
|
| 32 | 31 |
#include <lemon/path.h> |
| ... | ... |
@@ -37,3 +36,3 @@ |
| 37 | 36 |
|
| 38 |
/// \brief Default |
|
| 37 |
/// \brief Default OperationTraits for the BellmanFord algorithm class. |
|
| 39 | 38 |
/// |
| ... | ... |
@@ -44,4 +43,2 @@ |
| 44 | 43 |
/// value is used as extremal infinity value. |
| 45 |
/// |
|
| 46 |
/// \see BellmanFordToleranceOperationTraits |
|
| 47 | 44 |
template < |
| ... | ... |
@@ -50,3 +47,3 @@ |
| 50 | 47 |
struct BellmanFordDefaultOperationTraits {
|
| 51 |
/// \ |
|
| 48 |
/// \e |
|
| 52 | 49 |
typedef V Value; |
| ... | ... |
@@ -89,47 +86,2 @@ |
| 89 | 86 |
|
| 90 |
/// \brief Operation traits for the BellmanFord algorithm class |
|
| 91 |
/// using tolerance. |
|
| 92 |
/// |
|
| 93 |
/// This operation traits class defines all computational operations |
|
| 94 |
/// and constants that are used in the Bellman-Ford algorithm. |
|
| 95 |
/// The only difference between this implementation and |
|
| 96 |
/// \ref BellmanFordDefaultOperationTraits is that this class uses |
|
| 97 |
/// the \ref Tolerance "tolerance technique" in its \ref less() |
|
| 98 |
/// function. |
|
| 99 |
/// |
|
| 100 |
/// \tparam V The value type. |
|
| 101 |
/// \tparam eps The epsilon value for the \ref less() function. |
|
| 102 |
/// By default, it is the epsilon value used by \ref Tolerance |
|
| 103 |
/// "Tolerance<V>". |
|
| 104 |
/// |
|
| 105 |
/// \see BellmanFordDefaultOperationTraits |
|
| 106 |
#ifdef DOXYGEN |
|
| 107 |
template <typename V, V eps> |
|
| 108 |
#else |
|
| 109 |
template < |
|
| 110 |
typename V, |
|
| 111 |
V eps = Tolerance<V>::def_epsilon> |
|
| 112 |
#endif |
|
| 113 |
struct BellmanFordToleranceOperationTraits {
|
|
| 114 |
/// \brief Value type for the algorithm. |
|
| 115 |
typedef V Value; |
|
| 116 |
/// \brief Gives back the zero value of the type. |
|
| 117 |
static Value zero() {
|
|
| 118 |
return static_cast<Value>(0); |
|
| 119 |
} |
|
| 120 |
/// \brief Gives back the positive infinity value of the type. |
|
| 121 |
static Value infinity() {
|
|
| 122 |
return std::numeric_limits<Value>::infinity(); |
|
| 123 |
} |
|
| 124 |
/// \brief Gives back the sum of the given two elements. |
|
| 125 |
static Value plus(const Value& left, const Value& right) {
|
|
| 126 |
return left + right; |
|
| 127 |
} |
|
| 128 |
/// \brief Gives back \c true only if the first value is less than |
|
| 129 |
/// the second. |
|
| 130 |
static bool less(const Value& left, const Value& right) {
|
|
| 131 |
return left + eps < right; |
|
| 132 |
} |
|
| 133 |
}; |
|
| 134 |
|
|
| 135 | 87 |
/// \brief Default traits class of BellmanFord class. |
| ... | ... |
@@ -157,4 +109,3 @@ |
| 157 | 109 |
/// given \c Value type. |
| 158 |
/// \see BellmanFordDefaultOperationTraits, |
|
| 159 |
/// BellmanFordToleranceOperationTraits |
|
| 110 |
/// \see BellmanFordDefaultOperationTraits |
|
| 160 | 111 |
typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; |
| ... | ... |
@@ -888,4 +839,3 @@ |
| 888 | 839 |
/// given \c Value type. |
| 889 |
/// \see BellmanFordDefaultOperationTraits, |
|
| 890 |
/// BellmanFordToleranceOperationTraits |
|
| 840 |
/// \see BellmanFordDefaultOperationTraits |
|
| 891 | 841 |
typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; |
| ... | ... |
@@ -40,3 +40,3 @@ |
| 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 |
| ... | ... |
@@ -101,3 +101,3 @@ |
| 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. |
0 comments (0 inline)