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