r1108:a1fd7008a052
Tue, 20 Dec 2011 18:15:38
[Not Reviewed]
0 comments (0 inline)
0
7
0
1
1
120
40
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 |
|
| 8 | 8 |
=========================================================================== |
| 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 |
| 4 | 84 |
features a better coverage of the tools available in the 0.x |
| ... | ... |
@@ -71,9 +151,9 @@ |
| 71 | 151 |
(made by autotools) |
| 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 |
| 79 | 159 |
----: Improvements in CMAKE config |
| ... | ... |
@@ -93,52 +173,52 @@ |
| 93 | 173 |
community. |
| 94 | 174 |
|
| 95 | 175 |
2008-10-13 Version 1.0 released |
| 96 | 176 |
|
| 97 |
This is the first stable release of LEMON. Compared to the 0.x |
|
| 98 |
release series, it features a considerably smaller but more |
|
| 99 |
matured set of tools. The API has also completely revised and |
|
| 100 |
changed in several places. |
|
| 177 |
This is the first stable release of LEMON. Compared to the 0.x |
|
| 178 |
release series, it features a considerably smaller but more |
|
| 179 |
matured set of tools. The API has also completely revised and |
|
| 180 |
changed in several places. |
|
| 101 | 181 |
|
| 102 |
|
|
| 182 |
* The major name changes compared to the 0.x series (see the |
|
| 103 | 183 |
Migration Guide in the doc for more details) |
| 104 | 184 |
* Graph -> Digraph, UGraph -> Graph |
| 105 | 185 |
* Edge -> Arc, UEdge -> Edge |
| 106 |
* source(UEdge)/target(UEdge) -> u(Edge)/v(Edge) |
|
| 107 |
* Other improvements |
|
| 108 |
* Better documentation |
|
| 109 |
* Reviewed and cleaned up codebase |
|
| 110 |
* CMake based build system (along with the autotools based one) |
|
| 111 |
* Contents of the library (ported from 0.x) |
|
| 112 |
* Algorithms |
|
| 113 |
* breadth-first search (bfs.h) |
|
| 114 |
* depth-first search (dfs.h) |
|
| 115 |
* Dijkstra's algorithm (dijkstra.h) |
|
| 116 |
* Kruskal's algorithm (kruskal.h) |
|
| 117 |
* Data structures |
|
| 118 |
* graph data structures (list_graph.h, smart_graph.h) |
|
| 119 |
* path data structures (path.h) |
|
| 120 |
* binary heap data structure (bin_heap.h) |
|
| 121 |
* union-find data structures (unionfind.h) |
|
| 122 |
* miscellaneous property maps (maps.h) |
|
| 123 |
* two dimensional vector and bounding box (dim2.h) |
|
| 186 |
* source(UEdge)/target(UEdge) -> u(Edge)/v(Edge) |
|
| 187 |
* Other improvements |
|
| 188 |
* Better documentation |
|
| 189 |
* Reviewed and cleaned up codebase |
|
| 190 |
* CMake based build system (along with the autotools based one) |
|
| 191 |
* Contents of the library (ported from 0.x) |
|
| 192 |
* Algorithms |
|
| 193 |
* breadth-first search (bfs.h) |
|
| 194 |
* depth-first search (dfs.h) |
|
| 195 |
* Dijkstra's algorithm (dijkstra.h) |
|
| 196 |
* Kruskal's algorithm (kruskal.h) |
|
| 197 |
* Data structures |
|
| 198 |
* graph data structures (list_graph.h, smart_graph.h) |
|
| 199 |
* path data structures (path.h) |
|
| 200 |
* binary heap data structure (bin_heap.h) |
|
| 201 |
* union-find data structures (unionfind.h) |
|
| 202 |
* miscellaneous property maps (maps.h) |
|
| 203 |
* two dimensional vector and bounding box (dim2.h) |
|
| 124 | 204 |
* Concepts |
| 125 |
|
|
| 205 |
* graph structure concepts (concepts/digraph.h, concepts/graph.h, |
|
| 126 | 206 |
concepts/graph_components.h) |
| 127 |
* concepts for other structures (concepts/heap.h, concepts/maps.h, |
|
| 128 |
concepts/path.h) |
|
| 129 |
* Tools |
|
| 130 |
* Mersenne twister random number generator (random.h) |
|
| 131 |
* tools for measuring cpu and wall clock time (time_measure.h) |
|
| 132 |
* tools for counting steps and events (counter.h) |
|
| 133 |
* tool for parsing command line arguments (arg_parser.h) |
|
| 134 |
* tool for visualizing graphs (graph_to_eps.h) |
|
| 135 |
|
|
| 207 |
* concepts for other structures (concepts/heap.h, concepts/maps.h, |
|
| 208 |
concepts/path.h) |
|
| 209 |
* Tools |
|
| 210 |
* Mersenne twister random number generator (random.h) |
|
| 211 |
* tools for measuring cpu and wall clock time (time_measure.h) |
|
| 212 |
* tools for counting steps and events (counter.h) |
|
| 213 |
* tool for parsing command line arguments (arg_parser.h) |
|
| 214 |
* tool for visualizing graphs (graph_to_eps.h) |
|
| 215 |
* tools for reading and writing data in LEMON Graph Format |
|
| 136 | 216 |
(lgf_reader.h, lgf_writer.h) |
| 137 | 217 |
* tools to handle the anomalies of calculations with |
| 138 |
|
|
| 218 |
floating point numbers (tolerance.h) |
|
| 139 | 219 |
* tools to manage RGB colors (color.h) |
| 140 |
* Infrastructure |
|
| 141 |
* extended assertion handling (assert.h) |
|
| 142 |
* exception classes and error handling (error.h) |
|
| 143 |
* concept checking (concept_check.h) |
|
| 144 |
|
|
| 220 |
* Infrastructure |
|
| 221 |
* extended assertion handling (assert.h) |
|
| 222 |
* exception classes and error handling (error.h) |
|
| 223 |
* concept checking (concept_check.h) |
|
| 224 |
* commonly used mathematical constants (math.h) |
| ... | ... |
@@ -262,16 +262,8 @@ |
| 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 |
|
| ... | ... |
@@ -471,21 +463,21 @@ |
| 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 |
| ... | ... |
@@ -34,14 +34,21 @@ |
| 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; |
| ... | ... |
@@ -27,29 +27,26 @@ |
| 27 | 27 |
#include <lemon/bits/path_dump.h> |
| 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() {
|
| 55 | 52 |
return static_cast<Value>(0); |
| ... | ... |
@@ -86,53 +83,8 @@ |
| 86 | 83 |
return left < right; |
| 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. |
| 138 | 90 |
/// \param GR The type of the digraph. |
| ... | ... |
@@ -154,10 +106,9 @@ |
| 154 | 106 |
/// \brief Operation traits for Bellman-Ford algorithm. |
| 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 |
| 163 | 114 |
/// shortest paths. |
| ... | ... |
@@ -885,10 +836,9 @@ |
| 885 | 836 |
/// \brief Operation traits for Bellman-Ford algorithm. |
| 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 |
| 894 | 844 |
/// arcs of the shortest paths. |
| ... | ... |
@@ -37,9 +37,9 @@ |
| 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, |
| ... | ... |
@@ -98,9 +98,9 @@ |
| 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. |
| ... | ... |
@@ -103,9 +103,8 @@ |
| 103 | 103 |
{
|
| 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; |
| 111 | 110 |
concepts::ReadWriteMap<Node,Arc> pred_map; |
0 comments (0 inline)