1 | 2008-02-08 Version 0.7 released |
---|
2 | |
---|
3 | * added |
---|
4 | - new data structures |
---|
5 | classes |
---|
6 | StaticGraphBase |
---|
7 | ExtendFindEnum |
---|
8 | BfsVisitor class |
---|
9 | Bipartite partitions based on visitors |
---|
10 | helper class for checking existence of a nested class |
---|
11 | general mapping based variant type |
---|
12 | IntegerMap |
---|
13 | - new functions and tools |
---|
14 | ArgParser, a command line argument parser |
---|
15 | DistLog, a tool for measuring one and two dimensional distributions |
---|
16 | undirected minimum cut benchmarking |
---|
17 | tools/lgf-gen.cc, a random graph generator |
---|
18 | BpUGraphReader and Writer |
---|
19 | DynEdgeLookUp implementation based on splay trees |
---|
20 | MACROS for debug map usage |
---|
21 | - new algoritmhs |
---|
22 | Lagrange relaxation based algorithm for the delay constrained least cost path problem |
---|
23 | a preflow based general network circulation algorithm |
---|
24 | 2-approximation of Steiner-tree problem |
---|
25 | two heuristics (http://www.avglab.com/andrew/pub/neci-tr-96-132.ps) |
---|
26 | tsp2, a minimum spanning tree based TSP algorithm |
---|
27 | Delaunay triangulation |
---|
28 | Gomory-Hu tree algorithm |
---|
29 | Edmond's Blossom shrinking algorithm |
---|
30 | minimum mean cycle algorithm |
---|
31 | Goldberg-Tarjan algorithm (Preflow with Dynamic Trees) |
---|
32 | Dinitz-Sleator-Tarjan (Blocking flow with Dynamic Tree) |
---|
33 | - new distributions (Gaussian, exponential, Gamma, two dimensional random, buffered bit generation) |
---|
34 | - push-relabel type algorithm related additions |
---|
35 | Elevator, a class for handling item labels in push-relabel type algorithms |
---|
36 | a push/relabel type max cardinality matching implementation |
---|
37 | some query function for push-relabel based matching |
---|
38 | - LP related additions |
---|
39 | Soplex support |
---|
40 | ColIt class |
---|
41 | new functions (simplify(), isFinite(), row and col getter function) |
---|
42 | _setColCoeff and _setRowCoeff parameters |
---|
43 | section reader and writer for lemon IO |
---|
44 | equality-type constraint can now be added to a LP |
---|
45 | virtual functions of class LpCplex |
---|
46 | some query functions for GLPK |
---|
47 | - demos |
---|
48 | preflow based general network circulation demo |
---|
49 | Steiner 2-approximation demo |
---|
50 | demo for SAT problems |
---|
51 | sample input for sat-2 and sat demos |
---|
52 | - tests for |
---|
53 | graph copies |
---|
54 | random.h |
---|
55 | max weighted matchings |
---|
56 | - rename graphs script |
---|
57 | - planarity related additions |
---|
58 | checking and embedding |
---|
59 | planar grid embedding |
---|
60 | planar graph coloring |
---|
61 | - administrative improvements |
---|
62 | script for automatic checking of SVN commit's consistency |
---|
63 | automatic doc generation from the SVN trunk |
---|
64 | check for gcc version 3.3, 3.4, 4.0 and 4.1.2 as well |
---|
65 | reorganization of the modules and groups |
---|
66 | a tools directory added for useful executables codes |
---|
67 | doxygen |
---|
68 | renaming topology doxygen group to graph_prop doxygen group |
---|
69 | introducing planar doxygen group |
---|
70 | - bipartite matchings |
---|
71 | common interface |
---|
72 | Query functions: aMatching and bMatching |
---|
73 | ANodeMap<UEdge> matching map |
---|
74 | BNodeMap<bool> barrier map |
---|
75 | |
---|
76 | * changed, modified, improved |
---|
77 | - redesigned |
---|
78 | undirected edgesets (like the smart or ugraph) |
---|
79 | interface of MaxMatching and UnionFindEnum |
---|
80 | interface of maximum flow algorithms |
---|
81 | Kruskal algorithm |
---|
82 | augmenting path based bipartite matching |
---|
83 | - min cost flows |
---|
84 | various min cost flow solvers |
---|
85 | redesigned CapacityScaling algorithm |
---|
86 | - graph copy |
---|
87 | preliminary support for static graphs |
---|
88 | added BpUGraphCopy |
---|
89 | - execution |
---|
90 | conditional execution until the target is reached |
---|
91 | modified start() function in Dfs and Dijkstra classes to give back reached edge/node |
---|
92 | - Dijkstra |
---|
93 | return the temporary distance of the current node |
---|
94 | using operation traits |
---|
95 | - patch for retrieving reached/processed node in dijkstra, bfs and dfs |
---|
96 | - prescaling can be turned off in GraphToEps |
---|
97 | - better handling of inexact computation |
---|
98 | - easier inverse |
---|
99 | - faster geometric minimum spanning tree |
---|
100 | - new implementation of undirected graphs |
---|
101 | - Hao-Orlin algorithm became epsilon-safe |
---|
102 | - LpSoplex |
---|
103 | added getter functions |
---|
104 | better m4 file |
---|
105 | better handling of unsolved lps |
---|
106 | - allowing 'string' type quoting |
---|
107 | - clear() function for unionfinds |
---|
108 | - integer parameters also converted to double |
---|
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 | |
---|
117 | * updated |
---|
118 | - tutorial for |
---|
119 | algorithms |
---|
120 | graph visualization |
---|
121 | - documentation |
---|
122 | |
---|
123 | * rename |
---|
124 | - min_cut.h => nagamochi_ibaraki.h |
---|
125 | - clone => build |
---|
126 | - RevIt => RevEdgeIt |
---|
127 | - _FixId => LpId |
---|
128 | - setObj => obj |
---|
129 | - is_min => isMin |
---|
130 | - is_max => isMax |
---|
131 | - 'hugo' => 'lemon' |
---|
132 | - ball2() => disc() |
---|
133 | - state_enum => State |
---|
134 | - getNotifier => notifier |
---|
135 | - using LEMON_ASSERT instead of LogicError() |
---|
136 | - uedgeset is an alias for edgeset |
---|
137 | - CPXMIP_OPTIMAL_TOL status is considered as OPTIMAL too |
---|
138 | - removed "Type" suffix from typedefs |
---|
139 | - lower case local variables |
---|
140 | |
---|
141 | * removed |
---|
142 | - template Map template parameter from InvertableMaps |
---|
143 | - unionfind Item template parameter |
---|
144 | - strict checking |
---|
145 | - some automatic callback generation |
---|
146 | '-Wshadow' seemed too strict therefore removed |
---|
147 | |
---|
148 | * several bugfixes |
---|
149 | |
---|
150 | 2006-10-31 Version 0.6 Released |
---|
151 | * GLEMON has moved to a separate repository |
---|
152 | (https://hugo.cs.elte.hu/svn/glemon/trunk) |
---|
153 | * New Features |
---|
154 | - Mixed Integer Programming (MIP) support |
---|
155 | - interface to GLPK and CPLEX MIP solvers |
---|
156 | - Data structures |
---|
157 | - Bipatrite graph concepts and implementations |
---|
158 | - a Polinomial template class |
---|
159 | - RefPtr: a reference counted pointer class |
---|
160 | - SimpleBucketHeap |
---|
161 | - random.h: Mersenne Twister random number generator |
---|
162 | - EdgeLookUp and AllEdgeLookUp |
---|
163 | - Tools to find edges between to nodes in time O(log d) |
---|
164 | - new matching algorithms |
---|
165 | - Bipartite Graph Max Cardinality Matching (Hopcroft-Karp) |
---|
166 | - MaxWeightedBipartiteMatching |
---|
167 | - MinCostMaxBipartiteMatching |
---|
168 | - MaxCardinalitySearch |
---|
169 | - MinimalCut in UGraph |
---|
170 | - Tabu Search framework |
---|
171 | - Minimum Cost Arborescence algorithm |
---|
172 | - Edmonds-Karp MaxFlow |
---|
173 | - Hao-Orlin algorithm |
---|
174 | - eps.h: A simple tool to create .eps pictures. |
---|
175 | * Backward incompatibilities/changed namings: |
---|
176 | - UndirXyz -> UXyz |
---|
177 | - UNDIRGRAPH_TYPEDEFS -> UGRAPH_TYPEDEFS |
---|
178 | - GridGraph -> GridUGraph |
---|
179 | - LinearHeap -> BucketHeap |
---|
180 | - ColorSet -> Palette |
---|
181 | - xy -> dim2::Point |
---|
182 | - DirPath -> Path |
---|
183 | - concept -> concepts (namespace & directory) |
---|
184 | - LpSolverBase |
---|
185 | - ColName() -> colName |
---|
186 | - Coeff() -> coeff() |
---|
187 | - MinCostFlow -> SspMinCostFlow |
---|
188 | * Repository reorganization: |
---|
189 | - compilation is conducted by a single makefile |
---|
190 | - internal building blocks are now in a separate directory |
---|
191 | (lemon/bits) |
---|
192 | * Major improvements many algorithms and data structures. |
---|
193 | * Several bugfixes |
---|
194 | * Compatibility issues: |
---|
195 | - known to compile with |
---|
196 | - GCC 3.3, 3.4, 4.0, 4.1 |
---|
197 | - MinGW, MinGW32 |
---|
198 | - Intel C++ 9.x support |
---|
199 | |
---|
200 | 2006-02-03 Version 0.5 Released |
---|
201 | * New features: |
---|
202 | - Bfs/Dfs/Dijkstra |
---|
203 | + query functions for the next node/edge to be processed |
---|
204 | + visitor interface for dfs |
---|
205 | - topology.h: small functions for discovering graph topology |
---|
206 | + connected components, strongly connected components |
---|
207 | + bipartiteness testing |
---|
208 | - Shortest paths algorithms: |
---|
209 | bellman_ford.h, floyd_warshall.h, johnson.h |
---|
210 | - Euler tour iterator for directed and undirected graphs |
---|
211 | - Other algorithms: |
---|
212 | + dag_shortest_path.h |
---|
213 | + fredman_tarjan.h and prim.h for min cost trees |
---|
214 | - Bipartite graph concept and implementations |
---|
215 | - Graph maps: |
---|
216 | + template assign operator |
---|
217 | + specialized iterable bool map |
---|
218 | + potential difference map |
---|
219 | + NodeMatrixMap -- Matrix over the nodes |
---|
220 | - Maps: |
---|
221 | + IterableIntMap |
---|
222 | - GUI: |
---|
223 | + NewMap window in MapSelector |
---|
224 | + Algorithm window and some algorithms (eg. Kruskal) added |
---|
225 | - LemonReader: |
---|
226 | + exception on non-existent files |
---|
227 | - LP interface: |
---|
228 | + (Dual)Expr::simplify(double tolerance) added |
---|
229 | + getDual() |
---|
230 | - GraphToEps: |
---|
231 | + negateY() opt |
---|
232 | + male/female node shapes :) |
---|
233 | + correct %%BoundingBox handling |
---|
234 | - Tools: |
---|
235 | + Timer can be stop()ed and (re)start()ed |
---|
236 | + radix sort algorithm |
---|
237 | + tolerance.h for working with imprecise numbers |
---|
238 | * Backward incompatibilities/changed namings: |
---|
239 | - Access functions of TimeStamp/Timer |
---|
240 | - Undir graph interface: findUEdge, ConUEdgeIt |
---|
241 | - pred -> predEdge renaming in search algorithms |
---|
242 | - SnapShot -> Snapshot in {List,Smart}Graph |
---|
243 | - NewEdgeSetAdaptor -> ListEdgeSet |
---|
244 | - LP: set{Obj,Row,Col}() -> {obj,row,col}() |
---|
245 | - "label" instead of "id" inside the LGF files |
---|
246 | - UndirGraph -> UGraph, UndirEdge* -> UEdge* |
---|
247 | - BipartiteGraph -> BpGraph, Lower/UpperNode* -> A/BNode* |
---|
248 | * Bugfixes in |
---|
249 | - DFS |
---|
250 | - Preflow |
---|
251 | - x86_64 connected bugfixes (lemon_reader.h) |
---|
252 | - lp.h |
---|
253 | * New demos, benchmarks and tools: |
---|
254 | - graph_orientation.cc: A thoroughly documented demo application |
---|
255 | - runningTimeTest(): a tool to measure running times more precisely |
---|
256 | - Demo for topology |
---|
257 | - counter.h: a tool to measure the number of steps of algorithms |
---|
258 | - Some useful scripts: check-compiler, check-integrity |
---|
259 | * Other changes: |
---|
260 | - Demos and benchmarks are not built by default now. They can be |
---|
261 | enabled with the --enable-demo and --enable-benchmark |
---|
262 | configure flags. |
---|
263 | - GCC 4.0.3 and ICC 9.0 compatibility |
---|
264 | |
---|
265 | 2005-08-27 Version 0.4 Released |
---|
266 | * List of new features and changes |
---|
267 | * Changed namings: |
---|
268 | Wrapper -> Adaptor |
---|
269 | kruskalEdgeMap() -> kruskal() |
---|
270 | kruskalEdgeMap_IteratorOut() -> kruskal() |
---|
271 | * BoundinBox<> |
---|
272 | * operator+=() -> add() |
---|
273 | + clear() |
---|
274 | + More and better graph I/O functionalities |
---|
275 | + High level uniform LP solver interface to CPLEX and GLKP |
---|
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 | + Function type interface |
---|
286 | + Changed interface |
---|
287 | * ListGraph/SmarGraph |
---|
288 | + split() splits a node |
---|
289 | + SnapShot |
---|
290 | + New map adaptors |
---|
291 | + New convenience maps |
---|
292 | + IdMap, DescriptorMap |
---|
293 | + InDegMap, OutDegMap |
---|
294 | + XMap, YMap |
---|
295 | + Default graph maps are iterable |
---|
296 | + glemon: a graph editor |
---|
297 | + Some new demo codes added, the old ones got polished. |
---|
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 | * List of new features and changes |
---|
309 | * Redesigned Graph infrastructures |
---|
310 | + Standardized LEMON exceptions |
---|
311 | + Undirected Graph |
---|
312 | + Standard graph file format, input and output classes for it. |
---|
313 | * head() -> target(), tail() -> source() |
---|
314 | * Some standard namings have changes: |
---|
315 | ValueType -> Value, |
---|
316 | KeyType -> Key, |
---|
317 | ReferenceType ->Reference, |
---|
318 | PointerType -> Pointer |
---|
319 | + GraphToEps: A simple graph drawer |
---|
320 | * Better documentation |
---|
321 | |
---|
322 | 2004-09-30 Version 0.2 released |
---|
323 | |
---|