RhodeCode

Copyright (C) 2003-2010 Egervary Jeno Kombinatorikus Optimalizalasi

2010-03-19 Version 1.2 released

        This is major feature release

        * New algorithms

          * Bellman-Ford algorithm (#51)

          * Minimum mean cycle algorithms (#179)

            * Karp, Hartman-Orlin and Howard algorithms

          * New minimum cost flow algorithms (#180)

            * Cost Scaling algorithms

            * Capacity Scaling algorithm

            * Cycle-Canceling algorithms

          * Planarity related algorithms (#62)

            * Planarity checking algorithm

            * Planar embedding algorithm

            * Schnyder's planar drawing algorithm

            * Coloring planar graphs with five or six colors

          * Fractional matching algorithms (#314)

        * New data structures

          * StaticDigraph structure (#68)

          * Several new priority queue structures (#50, #301)

            * Fibonacci, Radix, Bucket, Pairing, Binomial

              D-ary and fourary heaps (#301)

          * Iterable map structures (#73)

        * Other new tools and functionality

          * Map utility functions (#320)

          * Reserve functions are added to ListGraph and SmartGraph (#311)

          * A resize() function is added to HypercubeGraph (#311)

          * A count() function is added to CrossRefMap (#302)

          * Support for multiple targets in Suurballe using fullInit() (#181)

          * Traits class and named parameters for Suurballe (#323)

          * Separate reset() and resetParams() functions in NetworkSimplex

            to handle graph changes (#327)

          * tolerance() functions are added to HaoOrlin (#306)

        * Implementation improvements

          * Improvements in weighted matching algorithms (#314)

            * Jumpstart initialization

          * ArcIt iteration is based on out-arc lists instead of in-arc lists

            in ListDigraph (#311)

          * Faster add row operation in CbcMip (#203)

          * Better implementation for split() in ListDigraph (#311)

          * ArgParser can also throw exception instead of exit(1) (#332)

        * Miscellaneous

          * A simple interactive bootstrap script

          * Doc improvements (#62,#180,#299,#302,#303,#304,#307,#311,#331,#315,

                #316,#319)

            * BibTeX references in the doc (#184)

          * Optionally use valgrind when running tests

          * Also check ReferenceMapTag in concept checks (#312)

          * dimacs-solver uses long long type by default.

        * Several bugfixes (compared to release 1.1):

          #295: Suppress MSVC warnings using pragmas

          ----: Various CMAKE related improvements

                * Remove duplications from doc/CMakeLists.txt

                * Rename documentation install folder from 'docs' to 'html'

                * Add tools/CMakeLists.txt to the tarball

                * Generate and install LEMONConfig.cmake

                * Change the label of the html project in Visual Studio

                * Fix the check for the 'long long' type

                * Put the version string into config.h

                * Minor CMake improvements

                * Set the version to 'hg-tip' if everything fails

          #311: Add missing 'explicit' keywords

          #302: Fix the implementation and doc of CrossRefMap

          #308: Remove duplicate list_graph.h entry from source list

          #307: Bugfix in Preflow and Circulation

          #305: Bugfix and extension in the rename script

          #312: Also check ReferenceMapTag in concept checks

          #250: Bugfix in pathSource() and pathTarget()

          #321: Use pathCopy(from,to) instead of copyPath(to,from)

          #322: Distribure LEMONConfig.cmake.in

          #330: Bug fix in map_extender.h

          #336: Fix the date field comment of graphToEps() output

          #323: Bug fix in Suurballe

          #335: Fix clear() function in ExtendFindEnum

          #337: Use void* as the LPX object pointer

          #317: Fix (and improve) error message in mip_test.cc

                Remove unnecessary OsiCbc dependency

          #356: Allow multiple executions of weighted matching algorithms (#356)

          #214,#215: windows.h should never be included by LEMON headers

        This is the first stable release of LEMON. Compared to the 0.x

        release series, it features a considerably smaller but more

        matured set of tools. The API has also completely revised and

        changed in several places.

        * The major name changes compared to the 0.x series (see the

          * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)

        * Other improvements

          * Better documentation

          * Reviewed and cleaned up codebase

          * CMake based build system (along with the autotools based one)

        * Contents of the library (ported from 0.x)

          * Algorithms

            * breadth-first search (bfs.h)

            * depth-first search (dfs.h)

            * Dijkstra's algorithm (dijkstra.h)

            * Kruskal's algorithm (kruskal.h)

          * Data structures

            * graph data structures (list_graph.h, smart_graph.h)

            * path data structures (path.h)

            * binary heap data structure (bin_heap.h)

            * union-find data structures (unionfind.h)

            * miscellaneous property maps (maps.h)

            * two dimensional vector and bounding box (dim2.h)

            * graph structure concepts (concepts/digraph.h, concepts/graph.h,

            * concepts for other structures (concepts/heap.h, concepts/maps.h,

              concepts/path.h)

          * Tools

            * Mersenne twister random number generator (random.h)

            * tools for measuring cpu and wall clock time (time_measure.h)

            * tools for counting steps and events (counter.h)

            * tool for parsing command line arguments (arg_parser.h)

            * tool for visualizing graphs (graph_to_eps.h)

            * tools for reading and writing data in LEMON Graph Format

              floating point numbers (tolerance.h)

          * Infrastructure

            * extended assertion handling (assert.h)

            * exception classes and error handling (error.h)

            * concept checking (concept_check.h)

            * commonly used mathematical constants (math.h)

- \ref KarpMmc Karp's original algorithm \ref amo93networkflows,

- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved

- \ref HowardMmc Howard's policy iteration algorithm

In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the

most efficient one, though the best known theoretical bound on its running

time is exponential.

Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms

run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is

typically faster due to the applied early termination scheme.

  ///Exception used by ArgParser.

  ///

    /// Reasons for failure

    /// Reasons for failure.

    ///

      HELP,         ///< <tt>--help</tt> option was given.

      UNKNOWN_OPT,  ///< Unknown option was given.

      INVALID_OPT   ///< Invalid combination of options.

  /// \brief Default OperationTraits for the BellmanFord algorithm class.

    /// \e

    /// \see BellmanFordDefaultOperationTraits

    /// \see BellmanFordDefaultOperationTraits

  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.

  /// It is an improved version of \ref KarpMmc "Karp"'s original algorithm,