2008-02-08 Version 0.7 released
New Features
+ new data structures
* classes
StaticGraph
ExtendFindEnum
BfsVisitor class
Bipartite partitions based on visitors
* helper class for checking existence of a nested class
* general mapping based variant type
* IntegerMap
+ new algoritmhs
* Lagrange relaxation based algorithm for the delay constrained least cost path problem
* a preflow based general network circulation algorithm
* 2-approximation of Steiner-tree problem
* two heuristics for minimum cut algorithms (http://www.avglab.com/andrew/pub/neci-tr-96-132.ps)
* Gomory-Hu tree algorithm
* Edmond's Blossom shrinking algorithm
* minimum mean cycle algorithm
* Goldberg-Tarjan algorithm (Preflow with Dynamic Trees)
* Dinitz-Sleator-Tarjan (Blocking flow with Dynamic Tree)
* min cost flow algorithms:
* successive shortest path algorithm
* capacity scaling algorithm
* simple cycle canceling algorithm
* minimum mean cycle canceling algorithm
* cost scaling algorithm
* network simplex algorithm
* min cost maximum flow algorithm
+ new functions and tools
* ArgParser, a command line argument parser
* DistLog, a tool for measuring one and two dimensional distributions
* undirected minimum cut benchmarking
* tools/lgf-gen.cc, a random graph generator
* BpUGraphReader and Writer
* DynEdgeLookUp implementation based on splay trees
* MACROS for debug map usage
+ new distributions (Gaussian, exponential, Gamma, two dimensional random, buffered bit generation)
+ push-relabel type algorithm related additions
* Elevator, a class for handling item labels in push-relabel type algorithms
* a push/relabel type max cardinality matching implementation
* some query function for push-relabel based matching
+ LP related additions
* Soplex support
* ColIt class
* new functions (simplify(), isFinite(), row and col getter function)
* _setColCoeff and _setRowCoeff parameters
* section reader and writer for LEMON IO
* equality-type constraint can now be added to a LP
* virtual functions of class LpCplex
* some query functions for GLPK
+ demos
* preflow based general network circulation demo
* Steiner 2-approximation demo
* demo for SAT problems
* sample input for sat-2 and sat demos
+ tests for
* graph copies
* random.h
* max weighted matchings
+ planarity related additions
* checking and embedding
* planar grid embedding
* planar graph coloring
+ bipartite matchings
* common interface
* Query functions: aMatching and bMatching
* ANodeMap matching map
* BNodeMap barrier map
Repository reorganization
* script for automatic checking of SVN commit's consistency
* automatic doc generation from the SVN trunk
* check for gcc version 3.3, 3.4, 4.0 and 4.1.2 as well
* reorganization of the modules and groups
* a tools directory added for useful executables codes
* doxygen
* renaming topology doxygen group to graph_prop doxygen group
* introducing planar doxygen group
Changes
* redesigned
* undirected edgesets (like the smart graph or ugraph)
* interface of MaxMatching and UnionFindEnum
* interface of maximum flow algorithms
* Kruskal algorithm
* augmenting path based bipartite matching
Improvements
* graph copy
* preliminary support for static graphs
* added BpUGraphCopy
* Bfs/Dfs/Dijkstra
* conditional execution until the target is reached
* modified start() function in Dfs and Dijkstra classes to give back reached edge/node
* return the temporary distance of the current node
* using operation traits in Dijkstra
* patch for retrieving reached/processed node
* prescaling can be turned off in GraphToEps
* better handling of inexact computations
* easier inverse
* faster geometric minimum spanning tree algorithm
* new implementation of undirected graphs
* Hao-Orlin algorithm became epsilon-safe
* LpSoplex
* added getter functions
* better m4 file
* better handling of unsolved lps
* allowing 'string' type quoting for item reading and writing
* clear() function for union-find structures
* hacking MIP is possible without integer variables
* space reservation for SmartGraph
* path
* PathNodeIt
PathWriter/Reader structures
Distinct MapSet readers and writers
* more simple interface for PathDumper
Updated
* tutorial for
* algorithms
* graph visualization
* documentation
Backward incompatibilities/changed namings
* min_cut.h => nagamochi_ibaraki.h
* clone => build
* RevIt => RevEdgeIt
* _FixId => LpId
* setObj => obj
* is_min => isMin
* is_max => isMax
* ball2() => disc()
* state_enum => State
* getNotifier => notifier
* using LEMON_ASSERT instead of LogicError()
* uedgeset is an alias for edgeset
* CPXMIP_OPTIMAL_TOL status is considered as OPTIMAL too
* removed "Type" suffix from typedefs
* lower case local variables
Removed
- SspMinCostFlow
- template Map template parameter from InvertableMaps
- union-find Item template parameter
- strict checking
- some automatic callback generation
- '-Wshadow' seemed too strict therefore removed
Several bugfixes
2006-10-31 Version 0.6 Released
GLEMON has moved to a separate repository
(https://hugo.cs.elte.hu/svn/glemon/trunk)
New Features
+ Mixed Integer Programming (MIP) support
+ interface to GLPK and CPLEX MIP solvers
+ Data structures
* Bipatrite graph concepts and implementations
* a Polinomial template class
* RefPtr: a reference counted pointer class
* SimpleBucketHeap
+ random.h: Mersenne Twister random number generator
+ EdgeLookUp and AllEdgeLookUp
+ Tools to find edges between to nodes in time O(log d)
+ new matching algorithms
+ Bipartite Graph Max Cardinality Matching (Hopcroft-Karp)
+ MaxWeightedBipartiteMatching
+ MinCostMaxBipartiteMatching
+ MaxCardinalitySearch
+ MinimalCut in UGraph
+ Tabu Search framework
+ Minimum Cost Arborescence algorithm
+ Edmonds-Karp MaxFlow
+ Hao-Orlin algorithm
+ eps.h: A simple tool to create .eps pictures.
Backward incompatibilities/changed namings:
* UndirXyz -> UXyz
* UNDIRGRAPH_TYPEDEFS -> UGRAPH_TYPEDEFS
* GridGraph -> GridUGraph
* LinearHeap -> BucketHeap
* ColorSet -> Palette
* xy -> dim2::Point
* DirPath -> Path
* concept -> concepts (namespace & directory)
* LpSolverBase
* ColName() -> colName
* Coeff() -> coeff()
* MinCostFlow -> SspMinCostFlow
Repository reorganization:
* compilation is conducted by a single makefile
* internal building blocks are now in a separate directory
(lemon/bits)
Major improvements of many algorithms and data structures
Several bugfixes
Compatibility issues:
* known to compile with
* GCC 3.3, 3.4, 4.0, 4.1
* MinGW, MinGW32
* Intel C++ 9.x support
2006-02-03 Version 0.5 Released
New features
+ 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
+ Tools:
* Timer can be stop()ed and (re)start()ed
* radix sort algorithm
* tolerance.h for working with imprecise numbers
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
Improvements
+ 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
+ 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
Backward incompatibilities/changed namings:
* Access functions of TimeStamp/Timer
* Undirected 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
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
New features
+ More and better graph I/O functionalities
+ High level uniform LP solver interface to CPLEX and GLKP
+ 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.
Improvements
+ 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
* Changed interface
* Function type interface
+ ListGraph/SmartGraph
* split() splits a node
* SnapShot
Changes
* Changed namings:
* Wrapper -> Adaptor
* kruskalEdgeMap() -> kruskal()
* kruskalEdgeMap_IteratorOut() -> kruskal()
* BoundingBox<>
* operator+=() -> add()
+ clear()
* 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
New features
+ Standardized LEMON exceptions
+ Undirected Graph
+ Standard graph file format, input and output classes for it
+ GraphToEps: A simple graph drawer
Changes
* Redesigned Graph infrastructures
* head() -> target(), tail() -> source()
* Some standard namings have changes:
ValueType -> Value,
KeyType -> Key,
ReferenceType -> Reference,
PointerType -> Pointer
* Better documentation
2004-09-30 Version 0.2 released