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