2006-10-27  Version 0.6 Released

#New

  *functor usage for writeable map adaptors

  *MIP support

    -interface to the cplex MIP solver

  *data structures

    -ListBpUGraph

    -SmartEdgeset

    -RefPtr: a reference counted pointer class

    -two state variant

    -Polinomial template class

    -SimpleBucketHeap  

      -even a smaller version

    -tolerance class

      -Tolerance<unsigned int> and Tolerance<unsigned long long int> added

    -the extender system

      -some UGraphExtender /SubUGraphExtenders, DirectUGraphExtender/

    -adaptor related

      -ResGraphAdaptor with Tolerance

      -SwapBpUGraphAdaptor which swaps the two nodeset of the bipartite graph

    -map related

      -SimpleMap and SimpleWriteMap

      -new map type based on array map for debugging purpose

      -DynamicAsymMatrixMap

      -MatrixMapTraits

  *functions

    -optimality test on random graph

    -implementation of the drand48 functions

    -negative cycle to path converter

    -reserveNode function

    -Mersenne Twister random number generator

    -EdgeLookUp and AllEdgeLookUp

  *scripts

    -script that lists all the header files included directly or indirectly by a certain header file

    -script creates/updates the copyright header of a source file

  *algorithms

    -algorithm group for matchings

      -Bipartite Graph Max Cardinality Matching (Hopcroft-Karp)

      -MaxWeightedBipartiteMatching

      -MinCostMaxBipartiteMatching

    -MaxCardinalitySearch

    -MinimalCut in UGraph

    -tabu search

    -Minimum Cost Arborescence algorithm 

      -dual solution computation and interface for algorithm

      -Edmonds-Karp MaxFlow

    -Hao-Orlin algorithm

#Progress in already existing objects:

  *radix sort to ansi compatible

  *map creation based on virtual base class is possible

  *default constructor which allocates empty graphs

  *defaultMap is introdouced, graph maps should not be inherited from the ObserverBase.

  *clarifing alteration observing system

  *resize for static size graph

  *an additional simplier interface for static size graphs.

  *Node operator()(int) for getting node by index

  *int index(Node node) for getting index by node

  *traits for alteration notifiers

  *graph adadptors can be alteration observed

  *count ANodes-BNodes in bipartite graphs

  *the template assign operators and map iterators can be used for adaptors also

  *writeable extension of some maps

  *rot180() added to xy.h

  *change source and target for the bipartite list graph

  *findEdge extension also for the BpUGraphs

  *proper handling of loop edges in the UGraph::findUEdge

  *exported interface to the Graph class

  *new random interface

  *graph imlementations actually provide ReferenceMaps

  *lgf2ps:

    -RGB color related stuff is in color.h now

    -simple class to create .eps figures (eps.h)

    -"Node shapes" added

    -some color constants added (BLACK, WHITE, RED etc)

    -absolute/relative node size/link width scaling

#Taken out:

  *SplitGraph is temporarly deleted

  *SubBidirGraphAdaptor

  *obsolote "id" map handling

  *concepts for extendable and erasable graphs

  *exceptionName()

  *bezier.h

  *functional interfaces

  *UPath

#Rewritten, modificated, improved

  *UnionFindEnum revision

  *countItems

  *findEdges

  *IncEdgeIt goes through on loop edges twice.

  *mining of the clear in heaps

  *SplitGraphAdaptor

  *item sets are written in the order sorted by the labels

  *make explicit constructors

  *snapshot

    -rewritten

    -implemented for SmartUGraph an SmartBpUGraph

  *Node/Edge::operator<() is required by the concept

  *Graph Component concepts

  *disabled the copy constructor and operator- of {List|Smart}[U]Graph.

  *modificated interface: colType() functions

  *made public what() in NodeSetError

  *improvment in exception handling

    -exception safe erase and clear handler

    -proper exception handling in the SmartEdgeSet

    -rethrow of exception missing 

  *signaling alterations in BpUGraphs

  *UnionFind

    -takes less space

    -UnionFindEnum

      -changed interface

  *updated the Path concept

  *item readers and writers

#Reorganized:

  *bootstrap: quiet option

  *utility, invalid and traits moved to bits

  *section readers moved to own group

  *separate group for matrices

  *single makefile

  *glemon is moved to own repository

  *graph_component.h -> graph_components.h

  *reference to modules added

  *disable assertions in default behaviour

  *BiVariant moved to lemon/bits/variant.h

  *using abort() instead of exit(1)

#Renamed:

  *Undir -> U

  *Minimum -> Min

  *Work -> Aux

  *UGraphExtender -> UndirectGraphExtender

    -UGraphExtenders with changed meaning

  *GridGraph -> GridUGraph

  *UNDIRGRAPH_TYPEDEFS -> UGRAPH_TYPEDEFS

  *LinearHeap -> BucketHeap

  *UGraphBaseExtender -> UndirGraphExtender

  *BpUGraphBaseExtender merged into BpUGraphExtender

  *StaticGraph to Graph

  *ColorSet to Palette

  *xy -> dim2::Point

  *DirPath to Path

  *concept -> concepts (namespace & directory)

#Compatibility issues:

  *compilation with G++ -ansi

  *gcc-4.1

  *NaN checking to be conform to MinGW32

  *MinGW, MinGW32

  *long long just for gnu compilers

  *CPLEX 9.x support

  *turned off 32bit specific tests.

#Beyond the aboves several bugfix and documentation improvement is made, new demos, benchmarks are implemented.

2006-02-03  Version 0.5 Released

	* New features:

	  - Bfs/Dfs/Dijkstra

	    + query functions for the next node/edge to be processed

	    + visitor interface for dfs

	  - topology.h: small functions for discovering graph topology

	    + connected components, strongly connected components

	    + bipartiteness testing

	  - Shortest paths algorithms:

	    bellman_ford.h, floyd_warshall.h, johnson.h

	  - Euler tour iterator for directed and undirected graphs

	  - Other algorithms:

	    + dag_shortest_path.h

	    + fredman_tarjan.h and prim.h for min cost trees

	  - Bipartite graph concept and implementations

	  - Graph maps:

	    + template assign operator

	    + specialized iterable bool map

	    + potential difference map

	    + NodeMatrixMap -- Matrix over the nodes

	  - Maps:

	    + IterableIntMap

	  - GUI:

	    + NewMap window in MapSelector

	    + Algorithm window and some algorithms (eg. Kruskal) added

	  - LemonReader:

	    + exception on non-existent files

	  - LP interface:

	    + (Dual)Expr::simplify(double tolerance) added

	    + getDual()

	  - GraphToEps:

	    + negateY() opt

	    + male/female node shapes :)

	    + correct %%BoundingBox handling

	  - Tools:

	    + Timer can be stop()ed and (re)start()ed

	    + radix sort algorithm

	    + tolerance.h for working with imprecise numbers

	* Backward incompatibilities/changed namings:

	  - Access functions of TimeStamp/Timer

	  - Undir graph interface: findUEdge, ConUEdgeIt

	  - pred -> predEdge renaming in search algorithms

	  - SnapShot -> Snapshot in {List,Smart}Graph

	  - NewEdgeSetAdaptor -> ListEdgeSet

	  - LP: set{Obj,Row,Col}() -> {obj,row,col}()

	  - "label" instead of "id" inside the LGF files

	  - UndirGraph -> UGraph, UndirEdge* -> UEdge*

	  - BipartiteGraph -> BpGraph, Lower/UpperNode* -> A/BNode*

	* Bugfixes in

	  - DFS

	  - Preflow

	  - x86_64 connected bugfixes (lemon_reader.h)

	  - lp.h

	* New demos, benchmarks and tools:

	  - graph_orientation.cc: A thoroughly documented demo application

	  - runningTimeTest(): a tool to measure running times more precisely

	  - Demo for topology

	  - counter.h: a tool to measure the number of steps of algorithms

	  - Some useful scripts: check-compiler, check-integrity

	* Other changes:

	  - Demos and benchmarks are not built by default now. They can be

	    enabled with the --enable-demo and --enable-benchmark

	    configure flags.

	  - GCC 4.0.3 and ICC 9.0 compatibility

2005-08-27  Version 0.4 Released

	* List of new features and changes	

	  * Changed namings:

	    Wrapper -> Adaptor

	    kruskalEdgeMap() -> kruskal()

	    kruskalEdgeMap_IteratorOut() -> kruskal()

	  * BoundinBox<>

	    * operator+=() -> add()

	    + clear()

	  + More and better graph I/O functionalities

	  + High level uniform LP solver interface to CPLEX and GLKP

	  * graphToEps()

	    + Automatic node size and edge width scaling

	    + Simple color palette tool (ColorSet)

	  * Bfs/Dfs/Dijkstra

	    + Step-by-step execution

	    + Run from multiple sources

	    + Used define stop condition

	    + Improved "named parameters"

	  * Preflow

	    + Function type interface

	    + Changed interface

	  * ListGraph/SmarGraph

	    + split() splits a node

	    + SnapShot

	  + New map adaptors

	  + New convenience maps

	    + IdMap, DescriptorMap

	    + InDegMap, OutDegMap

	    + XMap, YMap

	  + Default graph maps are iterable

	  + glemon: a graph editor

	  + Some new demo codes added, the old ones got polished.

	  * Better documentation

	  * Several important bugfixes

	  * Now lemon should compile without warnings with

	    * gcc 3.3, 3.4, 4.0

	    * Intel C++ Compiler v9.0 

2005-03-19  Version 0.3.1 Released

	* This release fixes a compilation failure bug under cygwin. 

2005-02-21  Version 0.3 released

	* List of new features and changes	

	  * Redesigned Graph infrastructures

	  + Standardized LEMON exceptions

	  + Undirected Graph

	  + Standard graph file format, input and output classes for it.

	  * head() -> target(), tail() -> source()

	  * Some standard namings have changes:

	    ValueType -> Value, 

	    KeyType -> Key,

	    ReferenceType ->Reference,

	    PointerType -> Pointer

	  + GraphToEps: A simple graph drawer

	  * Better documentation

2004-09-30  Version 0.2 released