NEWS
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
parent 262 0181b7f12a2a
child 496 4f3ea453eb90
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).
alpar@322
     1
2008-10-13 Version 1.0 released
alpar@262
     2
alpar@262
     3
	This is the first stable release of LEMON. Compared to the 0.x
alpar@262
     4
	release series, it features a considerably smaller but more
alpar@262
     5
	matured set of tools. The API has also completely revised and
alpar@262
     6
	changed in several places.
alpar@262
     7
alpar@322
     8
	* The major name changes compared to the 0.x series (see the
alpar@322
     9
          Migration Guide in the doc for more details)
alpar@262
    10
          * Graph -> Digraph, UGraph -> Graph
alpar@262
    11
          * Edge -> Arc, UEdge -> Edge
alpar@262
    12
	  * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
alpar@262
    13
	* Other improvements
alpar@262
    14
	  * Better documentation
alpar@262
    15
	  * Reviewed and cleaned up codebase
alpar@262
    16
	  * CMake based build system (along with the autotools based one)
alpar@262
    17
	* Contents of the library (ported from 0.x)
alpar@262
    18
	  * Algorithms
alpar@262
    19
       	    * breadth-first search (bfs.h)
alpar@262
    20
       	    * depth-first search (dfs.h)
alpar@262
    21
       	    * Dijkstra's algorithm (dijkstra.h)
alpar@262
    22
       	    * Kruskal's algorithm (kruskal.h)
alpar@262
    23
    	  * Data structures
alpar@262
    24
       	    * graph data structures (list_graph.h, smart_graph.h)
alpar@262
    25
       	    * path data structures (path.h)
alpar@262
    26
       	    * binary heap data structure (bin_heap.h)
alpar@262
    27
       	    * union-find data structures (unionfind.h)
alpar@262
    28
       	    * miscellaneous property maps (maps.h)
alpar@262
    29
       	    * two dimensional vector and bounding box (dim2.h)
alpar@262
    30
          * Concepts
alpar@262
    31
       	    * graph structure concepts (concepts/digraph.h, concepts/graph.h,
alpar@262
    32
              concepts/graph_components.h)
alpar@262
    33
       	    * concepts for other structures (concepts/heap.h, concepts/maps.h,
alpar@262
    34
	      concepts/path.h)
alpar@262
    35
    	  * Tools
alpar@262
    36
       	    * Mersenne twister random number generator (random.h)
alpar@262
    37
       	    * tools for measuring cpu and wall clock time (time_measure.h)
alpar@262
    38
       	    * tools for counting steps and events (counter.h)
alpar@262
    39
       	    * tool for parsing command line arguments (arg_parser.h)
alpar@262
    40
       	    * tool for visualizing graphs (graph_to_eps.h)
alpar@262
    41
       	    * tools for reading and writing data in LEMON Graph Format
alpar@262
    42
              (lgf_reader.h, lgf_writer.h)
alpar@262
    43
            * tools to handle the anomalies of calculations with
alpar@262
    44
	      floating point numbers (tolerance.h)
alpar@262
    45
            * tools to manage RGB colors (color.h)
alpar@262
    46
    	  * Infrastructure
alpar@262
    47
       	    * extended assertion handling (assert.h)
alpar@262
    48
       	    * exception classes and error handling (error.h)
alpar@262
    49
      	    * concept checking (concept_check.h)
alpar@262
    50
       	    * commonly used mathematical constants (math.h)