1 | 2008-02-08 Version 0.7 released |
---|
2 | New Features |
---|
3 | + new data structures |
---|
4 | * classes |
---|
5 | StaticGraph |
---|
6 | ExtendFindEnum |
---|
7 | BfsVisitor class |
---|
8 | Bipartite partitions based on visitors |
---|
9 | * helper class for checking existence of a nested class |
---|
10 | * general mapping based variant type |
---|
11 | * IntegerMap |
---|
12 | + new algoritmhs |
---|
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 |
---|
45 | * Soplex support |
---|
46 | * ColIt class |
---|
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 |
---|
53 | + demos |
---|
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 |
---|
58 | + tests for |
---|
59 | * graph copies |
---|
60 | * random.h |
---|
61 | * max weighted matchings |
---|
62 | + planarity related additions |
---|
63 | * checking and embedding |
---|
64 | * planar grid embedding |
---|
65 | * planar graph coloring |
---|
66 | + bipartite matchings |
---|
67 | * common interface |
---|
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 |
---|
77 | * doxygen |
---|
78 | * renaming topology doxygen group to graph_prop doxygen group |
---|
79 | * introducing planar doxygen group |
---|
80 | Changes |
---|
81 | * redesigned |
---|
82 | * undirected edgesets (like the smart graph or ugraph) |
---|
83 | * interface of MaxMatching and UnionFindEnum |
---|
84 | * interface of maximum flow algorithms |
---|
85 | * Kruskal algorithm |
---|
86 | * augmenting path based bipartite matching |
---|
87 | Improvements |
---|
88 | * graph copy |
---|
89 | * preliminary support for static graphs |
---|
90 | * added BpUGraphCopy |
---|
91 | * Bfs/Dfs/Dijkstra |
---|
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 |
---|
99 | * easier inverse |
---|
100 | * faster geometric minimum spanning tree algorithm |
---|
101 | * new implementation of undirected graphs |
---|
102 | * Hao-Orlin algorithm became epsilon-safe |
---|
103 | * LpSoplex |
---|
104 | * added getter functions |
---|
105 | * better m4 file |
---|
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 |
---|
111 | * path |
---|
112 | * PathNodeIt |
---|
113 | PathWriter/Reader structures |
---|
114 | Distinct MapSet readers and writers |
---|
115 | * more simple interface for PathDumper |
---|
116 | Updated |
---|
117 | * tutorial for |
---|
118 | * algorithms |
---|
119 | * graph visualization |
---|
120 | * documentation |
---|
121 | Backward incompatibilities/changed namings |
---|
122 | * min_cut.h => nagamochi_ibaraki.h |
---|
123 | * clone => build |
---|
124 | * RevIt => RevEdgeIt |
---|
125 | * _FixId => LpId |
---|
126 | * setObj => obj |
---|
127 | * is_min => isMin |
---|
128 | * is_max => isMax |
---|
129 | * ball2() => disc() |
---|
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 |
---|
137 | Removed |
---|
138 | - template Map template parameter from InvertableMaps |
---|
139 | - union-find Item template parameter |
---|
140 | - strict checking |
---|
141 | - some automatic callback generation |
---|
142 | - '-Wshadow' seemed too strict therefore removed |
---|
143 | Several bugfixes |
---|
144 | |
---|
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) |
---|
148 | New Features |
---|
149 | + Mixed Integer Programming (MIP) support |
---|
150 | + interface to GLPK and CPLEX MIP solvers |
---|
151 | + Data structures |
---|
152 | * Bipatrite graph concepts and implementations |
---|
153 | * a Polinomial template class |
---|
154 | * RefPtr: a reference counted pointer class |
---|
155 | * SimpleBucketHeap |
---|
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: |
---|
171 | * UndirXyz -> UXyz |
---|
172 | * UNDIRGRAPH_TYPEDEFS -> UGRAPH_TYPEDEFS |
---|
173 | * GridGraph -> GridUGraph |
---|
174 | * LinearHeap -> BucketHeap |
---|
175 | * ColorSet -> Palette |
---|
176 | * xy -> dim2::Point |
---|
177 | * DirPath -> Path |
---|
178 | * concept -> concepts (namespace & directory) |
---|
179 | * LpSolverBase |
---|
180 | * ColName() -> colName |
---|
181 | * Coeff() -> coeff() |
---|
182 | * MinCostFlow -> SspMinCostFlow |
---|
183 | Repository reorganization: |
---|
184 | * compilation is conducted by a single makefile |
---|
185 | * internal building blocks are now in a separate directory |
---|
186 | (lemon/bits) |
---|
187 | Major improvements of many algorithms and data structures |
---|
188 | Several bugfixes |
---|
189 | Compatibility issues: |
---|
190 | * known to compile with |
---|
191 | * GCC 3.3, 3.4, 4.0, 4.1 |
---|
192 | * MinGW, MinGW32 |
---|
193 | * Intel C++ 9.x support |
---|
194 | |
---|
195 | 2006-02-03 Version 0.5 Released |
---|
196 | New features |
---|
197 | + Shortest paths algorithms |
---|
198 | * bellman_ford.h |
---|
199 | * floyd_warshall.h |
---|
200 | * johnson.h |
---|
201 | + Euler tour iterator for directed and undirected graphs |
---|
202 | + Other algorithms: |
---|
203 | * dag_shortest_path.h |
---|
204 | * fredman_tarjan.h and prim.h for min cost trees |
---|
205 | + Bipartite graph concept and implementations |
---|
206 | + Graph maps: |
---|
207 | * template assign operator |
---|
208 | * specialized iterable bool map |
---|
209 | * potential difference map |
---|
210 | * NodeMatrixMap -- Matrix over the nodes |
---|
211 | + Maps: |
---|
212 | * IterableIntMap |
---|
213 | + Tools: |
---|
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 |
---|
220 | + Demo for topology |
---|
221 | + counter.h: a tool to measure the number of steps of algorithms |
---|
222 | + Some useful scripts: check-compiler, check-integrity |
---|
223 | Improvements |
---|
224 | + Bfs/Dfs/Dijkstra |
---|
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 |
---|
230 | + GUI: |
---|
231 | * NewMap window in MapSelector |
---|
232 | * Algorithm window and some algorithms (eg. Kruskal) added |
---|
233 | + LemonReader: |
---|
234 | * exception on non-existent files |
---|
235 | + LP interface: |
---|
236 | * (Dual)Expr::simplify(double tolerance) added |
---|
237 | * getDual() |
---|
238 | + GraphToEps: |
---|
239 | * negateY() opt |
---|
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* |
---|
252 | Bugfixes in |
---|
253 | * DFS |
---|
254 | * Preflow |
---|
255 | * x86_64 connected bugfixes (lemon_reader.h) |
---|
256 | * lp.h |
---|
257 | Other changes |
---|
258 | * Demos and benchmarks are not built by default now. They can be |
---|
259 | * enabled with the --enable-demo and --enable-benchmark |
---|
260 | * configure flags. |
---|
261 | * GCC 4.0.3 and ICC 9.0 compatibility |
---|
262 | |
---|
263 | 2005-08-27 Version 0.4 Released |
---|
264 | New features |
---|
265 | + More and better graph I/O functionalities |
---|
266 | + High level uniform LP solver interface to CPLEX and GLKP |
---|
267 | + New map adaptors |
---|
268 | + New convenience maps |
---|
269 | * IdMap, DescriptorMap |
---|
270 | * InDegMap, OutDegMap |
---|
271 | * XMap, YMap |
---|
272 | + Default graph maps are iterable |
---|
273 | + glemon: a graph editor |
---|
274 | + Some new demo codes added, the old ones got polished. |
---|
275 | Improvements |
---|
276 | + graphToEps() |
---|
277 | * Automatic node size and edge width scaling |
---|
278 | * Simple color palette tool (ColorSet) |
---|
279 | + Bfs/Dfs/Dijkstra |
---|
280 | * Step-by-step execution |
---|
281 | * Run from multiple sources |
---|
282 | * Used define stop condition |
---|
283 | * Improved "named parameters" |
---|
284 | + Preflow |
---|
285 | * Changed interface |
---|
286 | * Function type interface |
---|
287 | + ListGraph/SmartGraph |
---|
288 | * split() splits a node |
---|
289 | * SnapShot |
---|
290 | Changes |
---|
291 | * Changed namings: |
---|
292 | * Wrapper -> Adaptor |
---|
293 | * kruskalEdgeMap() -> kruskal() |
---|
294 | * kruskalEdgeMap_IteratorOut() -> kruskal() |
---|
295 | * BoundingBox<> |
---|
296 | * operator+=() -> add() |
---|
297 | + clear() |
---|
298 | * Better documentation |
---|
299 | * Several important bugfixes |
---|
300 | * Now LEMON should compile without warnings with |
---|
301 | * gcc 3.3, 3.4, 4.0 |
---|
302 | * Intel C++ Compiler v9.0 |
---|
303 | |
---|
304 | 2005-03-19 Version 0.3.1 Released |
---|
305 | This release fixes a compilation failure bug under cygwin. |
---|
306 | |
---|
307 | 2005-02-21 Version 0.3 released |
---|
308 | New features |
---|
309 | + Standardized LEMON exceptions |
---|
310 | + Undirected Graph |
---|
311 | + Standard graph file format, input and output classes for it |
---|
312 | + GraphToEps: A simple graph drawer |
---|
313 | Changes |
---|
314 | * Redesigned Graph infrastructures |
---|
315 | * head() -> target(), tail() -> source() |
---|
316 | * Some standard namings have changes: |
---|
317 | ValueType -> Value, |
---|
318 | KeyType -> Key, |
---|
319 | ReferenceType -> Reference, |
---|
320 | PointerType -> Pointer |
---|
321 | * Better documentation |
---|
322 | |
---|
323 | 2004-09-30 Version 0.2 released |
---|