11 * IntegerMap |
11 * IntegerMap |
12 + new algoritmhs |
12 + new algoritmhs |
13 * Lagrange relaxation based algorithm for the delay constrained least cost path problem |
13 * Lagrange relaxation based algorithm for the delay constrained least cost path problem |
14 * a preflow based general network circulation algorithm |
14 * a preflow based general network circulation algorithm |
15 * 2-approximation of Steiner-tree problem |
15 * 2-approximation of Steiner-tree problem |
16 * two heuristics (http://www.avglab.com/andrew/pub/neci-tr-96-132.ps) |
16 * two heuristics for minimum cut algorithms |
17 * Delaunay triangulation |
17 (http://www.avglab.com/andrew/pub/neci-tr-96-132.ps) |
18 * Gomory-Hu tree algorithm |
18 * Gomory-Hu tree algorithm |
19 * Edmond's Blossom shrinking algorithm |
19 * Edmond's Blossom shrinking algorithm |
20 * minimum mean cycle algorithm |
20 * minimum mean cycle algorithm |
21 * Goldberg-Tarjan algorithm (Preflow with Dynamic Trees) |
21 * Goldberg-Tarjan algorithm (Preflow with Dynamic Trees) |
22 * Dinitz-Sleator-Tarjan (Blocking flow with Dynamic Tree) |
22 * Dinitz-Sleator-Tarjan (Blocking flow with Dynamic Tree) |
25 * capacity scaling algorithm |
25 * capacity scaling algorithm |
26 * simple cycle canceling algorithm |
26 * simple cycle canceling algorithm |
27 * minimum mean cycle canceling algorithm |
27 * minimum mean cycle canceling algorithm |
28 * cost scaling algorithm |
28 * cost scaling algorithm |
29 * network simplex algorithm |
29 * network simplex algorithm |
|
30 * min cost maximum flow algorithm |
30 + new functions and tools |
31 + new functions and tools |
31 ArgParser, a command line argument parser |
32 * ArgParser, a command line argument parser |
32 * DistLog, a tool for measuring one and two dimensional distributions |
33 * DistLog, a tool for measuring one and two dimensional distributions |
33 * undirected minimum cut benchmarking |
34 * undirected minimum cut benchmarking |
34 * tools/lgf-gen.cc, a random graph generator |
35 * tools/lgf-gen.cc, a random graph generator |
35 * BpUGraphReader and Writer |
36 * BpUGraphReader and Writer |
36 * DynEdgeLookUp implementation based on splay trees |
37 * DynEdgeLookUp implementation based on splay trees |
89 * added BpUGraphCopy |
90 * added BpUGraphCopy |
90 * Bfs/Dfs/Dijkstra |
91 * Bfs/Dfs/Dijkstra |
91 * conditional execution until the target is reached |
92 * conditional execution until the target is reached |
92 * modified start() function in Dfs and Dijkstra classes to give back reached edge/node |
93 * modified start() function in Dfs and Dijkstra classes to give back reached edge/node |
93 * return the temporary distance of the current node |
94 * return the temporary distance of the current node |
94 * using operation traits |
95 * using operation traits in Dijkstra |
95 * patch for retrieving reached/processed node |
96 * patch for retrieving reached/processed node |
96 * prescaling can be turned off in GraphToEps |
97 * prescaling can be turned off in GraphToEps |
97 * better handling of inexact computations |
98 * better handling of inexact computations |
98 * easier inverse |
99 * easier inverse |
99 * faster geometric minimum spanning tree algorithm |
100 * faster geometric minimum spanning tree algorithm |
133 * CPXMIP_OPTIMAL_TOL status is considered as OPTIMAL too |
134 * CPXMIP_OPTIMAL_TOL status is considered as OPTIMAL too |
134 * removed "Type" suffix from typedefs |
135 * removed "Type" suffix from typedefs |
135 * lower case local variables |
136 * lower case local variables |
136 Removed |
137 Removed |
137 - template Map template parameter from InvertableMaps |
138 - template Map template parameter from InvertableMaps |
138 - unionfind Item template parameter |
139 - union-find Item template parameter |
139 - strict checking |
140 - strict checking |
140 - some automatic callback generation |
141 - some automatic callback generation |
141 - '-Wshadow' seemed too strict therefore removed |
142 - '-Wshadow' seemed too strict therefore removed |
142 Several bugfixes |
143 Several bugfixes |
143 |
144 |
235 * (Dual)Expr::simplify(double tolerance) added |
236 * (Dual)Expr::simplify(double tolerance) added |
236 * getDual() |
237 * getDual() |
237 + GraphToEps: |
238 + GraphToEps: |
238 * negateY() opt |
239 * negateY() opt |
239 * male/female node shapes :) |
240 * male/female node shapes :) |
240 * correct %%BoundingBox handling |
241 * correct BoundingBox handling |
241 Backward incompatibilities/changed namings: |
242 Backward incompatibilities/changed namings: |
242 * Access functions of TimeStamp/Timer |
243 * Access functions of TimeStamp/Timer |
243 * Undir graph interface: findUEdge, ConUEdgeIt |
244 * Undirected graph interface: findUEdge, ConUEdgeIt |
244 * pred -> predEdge renaming in search algorithms |
245 * pred -> predEdge renaming in search algorithms |
245 * SnapShot -> Snapshot in {List,Smart}Graph |
246 * SnapShot -> Snapshot in {List,Smart}Graph |
246 * NewEdgeSetAdaptor -> ListEdgeSet |
247 * NewEdgeSetAdaptor -> ListEdgeSet |
247 * LP: set{Obj,Row,Col}() -> {obj,row,col}() |
248 * LP: set{Obj,Row,Col}() -> {obj,row,col}() |
248 * "label" instead of "id" inside the LGF files |
249 * "label" instead of "id" inside the LGF files |
279 * Step-by-step execution |
280 * Step-by-step execution |
280 * Run from multiple sources |
281 * Run from multiple sources |
281 * Used define stop condition |
282 * Used define stop condition |
282 * Improved "named parameters" |
283 * Improved "named parameters" |
283 + Preflow |
284 + Preflow |
|
285 * Changed interface |
284 * Function type interface |
286 * Function type interface |
285 * Changed interface |
287 + ListGraph/SmartGraph |
286 + ListGraph/SmarGraph |
|
287 * split() splits a node |
288 * split() splits a node |
288 * SnapShot |
289 * SnapShot |
289 Changes |
290 Changes |
290 * Changed namings: |
291 * Changed namings: |
291 * Wrapper -> Adaptor |
292 * Wrapper -> Adaptor |
294 * BoundingBox<> |
295 * BoundingBox<> |
295 * operator+=() -> add() |
296 * operator+=() -> add() |
296 + clear() |
297 + clear() |
297 * Better documentation |
298 * Better documentation |
298 * Several important bugfixes |
299 * Several important bugfixes |
299 * Now lemon should compile without warnings with |
300 * Now LEMON should compile without warnings with |
300 * gcc 3.3, 3.4, 4.0 |
301 * gcc 3.3, 3.4, 4.0 |
301 * Intel C++ Compiler v9.0 |
302 * Intel C++ Compiler v9.0 |
302 |
303 |
303 2005-03-19 Version 0.3.1 Released |
304 2005-03-19 Version 0.3.1 Released |
304 This release fixes a compilation failure bug under cygwin. |
305 This release fixes a compilation failure bug under cygwin. |
305 |
306 |
306 2005-02-21 Version 0.3 released |
307 2005-02-21 Version 0.3 released |
307 |
|
308 New features |
308 New features |
309 + Standardized LEMON exceptions |
309 + Standardized LEMON exceptions |
310 + Undirected Graph |
310 + Undirected Graph |
311 + Standard graph file format, input and output classes for it. |
311 + Standard graph file format, input and output classes for it |
312 + GraphToEps: A simple graph drawer |
312 + GraphToEps: A simple graph drawer |
313 Changes |
313 Changes |
314 * Redesigned Graph infrastructures |
314 * Redesigned Graph infrastructures |
315 * head() -> target(), tail() -> source() |
315 * head() -> target(), tail() -> source() |
316 * Some standard namings have changes: |
316 * Some standard namings have changes: |
317 ValueType -> Value, |
317 ValueType -> Value, |
318 KeyType -> Key, |
318 KeyType -> Key, |
319 ReferenceType ->Reference, |
319 ReferenceType -> Reference, |
320 PointerType -> Pointer |
320 PointerType -> Pointer |
321 * Better documentation |
321 * Better documentation |
322 |
322 |
323 2004-09-30 Version 0.2 released |
323 2004-09-30 Version 0.2 released |