Changes in / [1107:2b6bffe0e7e8:1108:a1fd7008a052] in lemon
- Files:
-
- 7 edited
Legend:
- Unmodified
- Added
- Removed
-
TabularUnified LICENSE ¶
r600 r959 2 2 copyright/license. 3 3 4 Copyright (C) 2003-20 09Egervary Jeno Kombinatorikus Optimalizalasi4 Copyright (C) 2003-2010 Egervary Jeno Kombinatorikus Optimalizalasi 5 5 Kutatocsoport (Egervary Combinatorial Optimization Research Group, 6 6 EGRES). -
TabularUnified NEWS ¶
r712 r962 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 … … 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 lemonheaders155 #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 … … 95 175 2008-10-13 Version 1.0 released 96 176 97 98 99 100 101 102 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. 181 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 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 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 128 129 130 131 132 133 134 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 141 142 143 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) -
TabularUnified doc/groups.dox ¶
r956 r959 264 264 265 265 /** 266 @defgroup matrices Matrices267 @ingroup datas268 \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 … … 473 465 474 466 LEMON contains three algorithms for solving the minimum mean cycle problem: 475 - \ref Karp "Karp"'s original algorithm \ref amo93networkflows,467 - \ref KarpMmc Karp's original algorithm \ref amo93networkflows, 476 468 \ref dasdan98minmeancycle. 477 - \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved469 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved 478 470 version of Karp's algorithm \ref dasdan98minmeancycle. 479 - \ref Howard "Howard"'s policy iteration algorithm471 - \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 efficient483 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 space486 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 -
TabularUnified lemon/arg_parser.h ¶
r956 r959 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 given42 UNKNOWN_OPT, /// Unknown option was given43 INVALID_OPT /// Invalid combination of options48 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 -
TabularUnified lemon/bellman_ford.h ¶
r956 r960 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 … … 36 35 namespace lemon { 37 36 38 /// \brief Default operation traits for the BellmanFord algorithm class.37 /// \brief Default OperationTraits for the BellmanFord algorithm class. 39 38 /// 40 39 /// This operation traits class defines all computational operations … … 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 BellmanFordToleranceOperationTraits47 44 template < 48 45 typename V, 49 46 bool has_inf = std::numeric_limits<V>::has_infinity> 50 47 struct BellmanFordDefaultOperationTraits { 51 /// \ brief Value type for the algorithm.48 /// \e 52 49 typedef V Value; 53 50 /// \brief Gives back the zero value of the type. … … 85 82 static bool less(const Value& left, const Value& right) { 86 83 return left < right; 87 }88 };89 90 /// \brief Operation traits for the BellmanFord algorithm class91 /// using tolerance.92 ///93 /// This operation traits class defines all computational operations94 /// and constants that are used in the Bellman-Ford algorithm.95 /// The only difference between this implementation and96 /// \ref BellmanFordDefaultOperationTraits is that this class uses97 /// 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 Tolerance103 /// "Tolerance<V>".104 ///105 /// \see BellmanFordDefaultOperationTraits106 #ifdef DOXYGEN107 template <typename V, V eps>108 #else109 template <110 typename V,111 V eps = Tolerance<V>::def_epsilon>112 #endif113 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 than129 /// the second.130 static bool less(const Value& left, const Value& right) {131 return left + eps < right;132 84 } 133 85 }; … … 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 … … 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 -
TabularUnified lemon/hartmann_orlin_mmc.h ¶
r956 r959 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 _data "Rea_data" concept.41 /// It must conform to the \ref concepts::ReadMap "ReadMap" 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 "Karp"'s original algorithm,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). -
TabularUnified test/bellman_ford_test.cc ¶
r956 r960 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
Note: See TracChangeset
for help on using the changeset viewer.