Merge
authorAlpar Juttner <alpar@cs.elte.hu>
Tue, 20 Dec 2011 18:15:38 +0100
changeset 1108a1fd7008a052
parent 1107 2b6bffe0e7e8
parent 962 87569cb5734d
child 1110 02c93d1f00d7
child 1111 c8fce9beb46a
child 1114 cfdbf1574403
Merge
     1.1 --- a/LICENSE	Tue Dec 20 18:15:14 2011 +0100
     1.2 +++ b/LICENSE	Tue Dec 20 18:15:38 2011 +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	Tue Dec 20 18:15:14 2011 +0100
     2.2 +++ b/NEWS	Tue Dec 20 18:15:38 2011 +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	Tue Dec 20 18:15:14 2011 +0100
     3.2 +++ b/doc/groups.dox	Tue Dec 20 18:15:38 2011 +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 @@ -472,19 +464,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	Tue Dec 20 18:15:14 2011 +0100
     4.2 +++ b/lemon/arg_parser.h	Tue Dec 20 18:15:38 2011 +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	Tue Dec 20 18:15:14 2011 +0100
     5.2 +++ b/lemon/bellman_ford.h	Tue Dec 20 18:15:38 2011 +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	Tue Dec 20 18:15:14 2011 +0100
     6.2 +++ b/lemon/hartmann_orlin_mmc.h	Tue Dec 20 18:15:38 2011 +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	Tue Dec 20 18:15:14 2011 +0100
     7.2 +++ b/test/bellman_ford_test.cc	Tue Dec 20 18:15:38 2011 +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;