1 2008-02-08 Version 0.7 released
8 Bipartite partitions based on visitors
9 * helper class for checking existence of a nested class
10 * general mapping based variant type
13 * Lagrange relaxation based algorithm for the delay constrained least cost path problem
14 * a preflow based general network circulation algorithm
15 * 2-approximation of Steiner-tree problem
16 * two heuristics for minimum cut algorithms
17 (http://www.avglab.com/andrew/pub/neci-tr-96-132.ps)
18 * Gomory-Hu tree algorithm
19 * Edmond's Blossom shrinking algorithm
20 * minimum mean cycle algorithm
21 * Goldberg-Tarjan algorithm (Preflow with Dynamic Trees)
22 * Dinitz-Sleator-Tarjan (Blocking flow with Dynamic Tree)
23 * min cost flow algorithms:
24 * successive shortest path algorithm
25 * capacity scaling algorithm
26 * simple cycle canceling algorithm
27 * minimum mean cycle canceling algorithm
28 * cost scaling algorithm
29 * network simplex algorithm
30 * min cost maximum flow algorithm
31 + new functions and tools
32 * ArgParser, a command line argument parser
33 * DistLog, a tool for measuring one and two dimensional distributions
34 * undirected minimum cut benchmarking
35 * tools/lgf-gen.cc, a random graph generator
36 * BpUGraphReader and Writer
37 * DynEdgeLookUp implementation based on splay trees
38 * MACROS for debug map usage
39 + new distributions (Gaussian, exponential, Gamma, two dimensional random, buffered bit generation)
40 + push-relabel type algorithm related additions
41 * Elevator, a class for handling item labels in push-relabel type algorithms
42 * a push/relabel type max cardinality matching implementation
43 * some query function for push-relabel based matching
44 + LP related additions
47 * new functions (simplify(), isFinite(), row and col getter function)
48 * _setColCoeff and _setRowCoeff parameters
49 * section reader and writer for LEMON IO
50 * equality-type constraint can now be added to a LP
51 * virtual functions of class LpCplex
52 * some query functions for GLPK
54 * preflow based general network circulation demo
55 * Steiner 2-approximation demo
56 * demo for SAT problems
57 * sample input for sat-2 and sat demos
61 * max weighted matchings
62 + planarity related additions
63 * checking and embedding
64 * planar grid embedding
65 * planar graph coloring
68 * Query functions: aMatching and bMatching
69 * ANodeMap<UEdge> matching map
70 * BNodeMap<bool> barrier map
71 Repository reorganization
72 * script for automatic checking of SVN commit's consistency
73 * automatic doc generation from the SVN trunk
74 * check for gcc version 3.3, 3.4, 4.0 and 4.1.2 as well
75 * reorganization of the modules and groups
76 * a tools directory added for useful executables codes
78 * renaming topology doxygen group to graph_prop doxygen group
79 * introducing planar doxygen group
82 * undirected edgesets (like the smart graph or ugraph)
83 * interface of MaxMatching and UnionFindEnum
84 * interface of maximum flow algorithms
86 * augmenting path based bipartite matching
89 * preliminary support for static graphs
92 * conditional execution until the target is reached
93 * modified start() function in Dfs and Dijkstra classes to give back reached edge/node
94 * return the temporary distance of the current node
95 * using operation traits in Dijkstra
96 * patch for retrieving reached/processed node
97 * prescaling can be turned off in GraphToEps
98 * better handling of inexact computations
100 * faster geometric minimum spanning tree algorithm
101 * new implementation of undirected graphs
102 * Hao-Orlin algorithm became epsilon-safe
104 * added getter functions
106 * better handling of unsolved lps
107 * allowing 'string' type quoting for item reading and writing
108 * clear() function for union-find structures
109 * hacking MIP is possible without integer variables
110 * space reservation for SmartGraph
113 PathWriter/Reader structures
114 Distinct MapSet readers and writers
115 * more simple interface for PathDumper
119 * graph visualization
121 Backward incompatibilities/changed namings
122 * min_cut.h => nagamochi_ibaraki.h
130 * state_enum => State
131 * getNotifier => notifier
132 * using LEMON_ASSERT instead of LogicError()
133 * uedgeset is an alias for edgeset
134 * CPXMIP_OPTIMAL_TOL status is considered as OPTIMAL too
135 * removed "Type" suffix from typedefs
136 * lower case local variables
138 - template Map template parameter from InvertableMaps
139 - union-find Item template parameter
141 - some automatic callback generation
142 - '-Wshadow' seemed too strict therefore removed
145 2006-10-31 Version 0.6 Released
146 GLEMON has moved to a separate repository
147 (https://hugo.cs.elte.hu/svn/glemon/trunk)
149 + Mixed Integer Programming (MIP) support
150 + interface to GLPK and CPLEX MIP solvers
152 * Bipatrite graph concepts and implementations
153 * a Polinomial template class
154 * RefPtr: a reference counted pointer class
156 + random.h: Mersenne Twister random number generator
157 + EdgeLookUp and AllEdgeLookUp
158 + Tools to find edges between to nodes in time O(log d)
159 + new matching algorithms
160 + Bipartite Graph Max Cardinality Matching (Hopcroft-Karp)
161 + MaxWeightedBipartiteMatching
162 + MinCostMaxBipartiteMatching
163 + MaxCardinalitySearch
164 + MinimalCut in UGraph
165 + Tabu Search framework
166 + Minimum Cost Arborescence algorithm
167 + Edmonds-Karp MaxFlow
168 + Hao-Orlin algorithm
169 + eps.h: A simple tool to create .eps pictures.
170 Backward incompatibilities/changed namings:
172 * UNDIRGRAPH_TYPEDEFS -> UGRAPH_TYPEDEFS
173 * GridGraph -> GridUGraph
174 * LinearHeap -> BucketHeap
175 * ColorSet -> Palette
178 * concept -> concepts (namespace & directory)
180 * ColName() -> colName
182 * MinCostFlow -> SspMinCostFlow
183 Repository reorganization:
184 * compilation is conducted by a single makefile
185 * internal building blocks are now in a separate directory
187 Major improvements of many algorithms and data structures
189 Compatibility issues:
190 * known to compile with
191 * GCC 3.3, 3.4, 4.0, 4.1
193 * Intel C++ 9.x support
195 2006-02-03 Version 0.5 Released
197 + Shortest paths algorithms
201 + Euler tour iterator for directed and undirected graphs
203 * dag_shortest_path.h
204 * fredman_tarjan.h and prim.h for min cost trees
205 + Bipartite graph concept and implementations
207 * template assign operator
208 * specialized iterable bool map
209 * potential difference map
210 * NodeMatrixMap -- Matrix over the nodes
214 * Timer can be stop()ed and (re)start()ed
215 * radix sort algorithm
216 * tolerance.h for working with imprecise numbers
217 New demos, benchmarks and tools
218 + graph_orientation.cc: A thoroughly documented demo application
219 + runningTimeTest(): a tool to measure running times more precisely
221 + counter.h: a tool to measure the number of steps of algorithms
222 + Some useful scripts: check-compiler, check-integrity
225 * query functions for the next node/edge to be processed
226 * visitor interface for dfs
227 + topology.h: small functions for discovering graph topology
228 * connected components, strongly connected components
229 * bipartiteness testing
231 * NewMap window in MapSelector
232 * Algorithm window and some algorithms (eg. Kruskal) added
234 * exception on non-existent files
236 * (Dual)Expr::simplify(double tolerance) added
240 * male/female node shapes :)
241 * correct BoundingBox handling
242 Backward incompatibilities/changed namings:
243 * Access functions of TimeStamp/Timer
244 * Undirected graph interface: findUEdge, ConUEdgeIt
245 * pred -> predEdge renaming in search algorithms
246 * SnapShot -> Snapshot in {List,Smart}Graph
247 * NewEdgeSetAdaptor -> ListEdgeSet
248 * LP: set{Obj,Row,Col}() -> {obj,row,col}()
249 * "label" instead of "id" inside the LGF files
250 * UndirGraph -> UGraph, UndirEdge* -> UEdge*
251 * BipartiteGraph -> BpGraph, Lower/UpperNode* -> A/BNode*
255 * x86_64 connected bugfixes (lemon_reader.h)
258 * Demos and benchmarks are not built by default now. They can be
259 * enabled with the --enable-demo and --enable-benchmark
261 * GCC 4.0.3 and ICC 9.0 compatibility
263 2005-08-27 Version 0.4 Released
265 + More and better graph I/O functionalities
266 + High level uniform LP solver interface to CPLEX and GLKP
268 + New convenience maps
269 * IdMap, DescriptorMap
270 * InDegMap, OutDegMap
272 + Default graph maps are iterable
273 + glemon: a graph editor
274 + Some new demo codes added, the old ones got polished.
277 * Automatic node size and edge width scaling
278 * Simple color palette tool (ColorSet)
280 * Step-by-step execution
281 * Run from multiple sources
282 * Used define stop condition
283 * Improved "named parameters"
286 * Function type interface
287 + ListGraph/SmartGraph
288 * split() splits a node
293 * kruskalEdgeMap() -> kruskal()
294 * kruskalEdgeMap_IteratorOut() -> kruskal()
296 * operator+=() -> add()
298 * Better documentation
299 * Several important bugfixes
300 * Now LEMON should compile without warnings with
302 * Intel C++ Compiler v9.0
304 2005-03-19 Version 0.3.1 Released
305 This release fixes a compilation failure bug under cygwin.
307 2005-02-21 Version 0.3 released
309 + Standardized LEMON exceptions
311 + Standard graph file format, input and output classes for it
312 + GraphToEps: A simple graph drawer
314 * Redesigned Graph infrastructures
315 * head() -> target(), tail() -> source()
316 * Some standard namings have changes:
319 ReferenceType -> Reference,
320 PointerType -> Pointer
321 * Better documentation
323 2004-09-30 Version 0.2 released