NEWS
author Balazs Dezso <deba@inf.elte.hu>
Thu, 24 Jun 2010 09:27:53 +0200
changeset 891 bb70ad62c95f
parent 507 4f3ea453eb90
child 881 87569cb5734d
permissions -rw-r--r--
Fix critical bug in preflow (#372)

The wrong transition between the bound decrease and highest active
heuristics caused the bug. The last node chosen in bound decrease mode
is used in the first iteration in highest active mode.
alpar@665
     1
2009-05-13 Version 1.1 released
alpar@665
     2
alpar@665
     3
        This is the second stable release of the 1.x series. It
alpar@665
     4
        features a better coverage of the tools available in the 0.x
alpar@665
     5
        series, a thoroughly reworked LP/MIP interface plus various
alpar@665
     6
        improvements in the existing tools.
alpar@665
     7
alpar@665
     8
        * Much improved M$ Windows support
alpar@665
     9
          * Various improvements in the CMAKE build system
alpar@665
    10
          * Compilation warnings are fixed/suppressed
alpar@665
    11
        * Support IBM xlC compiler
alpar@665
    12
        * New algorithms
alpar@665
    13
          * Connectivity related algorithms (#61)
alpar@665
    14
          * Euler walks (#65)
alpar@665
    15
          * Preflow push-relabel max. flow algorithm (#176)
alpar@665
    16
          * Circulation algorithm (push-relabel based) (#175)
alpar@665
    17
          * Suurballe algorithm (#47)
alpar@665
    18
          * Gomory-Hu algorithm (#66)
alpar@665
    19
          * Hao-Orlin algorithm (#58)
alpar@665
    20
          * Edmond's maximum cardinality and weighted matching algorithms
alpar@665
    21
            in general graphs (#48,#265)
alpar@665
    22
          * Minimum cost arborescence/branching (#60)
alpar@665
    23
          * Network Simplex min. cost flow algorithm (#234)
alpar@665
    24
        * New data structures
alpar@665
    25
          * Full graph structure (#57)
alpar@665
    26
          * Grid graph structure (#57)
alpar@665
    27
          * Hypercube graph structure (#57)
alpar@665
    28
          * Graph adaptors (#67)
alpar@665
    29
          * ArcSet and EdgeSet classes (#67)
alpar@665
    30
          * Elevator class (#174)
alpar@665
    31
        * Other new tools
alpar@665
    32
          * LP/MIP interface (#44)
alpar@665
    33
            * Support for GLPK, CPLEX, Soplex, COIN-OR CLP and CBC
alpar@665
    34
          * Reader for the Nauty file format (#55)
alpar@665
    35
          * DIMACS readers (#167)
alpar@665
    36
          * Radix sort algorithms (#72)
alpar@665
    37
          * RangeIdMap and CrossRefMap (#160)
alpar@665
    38
        * New command line tools
alpar@665
    39
          * DIMACS to LGF converter (#182)
alpar@665
    40
          * lgf-gen - a graph generator (#45)
alpar@665
    41
          * DIMACS solver utility (#226)
alpar@665
    42
        * Other code improvements
alpar@665
    43
          * Lognormal distribution added to Random (#102)
alpar@665
    44
          * Better (i.e. O(1) time) item counting in SmartGraph (#3)
alpar@665
    45
          * The standard maps of graphs are guaranteed to be
alpar@665
    46
            reference maps (#190)
alpar@665
    47
        * Miscellaneous
alpar@665
    48
          * Various doc improvements
alpar@665
    49
          * Improved 0.x -> 1.x converter script
alpar@665
    50
alpar@665
    51
        * Several bugfixes (compared to release 1.0):
alpar@665
    52
          #170: Bugfix SmartDigraph::split()
alpar@665
    53
          #171: Bugfix in SmartGraph::restoreSnapshot()
alpar@665
    54
          #172: Extended test cases for graphs and digraphs
alpar@665
    55
          #173: Bugfix in Random
alpar@665
    56
                * operator()s always return a double now
alpar@665
    57
                * the faulty real<Num>(Num) and real<Num>(Num,Num)
alpar@665
    58
                  have been removed
alpar@665
    59
          #187: Remove DijkstraWidestPathOperationTraits
alpar@665
    60
          #61:  Bugfix in DfsVisit
alpar@665
    61
          #193: Bugfix in GraphReader::skipSection()
alpar@665
    62
          #195: Bugfix in ConEdgeIt()
alpar@665
    63
          #197: Bugfix in heap unionfind
alpar@665
    64
                * This bug affects Edmond's general matching algorithms
alpar@665
    65
          #207: Fix 'make install' without 'make html' using CMAKE
alpar@665
    66
          #208: Suppress or fix VS2008 compilation warnings
alpar@665
    67
          ----: Update the LEMON icon
alpar@665
    68
          ----: Enable the component-based installer
alpar@665
    69
                (in installers made by CPACK)
alpar@665
    70
          ----: Set the proper version for CMAKE in the tarballs
alpar@665
    71
                (made by autotools)
alpar@665
    72
          ----: Minor clarification in the LICENSE file
alpar@665
    73
          ----: Add missing unistd.h include to time_measure.h
alpar@665
    74
          #204: Compilation bug fixed in graph_to_eps.h with VS2005
alpar@665
    75
          #214,#215: windows.h should never be included by lemon headers
alpar@665
    76
          #230: Build systems check the availability of 'long long' type
alpar@665
    77
          #229: Default implementation of Tolerance<> is used for integer types
alpar@665
    78
          #211,#212: Various fixes for compiling on AIX
alpar@665
    79
          ----: Improvements in CMAKE config
alpar@665
    80
                - docs is installed in share/doc/
alpar@665
    81
                - detects newer versions of Ghostscript
alpar@665
    82
          #239: Fix missing 'inline' specifier in time_measure.h
alpar@665
    83
          #274,#280: Install lemon/config.h
alpar@665
    84
          #275: Prefix macro names with LEMON_ in lemon/config.h
alpar@665
    85
          ----: Small script for making the release tarballs added
alpar@665
    86
          ----: Minor improvement in unify-sources.sh (a76f55d7d397)
alpar@665
    87
alpar@507
    88
2009-03-27 LEMON joins to the COIN-OR initiative
alpar@507
    89
alpar@507
    90
        COIN-OR (Computational Infrastructure for Operations Research,
alpar@507
    91
        http://www.coin-or.org) project is an initiative to spur the
alpar@507
    92
        development of open-source software for the operations research
alpar@507
    93
        community.
alpar@507
    94
alpar@322
    95
2008-10-13 Version 1.0 released
alpar@262
    96
alpar@262
    97
	This is the first stable release of LEMON. Compared to the 0.x
alpar@262
    98
	release series, it features a considerably smaller but more
alpar@262
    99
	matured set of tools. The API has also completely revised and
alpar@262
   100
	changed in several places.
alpar@262
   101
alpar@322
   102
	* The major name changes compared to the 0.x series (see the
alpar@322
   103
          Migration Guide in the doc for more details)
alpar@262
   104
          * Graph -> Digraph, UGraph -> Graph
alpar@262
   105
          * Edge -> Arc, UEdge -> Edge
alpar@262
   106
	  * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
alpar@262
   107
	* Other improvements
alpar@262
   108
	  * Better documentation
alpar@262
   109
	  * Reviewed and cleaned up codebase
alpar@262
   110
	  * CMake based build system (along with the autotools based one)
alpar@262
   111
	* Contents of the library (ported from 0.x)
alpar@262
   112
	  * Algorithms
alpar@262
   113
       	    * breadth-first search (bfs.h)
alpar@262
   114
       	    * depth-first search (dfs.h)
alpar@262
   115
       	    * Dijkstra's algorithm (dijkstra.h)
alpar@262
   116
       	    * Kruskal's algorithm (kruskal.h)
alpar@262
   117
    	  * Data structures
alpar@262
   118
       	    * graph data structures (list_graph.h, smart_graph.h)
alpar@262
   119
       	    * path data structures (path.h)
alpar@262
   120
       	    * binary heap data structure (bin_heap.h)
alpar@262
   121
       	    * union-find data structures (unionfind.h)
alpar@262
   122
       	    * miscellaneous property maps (maps.h)
alpar@262
   123
       	    * two dimensional vector and bounding box (dim2.h)
alpar@262
   124
          * Concepts
alpar@262
   125
       	    * graph structure concepts (concepts/digraph.h, concepts/graph.h,
alpar@262
   126
              concepts/graph_components.h)
alpar@262
   127
       	    * concepts for other structures (concepts/heap.h, concepts/maps.h,
alpar@262
   128
	      concepts/path.h)
alpar@262
   129
    	  * Tools
alpar@262
   130
       	    * Mersenne twister random number generator (random.h)
alpar@262
   131
       	    * tools for measuring cpu and wall clock time (time_measure.h)
alpar@262
   132
       	    * tools for counting steps and events (counter.h)
alpar@262
   133
       	    * tool for parsing command line arguments (arg_parser.h)
alpar@262
   134
       	    * tool for visualizing graphs (graph_to_eps.h)
alpar@262
   135
       	    * tools for reading and writing data in LEMON Graph Format
alpar@262
   136
              (lgf_reader.h, lgf_writer.h)
alpar@262
   137
            * tools to handle the anomalies of calculations with
alpar@262
   138
	      floating point numbers (tolerance.h)
alpar@262
   139
            * tools to manage RGB colors (color.h)
alpar@262
   140
    	  * Infrastructure
alpar@262
   141
       	    * extended assertion handling (assert.h)
alpar@262
   142
       	    * exception classes and error handling (error.h)
alpar@262
   143
      	    * concept checking (concept_check.h)
alpar@262
   144
       	    * commonly used mathematical constants (math.h)