r965:a1fd7008a052
Tue, 20 Dec 2011 18:15:38
[Not Reviewed]
0 comments (0 inline)
0
7
0
1
1
81
1
9
17
| 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 |
| 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 |
| 2 | 82 |
|
| 3 | 83 |
This is the second stable release of the 1.x series. It |
| ... | ... |
@@ -72,7 +152,7 @@ |
| 72 | 152 |
----: Minor clarification in the LICENSE file |
| 73 | 153 |
----: Add missing unistd.h include to time_measure.h |
| 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 |
| 77 | 157 |
#229: Default implementation of Tolerance<> is used for integer types |
| 78 | 158 |
#211,#212: Various fixes for compiling on AIX |
| ... | ... |
@@ -263,14 +263,6 @@ |
| 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. |
| ... | ... |
@@ -472,19 +464,19 @@ |
| 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 |
/** |
| ... | ... |
@@ -35,12 +35,19 @@ |
| 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: |
| ... | ... |
@@ -28,27 +28,24 @@ |
| 28 | 28 |
#include <lemon/core.h> |
| 29 | 29 |
#include <lemon/error.h> |
| 30 | 30 |
#include <lemon/maps.h> |
| 31 |
#include <lemon/tolerance.h> |
|
| 32 | 31 |
#include <lemon/path.h> |
| 33 | 32 |
|
| 34 | 33 |
#include <limits> |
| 35 | 34 |
|
| 36 | 35 |
namespace lemon {
|
| 37 | 36 |
|
| 38 |
/// \brief Default |
|
| 37 |
/// \brief Default OperationTraits for the BellmanFord algorithm class. |
|
| 39 | 38 |
/// |
| 40 | 39 |
/// This operation traits class defines all computational operations |
| 41 | 40 |
/// and constants that are used in the Bellman-Ford algorithm. |
| 42 | 41 |
/// The default implementation is based on the \c numeric_limits class. |
| 43 | 42 |
/// If the numeric type does not have infinity value, then the maximum |
| 44 | 43 |
/// value is used as extremal infinity value. |
| 45 |
/// |
|
| 46 |
/// \see BellmanFordToleranceOperationTraits |
|
| 47 | 44 |
template < |
| 48 | 45 |
typename V, |
| 49 | 46 |
bool has_inf = std::numeric_limits<V>::has_infinity> |
| 50 | 47 |
struct BellmanFordDefaultOperationTraits {
|
| 51 |
/// \ |
|
| 48 |
/// \e |
|
| 52 | 49 |
typedef V Value; |
| 53 | 50 |
/// \brief Gives back the zero value of the type. |
| 54 | 51 |
static Value zero() {
|
| ... | ... |
@@ -87,51 +84,6 @@ |
| 87 | 84 |
} |
| 88 | 85 |
}; |
| 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. |
| 136 | 88 |
/// |
| 137 | 89 |
/// Default traits class of BellmanFord class. |
| ... | ... |
@@ -155,8 +107,7 @@ |
| 155 | 107 |
/// |
| 156 | 108 |
/// It defines the used operations and the infinity value for the |
| 157 | 109 |
/// given \c Value type. |
| 158 |
/// \see BellmanFordDefaultOperationTraits, |
|
| 159 |
/// BellmanFordToleranceOperationTraits |
|
| 110 |
/// \see BellmanFordDefaultOperationTraits |
|
| 160 | 111 |
typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; |
| 161 | 112 |
|
| 162 | 113 |
/// \brief The type of the map that stores the last arcs of the |
| ... | ... |
@@ -886,8 +837,7 @@ |
| 886 | 837 |
/// |
| 887 | 838 |
/// It defines the used operations and the infinity value for the |
| 888 | 839 |
/// given \c Value type. |
| 889 |
/// \see BellmanFordDefaultOperationTraits, |
|
| 890 |
/// BellmanFordToleranceOperationTraits |
|
| 840 |
/// \see BellmanFordDefaultOperationTraits |
|
| 891 | 841 |
typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; |
| 892 | 842 |
|
| 893 | 843 |
/// \brief The type of the map that stores the last |
| ... | ... |
@@ -38,7 +38,7 @@ |
| 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 |
| ... | ... |
@@ -99,7 +99,7 @@ |
| 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 |
/// |
| ... | ... |
@@ -104,7 +104,6 @@ |
| 104 | 104 |
BF::SetPredMap<concepts::ReadWriteMap<Node,Arc> > |
| 105 | 105 |
::SetDistMap<concepts::ReadWriteMap<Node,Value> > |
| 106 | 106 |
::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> > |
| 107 |
::SetOperationTraits<BellmanFordToleranceOperationTraits<Value, 0> > |
|
| 108 | 107 |
::Create bf_test(gr,length); |
| 109 | 108 |
|
| 110 | 109 |
LengthMap length_map; |
0 comments (0 inline)