NEWS
author Alpar Juttner <alpar@cs.elte.hu>
Thu, 07 May 2015 11:41:48 +0200
branch1.3
changeset 1149 57a344e446c9
parent 1096 c08d0f04c117
permissions -rw-r--r--
Merge bugfix #473 to branch 1.3
     1 2014-07-07 Version 1.3.1 released
     2 
     3         Bugfix release.
     4 
     5         #484: Require CMAKE 2.8
     6         #471, #472, #480: Various clang compatibility fixes
     7         #481, #482: Fix shared lib build and versioning
     8         #476: Fix invalid map query in NearestNeighborTsp
     9         #478: Bugfix in debug checking and lower bound handling
    10               in min cost flow algorithms
    11         #479, #465: Bugfix in default LP/MIP backend settings
    12         #476: Bugfix in tsp_test
    13         #487: Add missing include header and std:: namespace spec.
    14         #474: Fix division by zero error in NetworkSimplex
    15 
    16 2013-08-10 Version 1.3 released
    17 
    18         This is major feature release
    19 
    20         * New data structures
    21 
    22           #69 : Bipartite graph concepts and implementations
    23 
    24         * New algorithms
    25 
    26           #177: Port Edmonds-Karp algorithm
    27           #380, #405: Heuristic algorithm for the max clique problem
    28           #386: Heuristic algorithms for symmetric TSP
    29           ----: Nagamochi-Ibaraki algorithm [5087694945e4]
    30           #397, #56: Max. cardinality search
    31 
    32         * Other new features
    33 
    34           #223: Thread safe graph and graph map implementations
    35           #442: Different TimeStamp print formats
    36           #457: File export functionality to LpBase
    37           #362: Bidirectional iterator support for radixSort()
    38 
    39         * Implementation improvements
    40 
    41           ----: Network Simplex
    42                 #391: Better update process, pivot rule and arc mixing
    43                 #435: Improved Altering List pivot rule
    44           #417: Various fine tunings in CostScaling
    45           #438: Optional iteration limit in HowardMmc
    46           #436: Ensure strongly polynomial running time for CycleCanceling
    47                 while keeping the same performance
    48           ----: Make the CBC interface be compatible with latest CBC releases
    49                 [ee581a0ecfbf]
    50 
    51         * CMAKE has become the default build environment (#434)
    52 
    53           ----: Autotool support has been dropped
    54           ----: Improved LP/MIP configuration
    55                 #465: Enable/disable options for LP/MIP backends
    56                 #446: Better CPLEX discovery
    57                 #460: Add cmake config to find SoPlex
    58           ----: Allow CPACK configuration on all platforms
    59           #390: Add 'Maintainer' CMAKE build type
    60           #388: Add 'check' target.
    61           #401: Add contrib dir
    62           #389: Better version string setting in CMAKE
    63           #433: Support shared library build    
    64           #416: Support testing with valgrind
    65   
    66         * Doc improvements
    67 
    68           #395: SOURCE_BROWSER Doxygen switch is configurable from CMAKE
    69                 update-external-tags CMAKE target
    70           #455: Optionally use MathJax for rendering the math formulae
    71           #402, #437, #459, #456, #463: Various doc improvements
    72 
    73         * Bugfixes (compared to release 1.2):
    74 
    75           #432: Add missing doc/template.h and doc/references.bib to release
    76                 tarball
    77           ----: Intel C++ compatibility fixes
    78           #441: Fix buggy reinitialization in _solver_bits::VarIndex::clear()
    79           #444: Bugfix in path copy constructors and assignment operators
    80           #447: Bugfix in AllArcLookUp<>
    81           #448: Bugfix in adaptor_test.cc
    82           #449: Fix clang compilation warnings and errors
    83           #440: Fix a bug + remove redundant typedefs in dimacs-solver
    84           #453: Avoid GCC 4.7 compiler warnings
    85           #445: Fix missing initialization in CplexEnv::CplexEnv()
    86           #428: Add missing lemon/lemon.pc.cmake to the release tarball
    87           #393: Create and install lemon.pc
    88           #429: Fix VS warnings
    89           #430: Fix LpBase::Constr two-side limit bug
    90           #392: Bug fix in Dfs::start(s,t)
    91           #414: Fix wrong initialization in Preflow
    92           #418: Better Win CodeBlock/MinGW support
    93           #419: Build environment improvements
    94                 - Build of mip_test and lp_test precede the running of the tests
    95                 - Also search for coin libs under ${COIN_ROOT_DIR}/lib/coin
    96                 - Do not look for COIN_VOL libraries
    97           #382: Allow lgf file without Arc maps
    98           #417: Bug fix in CostScaling
    99           #366: Fix Pred[Matrix]MapPath::empty()
   100           #371: Bug fix in (di)graphCopy()
   101                 The target graph is cleared before adding nodes and arcs/edges.
   102           #364: Add missing UndirectedTags
   103           #368: Fix the usage of std::numeric_limits<>::min() in Network Simplex
   104           #372: Fix a critical bug in preflow
   105           #461: Bugfix in assert.h
   106           #470: Fix compilation issues related to various gcc versions
   107           #446: Fix #define indicating CPLEX availability
   108           #294: Add explicit namespace to
   109                 ignore_unused_variable_warning() usages
   110           #420: Bugfix in IterableValueMap
   111           #439: Bugfix in biNodeConnected()
   112 
   113 
   114 2010-03-19 Version 1.2 released
   115 
   116         This is major feature release
   117 
   118         * New algorithms
   119           * Bellman-Ford algorithm (#51)
   120           * Minimum mean cycle algorithms (#179)
   121             * Karp, Hartman-Orlin and Howard algorithms
   122           * New minimum cost flow algorithms (#180)
   123             * Cost Scaling algorithms
   124             * Capacity Scaling algorithm
   125             * Cycle-Canceling algorithms
   126           * Planarity related algorithms (#62)
   127             * Planarity checking algorithm
   128             * Planar embedding algorithm
   129             * Schnyder's planar drawing algorithm
   130             * Coloring planar graphs with five or six colors
   131           * Fractional matching algorithms (#314)
   132         * New data structures
   133           * StaticDigraph structure (#68)
   134           * Several new priority queue structures (#50, #301)
   135             * Fibonacci, Radix, Bucket, Pairing, Binomial
   136               D-ary and fourary heaps (#301)
   137           * Iterable map structures (#73)
   138         * Other new tools and functionality
   139           * Map utility functions (#320)
   140           * Reserve functions are added to ListGraph and SmartGraph (#311)
   141           * A resize() function is added to HypercubeGraph (#311)
   142           * A count() function is added to CrossRefMap (#302)
   143           * Support for multiple targets in Suurballe using fullInit() (#181)
   144           * Traits class and named parameters for Suurballe (#323)
   145           * Separate reset() and resetParams() functions in NetworkSimplex
   146             to handle graph changes (#327)
   147           * tolerance() functions are added to HaoOrlin (#306)
   148         * Implementation improvements
   149           * Improvements in weighted matching algorithms (#314)
   150             * Jumpstart initialization
   151           * ArcIt iteration is based on out-arc lists instead of in-arc lists
   152             in ListDigraph (#311)
   153           * Faster add row operation in CbcMip (#203)
   154           * Better implementation for split() in ListDigraph (#311)
   155           * ArgParser can also throw exception instead of exit(1) (#332)
   156         * Miscellaneous
   157           * A simple interactive bootstrap script
   158           * Doc improvements (#62,#180,#299,#302,#303,#304,#307,#311,#331,#315,
   159                 #316,#319)
   160             * BibTeX references in the doc (#184)
   161           * Optionally use valgrind when running tests
   162           * Also check ReferenceMapTag in concept checks (#312)
   163           * dimacs-solver uses long long type by default.
   164         * Several bugfixes (compared to release 1.1):
   165           #295: Suppress MSVC warnings using pragmas
   166           ----: Various CMAKE related improvements
   167                 * Remove duplications from doc/CMakeLists.txt
   168                 * Rename documentation install folder from 'docs' to 'html'
   169                 * Add tools/CMakeLists.txt to the tarball
   170                 * Generate and install LEMONConfig.cmake
   171                 * Change the label of the html project in Visual Studio
   172                 * Fix the check for the 'long long' type
   173                 * Put the version string into config.h
   174                 * Minor CMake improvements
   175                 * Set the version to 'hg-tip' if everything fails
   176           #311: Add missing 'explicit' keywords
   177           #302: Fix the implementation and doc of CrossRefMap
   178           #308: Remove duplicate list_graph.h entry from source list
   179           #307: Bugfix in Preflow and Circulation
   180           #305: Bugfix and extension in the rename script
   181           #312: Also check ReferenceMapTag in concept checks
   182           #250: Bugfix in pathSource() and pathTarget()
   183           #321: Use pathCopy(from,to) instead of copyPath(to,from)
   184           #322: Distribure LEMONConfig.cmake.in
   185           #330: Bug fix in map_extender.h
   186           #336: Fix the date field comment of graphToEps() output
   187           #323: Bug fix in Suurballe
   188           #335: Fix clear() function in ExtendFindEnum
   189           #337: Use void* as the LPX object pointer
   190           #317: Fix (and improve) error message in mip_test.cc
   191                 Remove unnecessary OsiCbc dependency
   192           #356: Allow multiple executions of weighted matching algorithms (#356)
   193 
   194 2009-05-13 Version 1.1 released
   195 
   196         This is the second stable release of the 1.x series. It
   197         features a better coverage of the tools available in the 0.x
   198         series, a thoroughly reworked LP/MIP interface plus various
   199         improvements in the existing tools.
   200 
   201         * Much improved M$ Windows support
   202           * Various improvements in the CMAKE build system
   203           * Compilation warnings are fixed/suppressed
   204         * Support IBM xlC compiler
   205         * New algorithms
   206           * Connectivity related algorithms (#61)
   207           * Euler walks (#65)
   208           * Preflow push-relabel max. flow algorithm (#176)
   209           * Circulation algorithm (push-relabel based) (#175)
   210           * Suurballe algorithm (#47)
   211           * Gomory-Hu algorithm (#66)
   212           * Hao-Orlin algorithm (#58)
   213           * Edmond's maximum cardinality and weighted matching algorithms
   214             in general graphs (#48,#265)
   215           * Minimum cost arborescence/branching (#60)
   216           * Network Simplex min. cost flow algorithm (#234)
   217         * New data structures
   218           * Full graph structure (#57)
   219           * Grid graph structure (#57)
   220           * Hypercube graph structure (#57)
   221           * Graph adaptors (#67)
   222           * ArcSet and EdgeSet classes (#67)
   223           * Elevator class (#174)
   224         * Other new tools
   225           * LP/MIP interface (#44)
   226             * Support for GLPK, CPLEX, Soplex, COIN-OR CLP and CBC
   227           * Reader for the Nauty file format (#55)
   228           * DIMACS readers (#167)
   229           * Radix sort algorithms (#72)
   230           * RangeIdMap and CrossRefMap (#160)
   231         * New command line tools
   232           * DIMACS to LGF converter (#182)
   233           * lgf-gen - a graph generator (#45)
   234           * DIMACS solver utility (#226)
   235         * Other code improvements
   236           * Lognormal distribution added to Random (#102)
   237           * Better (i.e. O(1) time) item counting in SmartGraph (#3)
   238           * The standard maps of graphs are guaranteed to be
   239             reference maps (#190)
   240         * Miscellaneous
   241           * Various doc improvements
   242           * Improved 0.x -> 1.x converter script
   243 
   244         * Several bugfixes (compared to release 1.0):
   245           #170: Bugfix SmartDigraph::split()
   246           #171: Bugfix in SmartGraph::restoreSnapshot()
   247           #172: Extended test cases for graphs and digraphs
   248           #173: Bugfix in Random
   249                 * operator()s always return a double now
   250                 * the faulty real<Num>(Num) and real<Num>(Num,Num)
   251                   have been removed
   252           #187: Remove DijkstraWidestPathOperationTraits
   253           #61:  Bugfix in DfsVisit
   254           #193: Bugfix in GraphReader::skipSection()
   255           #195: Bugfix in ConEdgeIt()
   256           #197: Bugfix in heap unionfind
   257                 * This bug affects Edmond's general matching algorithms
   258           #207: Fix 'make install' without 'make html' using CMAKE
   259           #208: Suppress or fix VS2008 compilation warnings
   260           ----: Update the LEMON icon
   261           ----: Enable the component-based installer
   262                 (in installers made by CPACK)
   263           ----: Set the proper version for CMAKE in the tarballs
   264                 (made by autotools)
   265           ----: Minor clarification in the LICENSE file
   266           ----: Add missing unistd.h include to time_measure.h
   267           #204: Compilation bug fixed in graph_to_eps.h with VS2005
   268           #214,#215: windows.h should never be included by LEMON headers
   269           #230: Build systems check the availability of 'long long' type
   270           #229: Default implementation of Tolerance<> is used for integer types
   271           #211,#212: Various fixes for compiling on AIX
   272           ----: Improvements in CMAKE config
   273                 - docs is installed in share/doc/
   274                 - detects newer versions of Ghostscript
   275           #239: Fix missing 'inline' specifier in time_measure.h
   276           #274,#280: Install lemon/config.h
   277           #275: Prefix macro names with LEMON_ in lemon/config.h
   278           ----: Small script for making the release tarballs added
   279           ----: Minor improvement in unify-sources.sh (a76f55d7d397)
   280 
   281 2009-03-27 LEMON joins to the COIN-OR initiative
   282 
   283         COIN-OR (Computational Infrastructure for Operations Research,
   284         http://www.coin-or.org) project is an initiative to spur the
   285         development of open-source software for the operations research
   286         community.
   287 
   288 2008-10-13 Version 1.0 released
   289 
   290         This is the first stable release of LEMON. Compared to the 0.x
   291         release series, it features a considerably smaller but more
   292         matured set of tools. The API has also completely revised and
   293         changed in several places.
   294 
   295         * The major name changes compared to the 0.x series (see the
   296           Migration Guide in the doc for more details)
   297           * Graph -> Digraph, UGraph -> Graph
   298           * Edge -> Arc, UEdge -> Edge
   299           * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
   300         * Other improvements
   301           * Better documentation
   302           * Reviewed and cleaned up codebase
   303           * CMake based build system (along with the autotools based one)
   304         * Contents of the library (ported from 0.x)
   305           * Algorithms
   306             * breadth-first search (bfs.h)
   307             * depth-first search (dfs.h)
   308             * Dijkstra's algorithm (dijkstra.h)
   309             * Kruskal's algorithm (kruskal.h)
   310           * Data structures
   311             * graph data structures (list_graph.h, smart_graph.h)
   312             * path data structures (path.h)
   313             * binary heap data structure (bin_heap.h)
   314             * union-find data structures (unionfind.h)
   315             * miscellaneous property maps (maps.h)
   316             * two dimensional vector and bounding box (dim2.h)
   317           * Concepts
   318             * graph structure concepts (concepts/digraph.h, concepts/graph.h,
   319               concepts/graph_components.h)
   320             * concepts for other structures (concepts/heap.h, concepts/maps.h,
   321               concepts/path.h)
   322           * Tools
   323             * Mersenne twister random number generator (random.h)
   324             * tools for measuring cpu and wall clock time (time_measure.h)
   325             * tools for counting steps and events (counter.h)
   326             * tool for parsing command line arguments (arg_parser.h)
   327             * tool for visualizing graphs (graph_to_eps.h)
   328             * tools for reading and writing data in LEMON Graph Format
   329               (lgf_reader.h, lgf_writer.h)
   330             * tools to handle the anomalies of calculations with
   331               floating point numbers (tolerance.h)
   332             * tools to manage RGB colors (color.h)
   333           * Infrastructure
   334             * extended assertion handling (assert.h)
   335             * exception classes and error handling (error.h)
   336             * concept checking (concept_check.h)
   337             * commonly used mathematical constants (math.h)