Changes in / [963:3ed8f7c8bed8:961:7af2ae7c1428] in lemon
- Files:
-
- 7 edited
Legend:
- Unmodified
- Added
- Removed
-
LICENSE
r959 r600 2 2 copyright/license. 3 3 4 Copyright (C) 2003-20 10Egervary Jeno Kombinatorikus Optimalizalasi4 Copyright (C) 2003-2009 Egervary Jeno Kombinatorikus Optimalizalasi 5 5 Kutatocsoport (Egervary Combinatorial Optimization Research Group, 6 6 EGRES). -
NEWS
r962 r712 1 2010-03-19 Version 1.2 released2 3 This is major feature release4 5 * New algorithms6 * Bellman-Ford algorithm (#51)7 * Minimum mean cycle algorithms (#179)8 * Karp, Hartman-Orlin and Howard algorithms9 * New minimum cost flow algorithms (#180)10 * Cost Scaling algorithms11 * Capacity Scaling algorithm12 * Cycle-Canceling algorithms13 * Planarity related algorithms (#62)14 * Planarity checking algorithm15 * Planar embedding algorithm16 * Schnyder's planar drawing algorithm17 * Coloring planar graphs with five or six colors18 * Fractional matching algorithms (#314)19 * New data structures20 * StaticDigraph structure (#68)21 * Several new priority queue structures (#50, #301)22 * Fibonacci, Radix, Bucket, Pairing, Binomial23 D-ary and fourary heaps (#301)24 * Iterable map structures (#73)25 * Other new tools and functionality26 * 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 NetworkSimplex33 to handle graph changes (#327)34 * tolerance() functions are added to HaoOrlin (#306)35 * Implementation improvements36 * Improvements in weighted matching algorithms (#314)37 * Jumpstart initialization38 * ArcIt iteration is based on out-arc lists instead of in-arc lists39 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 * Miscellaneous44 * A simple interactive bootstrap script45 * 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 tests49 * 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 pragmas53 ----: Various CMAKE related improvements54 * Remove duplications from doc/CMakeLists.txt55 * Rename documentation install folder from 'docs' to 'html'56 * Add tools/CMakeLists.txt to the tarball57 * Generate and install LEMONConfig.cmake58 * Change the label of the html project in Visual Studio59 * Fix the check for the 'long long' type60 * Put the version string into config.h61 * Minor CMake improvements62 * Set the version to 'hg-tip' if everything fails63 #311: Add missing 'explicit' keywords64 #302: Fix the implementation and doc of CrossRefMap65 #308: Remove duplicate list_graph.h entry from source list66 #307: Bugfix in Preflow and Circulation67 #305: Bugfix and extension in the rename script68 #312: Also check ReferenceMapTag in concept checks69 #250: Bugfix in pathSource() and pathTarget()70 #321: Use pathCopy(from,to) instead of copyPath(to,from)71 #322: Distribure LEMONConfig.cmake.in72 #330: Bug fix in map_extender.h73 #336: Fix the date field comment of graphToEps() output74 #323: Bug fix in Suurballe75 #335: Fix clear() function in ExtendFindEnum76 #337: Use void* as the LPX object pointer77 #317: Fix (and improve) error message in mip_test.cc78 Remove unnecessary OsiCbc dependency79 #356: Allow multiple executions of weighted matching algorithms (#356)80 81 1 2009-05-13 Version 1.1 released 82 2 … … 153 73 ----: Add missing unistd.h include to time_measure.h 154 74 #204: Compilation bug fixed in graph_to_eps.h with VS2005 155 #214,#215: windows.h should never be included by LEMONheaders75 #214,#215: windows.h should never be included by lemon headers 156 76 #230: Build systems check the availability of 'long long' type 157 77 #229: Default implementation of Tolerance<> is used for integer types … … 175 95 2008-10-13 Version 1.0 released 176 96 177 178 179 180 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. 181 101 182 102 * The major name changes compared to the 0.x series (see the 183 103 Migration Guide in the doc for more details) 184 104 * Graph -> Digraph, UGraph -> Graph 185 105 * Edge -> Arc, UEdge -> Edge 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 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) 204 124 * Concepts 205 125 * graph structure concepts (concepts/digraph.h, concepts/graph.h, 206 126 concepts/graph_components.h) 207 208 209 210 211 212 213 214 215 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 * tools for reading and writing data in LEMON Graph Format 216 136 (lgf_reader.h, lgf_writer.h) 217 137 * tools to handle the anomalies of calculations with 218 138 floating point numbers (tolerance.h) 219 139 * tools to manage RGB colors (color.h) 220 221 222 223 224 140 * Infrastructure 141 * extended assertion handling (assert.h) 142 * exception classes and error handling (error.h) 143 * concept checking (concept_check.h) 144 * commonly used mathematical constants (math.h) -
doc/groups.dox
r963 r961 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 /** 266 274 @defgroup auxdat Auxiliary Data Structures 267 275 @ingroup datas … … 441 449 442 450 LEMON contains three algorithms for solving the minimum mean cycle problem: 443 - \ref Karp Mmc Karp's original algorithm \ref amo93networkflows,451 - \ref Karp "Karp"'s original algorithm \ref amo93networkflows, 444 452 \ref dasdan98minmeancycle. 445 - \ref HartmannOrlin Mmc Hartmann-Orlin's algorithm, which is an improved453 - \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved 446 454 version of Karp's algorithm \ref dasdan98minmeancycle. 447 - \ref Howard Mmc Howard's policy iteration algorithm455 - \ref Howard "Howard"'s policy iteration algorithm 448 456 \ref dasdan98minmeancycle. 449 457 450 In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the451 most efficient one, though the best known theoretical bound on its running 452 time isexponential.453 Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms454 run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is 455 typically faster due to theapplied early termination scheme.458 In practice, the Howard algorithm proved to be by far the most efficient 459 one, though the best known theoretical bound on its running time is 460 exponential. 461 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space 462 O(n<sup>2</sup>+e), but the latter one is typically faster due to the 463 applied early termination scheme. 456 464 */ 457 465 -
lemon/arg_parser.h
r959 r956 36 36 37 37 ///Exception used by ArgParser 38 39 ///Exception used by ArgParser.40 ///41 38 class ArgParserException : public Exception { 42 39 public: 43 /// Reasons for failure44 45 /// Reasons for failure.46 ///47 40 enum Reason { 48 HELP, /// < <tt>--help</tt> option was given.49 UNKNOWN_OPT, /// < Unknown option was given.50 INVALID_OPT /// < Invalid combination of options.41 HELP, /// <tt>--help</tt> option was given 42 UNKNOWN_OPT, /// Unknown option was given 43 INVALID_OPT /// Invalid combination of options 51 44 }; 52 45 -
lemon/bellman_ford.h
r960 r956 29 29 #include <lemon/error.h> 30 30 #include <lemon/maps.h> 31 #include <lemon/tolerance.h> 31 32 #include <lemon/path.h> 32 33 … … 35 36 namespace lemon { 36 37 37 /// \brief Default OperationTraits for the BellmanFord algorithm class.38 /// \brief Default operation traits for the BellmanFord algorithm class. 38 39 /// 39 40 /// This operation traits class defines all computational operations … … 42 43 /// If the numeric type does not have infinity value, then the maximum 43 44 /// value is used as extremal infinity value. 45 /// 46 /// \see BellmanFordToleranceOperationTraits 44 47 template < 45 48 typename V, 46 49 bool has_inf = std::numeric_limits<V>::has_infinity> 47 50 struct BellmanFordDefaultOperationTraits { 48 /// \ e51 /// \brief Value type for the algorithm. 49 52 typedef V Value; 50 53 /// \brief Gives back the zero value of the type. … … 82 85 static bool less(const Value& left, const Value& right) { 83 86 return left < right; 87 } 88 }; 89 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; 84 132 } 85 133 }; … … 108 156 /// It defines the used operations and the infinity value for the 109 157 /// given \c Value type. 110 /// \see BellmanFordDefaultOperationTraits 158 /// \see BellmanFordDefaultOperationTraits, 159 /// BellmanFordToleranceOperationTraits 111 160 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; 112 161 … … 838 887 /// It defines the used operations and the infinity value for the 839 888 /// given \c Value type. 840 /// \see BellmanFordDefaultOperationTraits 889 /// \see BellmanFordDefaultOperationTraits, 890 /// BellmanFordToleranceOperationTraits 841 891 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; 842 892 -
lemon/hartmann_orlin_mmc.h
r959 r956 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::Rea dMap "ReadMap" concept.41 /// It must conform to the \ref concepts::Rea_data "Rea_data" concept. 42 42 #ifdef DOXYGEN 43 43 template <typename GR, typename CM> … … 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 Karp Mmc"Karp"'s original algorithm,102 /// It is an improved version of \ref Karp "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). -
test/bellman_ford_test.cc
r960 r956 105 105 ::SetDistMap<concepts::ReadWriteMap<Node,Value> > 106 106 ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> > 107 ::SetOperationTraits<BellmanFordToleranceOperationTraits<Value, 0> > 107 108 ::Create bf_test(gr,length); 108 109
Note: See TracChangeset
for help on using the changeset viewer.