1.1 --- a/LICENSE Thu Mar 18 00:29:35 2010 +0100
1.2 +++ b/LICENSE Thu Mar 18 14:50:32 2010 +0100
1.3 @@ -1,7 +1,7 @@
1.4 LEMON code without an explicit copyright notice is covered by the following
1.5 copyright/license.
1.6
1.7 -Copyright (C) 2003-2009 Egervary Jeno Kombinatorikus Optimalizalasi
1.8 +Copyright (C) 2003-2010 Egervary Jeno Kombinatorikus Optimalizalasi
1.9 Kutatocsoport (Egervary Combinatorial Optimization Research Group,
1.10 EGRES).
1.11
2.1 --- a/NEWS Thu Mar 18 00:29:35 2010 +0100
2.2 +++ b/NEWS Thu Mar 18 14:50:32 2010 +0100
2.3 @@ -1,3 +1,83 @@
2.4 +2010-03-19 Version 1.2 released
2.5 +
2.6 + This is major feature release
2.7 +
2.8 + * New algorithms
2.9 + * Bellman-Ford algorithm (#51)
2.10 + * Minimum mean cycle algorithms (#179)
2.11 + * Karp, Hartman-Orlin and Howard algorithms
2.12 + * New minimum cost flow algorithms (#180)
2.13 + * Cost Scaling algorithms
2.14 + * Capacity Scaling algorithm
2.15 + * Cycle-Canceling algorithms
2.16 + * Planarity related algorithms (#62)
2.17 + * Planarity checking algorithm
2.18 + * Planar embedding algorithm
2.19 + * Schnyder's planar drawing algorithm
2.20 + * Coloring planar graphs with five or six colors
2.21 + * Fractional matching algorithms (#314)
2.22 + * New data structures
2.23 + * StaticDigraph structure (#68)
2.24 + * Several new priority queue structures (#50, #301)
2.25 + * Fibonacci, Radix, Bucket, Pairing, Binomial
2.26 + D-ary and fourary heaps (#301)
2.27 + * Iterable map structures (#73)
2.28 + * Other new tools and functionality
2.29 + * Map utility functions (#320)
2.30 + * Reserve functions are added to ListGraph and SmartGraph (#311)
2.31 + * A resize() function is added to HypercubeGraph (#311)
2.32 + * A count() function is added to CrossRefMap (#302)
2.33 + * Support for multiple targets in Suurballe using fullInit() (#181)
2.34 + * Traits class and named parameters for Suurballe (#323)
2.35 + * Separate reset() and resetParams() functions in NetworkSimplex
2.36 + to handle graph changes (#327)
2.37 + * tolerance() functions are added to HaoOrlin (#306)
2.38 + * Implementation improvements
2.39 + * Improvements in weighted matching algorithms (#314)
2.40 + * Jumpstart initialization
2.41 + * ArcIt iteration is based on out-arc lists instead of in-arc lists
2.42 + in ListDigraph (#311)
2.43 + * Faster add row operation in CbcMip (#203)
2.44 + * Better implementation for split() in ListDigraph (#311)
2.45 + * ArgParser can also throw exception instead of exit(1) (#332)
2.46 + * Miscellaneous
2.47 + * A simple interactive bootstrap script
2.48 + * Doc improvements (#62,#180,#299,#302,#303,#304,#307,#311,#331,#315,
2.49 + #316,#319)
2.50 + * BibTeX references in the doc (#184)
2.51 + * Optionally use valgrind when running tests
2.52 + * Also check ReferenceMapTag in concept checks (#312)
2.53 + * dimacs-solver uses long long type by default.
2.54 + * Several bugfixes (compared to release 1.1):
2.55 + #295: Suppress MSVC warnings using pragmas
2.56 + ----: Various CMAKE related improvements
2.57 + * Remove duplications from doc/CMakeLists.txt
2.58 + * Rename documentation install folder from 'docs' to 'html'
2.59 + * Add tools/CMakeLists.txt to the tarball
2.60 + * Generate and install LEMONConfig.cmake
2.61 + * Change the label of the html project in Visual Studio
2.62 + * Fix the check for the 'long long' type
2.63 + * Put the version string into config.h
2.64 + * Minor CMake improvements
2.65 + * Set the version to 'hg-tip' if everything fails
2.66 + #311: Add missing 'explicit' keywords
2.67 + #302: Fix the implementation and doc of CrossRefMap
2.68 + #308: Remove duplicate list_graph.h entry from source list
2.69 + #307: Bugfix in Preflow and Circulation
2.70 + #305: Bugfix and extension in the rename script
2.71 + #312: Also check ReferenceMapTag in concept checks
2.72 + #250: Bugfix in pathSource() and pathTarget()
2.73 + #321: Use pathCopy(from,to) instead of copyPath(to,from)
2.74 + #322: Distribure LEMONConfig.cmake.in
2.75 + #330: Bug fix in map_extender.h
2.76 + #336: Fix the date field comment of graphToEps() output
2.77 + #323: Bug fix in Suurballe
2.78 + #335: Fix clear() function in ExtendFindEnum
2.79 + #337: Use void* as the LPX object pointer
2.80 + #317: Fix (and improve) error message in mip_test.cc
2.81 + Remove unnecessary OsiCbc dependency
2.82 + #356: Allow multiple executions of weighted matching algorithms (#356)
2.83 +
2.84 2009-05-13 Version 1.1 released
2.85
2.86 This is the second stable release of the 1.x series. It
2.87 @@ -72,7 +152,7 @@
2.88 ----: Minor clarification in the LICENSE file
2.89 ----: Add missing unistd.h include to time_measure.h
2.90 #204: Compilation bug fixed in graph_to_eps.h with VS2005
2.91 - #214,#215: windows.h should never be included by lemon headers
2.92 + #214,#215: windows.h should never be included by LEMON headers
2.93 #230: Build systems check the availability of 'long long' type
2.94 #229: Default implementation of Tolerance<> is used for integer types
2.95 #211,#212: Various fixes for compiling on AIX
2.96 @@ -94,51 +174,51 @@
2.97
2.98 2008-10-13 Version 1.0 released
2.99
2.100 - This is the first stable release of LEMON. Compared to the 0.x
2.101 - release series, it features a considerably smaller but more
2.102 - matured set of tools. The API has also completely revised and
2.103 - changed in several places.
2.104 + This is the first stable release of LEMON. Compared to the 0.x
2.105 + release series, it features a considerably smaller but more
2.106 + matured set of tools. The API has also completely revised and
2.107 + changed in several places.
2.108
2.109 - * The major name changes compared to the 0.x series (see the
2.110 + * The major name changes compared to the 0.x series (see the
2.111 Migration Guide in the doc for more details)
2.112 * Graph -> Digraph, UGraph -> Graph
2.113 * Edge -> Arc, UEdge -> Edge
2.114 - * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
2.115 - * Other improvements
2.116 - * Better documentation
2.117 - * Reviewed and cleaned up codebase
2.118 - * CMake based build system (along with the autotools based one)
2.119 - * Contents of the library (ported from 0.x)
2.120 - * Algorithms
2.121 - * breadth-first search (bfs.h)
2.122 - * depth-first search (dfs.h)
2.123 - * Dijkstra's algorithm (dijkstra.h)
2.124 - * Kruskal's algorithm (kruskal.h)
2.125 - * Data structures
2.126 - * graph data structures (list_graph.h, smart_graph.h)
2.127 - * path data structures (path.h)
2.128 - * binary heap data structure (bin_heap.h)
2.129 - * union-find data structures (unionfind.h)
2.130 - * miscellaneous property maps (maps.h)
2.131 - * two dimensional vector and bounding box (dim2.h)
2.132 + * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
2.133 + * Other improvements
2.134 + * Better documentation
2.135 + * Reviewed and cleaned up codebase
2.136 + * CMake based build system (along with the autotools based one)
2.137 + * Contents of the library (ported from 0.x)
2.138 + * Algorithms
2.139 + * breadth-first search (bfs.h)
2.140 + * depth-first search (dfs.h)
2.141 + * Dijkstra's algorithm (dijkstra.h)
2.142 + * Kruskal's algorithm (kruskal.h)
2.143 + * Data structures
2.144 + * graph data structures (list_graph.h, smart_graph.h)
2.145 + * path data structures (path.h)
2.146 + * binary heap data structure (bin_heap.h)
2.147 + * union-find data structures (unionfind.h)
2.148 + * miscellaneous property maps (maps.h)
2.149 + * two dimensional vector and bounding box (dim2.h)
2.150 * Concepts
2.151 - * graph structure concepts (concepts/digraph.h, concepts/graph.h,
2.152 + * graph structure concepts (concepts/digraph.h, concepts/graph.h,
2.153 concepts/graph_components.h)
2.154 - * concepts for other structures (concepts/heap.h, concepts/maps.h,
2.155 - concepts/path.h)
2.156 - * Tools
2.157 - * Mersenne twister random number generator (random.h)
2.158 - * tools for measuring cpu and wall clock time (time_measure.h)
2.159 - * tools for counting steps and events (counter.h)
2.160 - * tool for parsing command line arguments (arg_parser.h)
2.161 - * tool for visualizing graphs (graph_to_eps.h)
2.162 - * tools for reading and writing data in LEMON Graph Format
2.163 + * concepts for other structures (concepts/heap.h, concepts/maps.h,
2.164 + concepts/path.h)
2.165 + * Tools
2.166 + * Mersenne twister random number generator (random.h)
2.167 + * tools for measuring cpu and wall clock time (time_measure.h)
2.168 + * tools for counting steps and events (counter.h)
2.169 + * tool for parsing command line arguments (arg_parser.h)
2.170 + * tool for visualizing graphs (graph_to_eps.h)
2.171 + * tools for reading and writing data in LEMON Graph Format
2.172 (lgf_reader.h, lgf_writer.h)
2.173 * tools to handle the anomalies of calculations with
2.174 - floating point numbers (tolerance.h)
2.175 + floating point numbers (tolerance.h)
2.176 * tools to manage RGB colors (color.h)
2.177 - * Infrastructure
2.178 - * extended assertion handling (assert.h)
2.179 - * exception classes and error handling (error.h)
2.180 - * concept checking (concept_check.h)
2.181 - * commonly used mathematical constants (math.h)
2.182 + * Infrastructure
2.183 + * extended assertion handling (assert.h)
2.184 + * exception classes and error handling (error.h)
2.185 + * concept checking (concept_check.h)
2.186 + * commonly used mathematical constants (math.h)
3.1 --- a/doc/groups.dox Thu Mar 18 00:29:35 2010 +0100
3.2 +++ b/doc/groups.dox Thu Mar 18 14:50:32 2010 +0100
3.3 @@ -263,14 +263,6 @@
3.4 */
3.5
3.6 /**
3.7 -@defgroup matrices Matrices
3.8 -@ingroup datas
3.9 -\brief Two dimensional data storages implemented in LEMON.
3.10 -
3.11 -This group contains two dimensional data storages implemented in LEMON.
3.12 -*/
3.13 -
3.14 -/**
3.15 @defgroup auxdat Auxiliary Data Structures
3.16 @ingroup datas
3.17 \brief Auxiliary data structures implemented in LEMON.
3.18 @@ -448,19 +440,19 @@
3.19 function.
3.20
3.21 LEMON contains three algorithms for solving the minimum mean cycle problem:
3.22 -- \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
3.23 +- \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
3.24 \ref dasdan98minmeancycle.
3.25 -- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
3.26 +- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
3.27 version of Karp's algorithm \ref dasdan98minmeancycle.
3.28 -- \ref Howard "Howard"'s policy iteration algorithm
3.29 +- \ref HowardMmc Howard's policy iteration algorithm
3.30 \ref dasdan98minmeancycle.
3.31
3.32 -In practice, the Howard algorithm proved to be by far the most efficient
3.33 -one, though the best known theoretical bound on its running time is
3.34 -exponential.
3.35 -Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
3.36 -O(n<sup>2</sup>+e), but the latter one is typically faster due to the
3.37 -applied early termination scheme.
3.38 +In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
3.39 +most efficient one, though the best known theoretical bound on its running
3.40 +time is exponential.
3.41 +Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
3.42 +run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
3.43 +typically faster due to the applied early termination scheme.
3.44 */
3.45
3.46 /**
4.1 --- a/lemon/arg_parser.h Thu Mar 18 00:29:35 2010 +0100
4.2 +++ b/lemon/arg_parser.h Thu Mar 18 14:50:32 2010 +0100
4.3 @@ -35,12 +35,19 @@
4.4 namespace lemon {
4.5
4.6 ///Exception used by ArgParser
4.7 +
4.8 + ///Exception used by ArgParser.
4.9 + ///
4.10 class ArgParserException : public Exception {
4.11 public:
4.12 + /// Reasons for failure
4.13 +
4.14 + /// Reasons for failure.
4.15 + ///
4.16 enum Reason {
4.17 - HELP, /// <tt>--help</tt> option was given
4.18 - UNKNOWN_OPT, /// Unknown option was given
4.19 - INVALID_OPT /// Invalid combination of options
4.20 + HELP, ///< <tt>--help</tt> option was given.
4.21 + UNKNOWN_OPT, ///< Unknown option was given.
4.22 + INVALID_OPT ///< Invalid combination of options.
4.23 };
4.24
4.25 private:
5.1 --- a/lemon/bellman_ford.h Thu Mar 18 00:29:35 2010 +0100
5.2 +++ b/lemon/bellman_ford.h Thu Mar 18 14:50:32 2010 +0100
5.3 @@ -28,27 +28,24 @@
5.4 #include <lemon/core.h>
5.5 #include <lemon/error.h>
5.6 #include <lemon/maps.h>
5.7 -#include <lemon/tolerance.h>
5.8 #include <lemon/path.h>
5.9
5.10 #include <limits>
5.11
5.12 namespace lemon {
5.13
5.14 - /// \brief Default operation traits for the BellmanFord algorithm class.
5.15 + /// \brief Default OperationTraits for the BellmanFord algorithm class.
5.16 ///
5.17 /// This operation traits class defines all computational operations
5.18 /// and constants that are used in the Bellman-Ford algorithm.
5.19 /// The default implementation is based on the \c numeric_limits class.
5.20 /// If the numeric type does not have infinity value, then the maximum
5.21 /// value is used as extremal infinity value.
5.22 - ///
5.23 - /// \see BellmanFordToleranceOperationTraits
5.24 template <
5.25 typename V,
5.26 bool has_inf = std::numeric_limits<V>::has_infinity>
5.27 struct BellmanFordDefaultOperationTraits {
5.28 - /// \brief Value type for the algorithm.
5.29 + /// \e
5.30 typedef V Value;
5.31 /// \brief Gives back the zero value of the type.
5.32 static Value zero() {
5.33 @@ -87,51 +84,6 @@
5.34 }
5.35 };
5.36
5.37 - /// \brief Operation traits for the BellmanFord algorithm class
5.38 - /// using tolerance.
5.39 - ///
5.40 - /// This operation traits class defines all computational operations
5.41 - /// and constants that are used in the Bellman-Ford algorithm.
5.42 - /// The only difference between this implementation and
5.43 - /// \ref BellmanFordDefaultOperationTraits is that this class uses
5.44 - /// the \ref Tolerance "tolerance technique" in its \ref less()
5.45 - /// function.
5.46 - ///
5.47 - /// \tparam V The value type.
5.48 - /// \tparam eps The epsilon value for the \ref less() function.
5.49 - /// By default, it is the epsilon value used by \ref Tolerance
5.50 - /// "Tolerance<V>".
5.51 - ///
5.52 - /// \see BellmanFordDefaultOperationTraits
5.53 -#ifdef DOXYGEN
5.54 - template <typename V, V eps>
5.55 -#else
5.56 - template <
5.57 - typename V,
5.58 - V eps = Tolerance<V>::def_epsilon>
5.59 -#endif
5.60 - struct BellmanFordToleranceOperationTraits {
5.61 - /// \brief Value type for the algorithm.
5.62 - typedef V Value;
5.63 - /// \brief Gives back the zero value of the type.
5.64 - static Value zero() {
5.65 - return static_cast<Value>(0);
5.66 - }
5.67 - /// \brief Gives back the positive infinity value of the type.
5.68 - static Value infinity() {
5.69 - return std::numeric_limits<Value>::infinity();
5.70 - }
5.71 - /// \brief Gives back the sum of the given two elements.
5.72 - static Value plus(const Value& left, const Value& right) {
5.73 - return left + right;
5.74 - }
5.75 - /// \brief Gives back \c true only if the first value is less than
5.76 - /// the second.
5.77 - static bool less(const Value& left, const Value& right) {
5.78 - return left + eps < right;
5.79 - }
5.80 - };
5.81 -
5.82 /// \brief Default traits class of BellmanFord class.
5.83 ///
5.84 /// Default traits class of BellmanFord class.
5.85 @@ -155,8 +107,7 @@
5.86 ///
5.87 /// It defines the used operations and the infinity value for the
5.88 /// given \c Value type.
5.89 - /// \see BellmanFordDefaultOperationTraits,
5.90 - /// BellmanFordToleranceOperationTraits
5.91 + /// \see BellmanFordDefaultOperationTraits
5.92 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
5.93
5.94 /// \brief The type of the map that stores the last arcs of the
5.95 @@ -886,8 +837,7 @@
5.96 ///
5.97 /// It defines the used operations and the infinity value for the
5.98 /// given \c Value type.
5.99 - /// \see BellmanFordDefaultOperationTraits,
5.100 - /// BellmanFordToleranceOperationTraits
5.101 + /// \see BellmanFordDefaultOperationTraits
5.102 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
5.103
5.104 /// \brief The type of the map that stores the last
6.1 --- a/lemon/hartmann_orlin_mmc.h Thu Mar 18 00:29:35 2010 +0100
6.2 +++ b/lemon/hartmann_orlin_mmc.h Thu Mar 18 14:50:32 2010 +0100
6.3 @@ -38,7 +38,7 @@
6.4 /// Default traits class of HartmannOrlinMmc class.
6.5 /// \tparam GR The type of the digraph.
6.6 /// \tparam CM The type of the cost map.
6.7 - /// It must conform to the \ref concepts::Rea_data "Rea_data" concept.
6.8 + /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
6.9 #ifdef DOXYGEN
6.10 template <typename GR, typename CM>
6.11 #else
6.12 @@ -99,7 +99,7 @@
6.13 /// This class implements the Hartmann-Orlin algorithm for finding
6.14 /// a directed cycle of minimum mean cost in a digraph
6.15 /// \ref amo93networkflows, \ref dasdan98minmeancycle.
6.16 - /// It is an improved version of \ref Karp "Karp"'s original algorithm,
6.17 + /// It is an improved version of \ref KarpMmc "Karp"'s original algorithm,
6.18 /// it applies an efficient early termination scheme.
6.19 /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
6.20 ///
7.1 --- a/test/bellman_ford_test.cc Thu Mar 18 00:29:35 2010 +0100
7.2 +++ b/test/bellman_ford_test.cc Thu Mar 18 14:50:32 2010 +0100
7.3 @@ -104,7 +104,6 @@
7.4 BF::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
7.5 ::SetDistMap<concepts::ReadWriteMap<Node,Value> >
7.6 ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> >
7.7 - ::SetOperationTraits<BellmanFordToleranceOperationTraits<Value, 0> >
7.8 ::Create bf_test(gr,length);
7.9
7.10 LengthMap length_map;