[2278] | 1 | 2006-10-31 Version 0.6 Released |
---|
| 2 | * New Features |
---|
| 3 | - Mixed Integer Programming (MIP) support |
---|
| 4 | - interface to GLPK and CPLEX MIP solvers |
---|
| 5 | - Data structures |
---|
| 6 | - Bipatrite graph concepts and implementations |
---|
| 7 | - a Polinomial template class |
---|
| 8 | - RefPtr: a reference counted pointer class |
---|
| 9 | - SimpleBucketHeap |
---|
| 10 | - random.h: Mersenne Twister random number generator |
---|
| 11 | - EdgeLookUp and AllEdgeLookUp |
---|
| 12 | - Tools to find edges between to nodes in time O(log d) |
---|
| 13 | - new matching algorithms |
---|
| 14 | - Bipartite Graph Max Cardinality Matching (Hopcroft-Karp) |
---|
| 15 | - MaxWeightedBipartiteMatching |
---|
| 16 | - MinCostMaxBipartiteMatching |
---|
| 17 | - MaxCardinalitySearch |
---|
| 18 | - MinimalCut in UGraph |
---|
| 19 | - Tabu Search framework |
---|
| 20 | - Minimum Cost Arborescence algorithm |
---|
| 21 | - Edmonds-Karp MaxFlow |
---|
| 22 | - Hao-Orlin algorithm |
---|
| 23 | - eps.h: A simple tool to create .eps pictures. |
---|
| 24 | * Backward incompatibilities/changed namings: |
---|
| 25 | - UndirXyz -> UXyz |
---|
| 26 | - UNDIRGRAPH_TYPEDEFS -> UGRAPH_TYPEDEFS |
---|
| 27 | - GridGraph -> GridUGraph |
---|
| 28 | - LinearHeap -> BucketHeap |
---|
| 29 | - ColorSet -> Palette |
---|
| 30 | - xy -> dim2::Point |
---|
| 31 | - DirPath -> Path |
---|
| 32 | - concept -> concepts (namespace & directory) |
---|
| 33 | - LpSolverBase |
---|
| 34 | - ColName() -> colName |
---|
| 35 | - Coeff() -> coeff() |
---|
| 36 | - MinCostFlow -> SspMinCostFlow |
---|
| 37 | * Repository reorganization: |
---|
| 38 | - glemon has moved to an separate repository |
---|
| 39 | - compilation is conducted by a single makefile |
---|
| 40 | - internal building blocks are now in a separate directory |
---|
| 41 | (lemon/bits) |
---|
| 42 | * Major improvements many algorithms and data structures. |
---|
| 43 | * Several bugfixes |
---|
| 44 | * Compatibility issues: |
---|
| 45 | - known to compile with |
---|
| 46 | - GCC 3.3, 3.4, 4.0, 4.1 |
---|
| 47 | - MinGW, MinGW32 |
---|
| 48 | - Intel C++ 9.x support |
---|
[2265] | 49 | |
---|
[2075] | 50 | 2006-02-03 Version 0.5 Released |
---|
[1945] | 51 | * New features: |
---|
| 52 | - Bfs/Dfs/Dijkstra |
---|
| 53 | + query functions for the next node/edge to be processed |
---|
| 54 | + visitor interface for dfs |
---|
| 55 | - topology.h: small functions for discovering graph topology |
---|
| 56 | + connected components, strongly connected components |
---|
| 57 | + bipartiteness testing |
---|
| 58 | - Shortest paths algorithms: |
---|
| 59 | bellman_ford.h, floyd_warshall.h, johnson.h |
---|
| 60 | - Euler tour iterator for directed and undirected graphs |
---|
| 61 | - Other algorithms: |
---|
| 62 | + dag_shortest_path.h |
---|
| 63 | + fredman_tarjan.h and prim.h for min cost trees |
---|
| 64 | - Bipartite graph concept and implementations |
---|
| 65 | - Graph maps: |
---|
| 66 | + template assign operator |
---|
| 67 | + specialized iterable bool map |
---|
[2075] | 68 | + potential difference map |
---|
[1945] | 69 | + NodeMatrixMap -- Matrix over the nodes |
---|
| 70 | - Maps: |
---|
| 71 | + IterableIntMap |
---|
| 72 | - GUI: |
---|
| 73 | + NewMap window in MapSelector |
---|
| 74 | + Algorithm window and some algorithms (eg. Kruskal) added |
---|
| 75 | - LemonReader: |
---|
| 76 | + exception on non-existent files |
---|
| 77 | - LP interface: |
---|
| 78 | + (Dual)Expr::simplify(double tolerance) added |
---|
| 79 | + getDual() |
---|
| 80 | - GraphToEps: |
---|
| 81 | + negateY() opt |
---|
| 82 | + male/female node shapes :) |
---|
[1947] | 83 | + correct %%BoundingBox handling |
---|
[1945] | 84 | - Tools: |
---|
| 85 | + Timer can be stop()ed and (re)start()ed |
---|
[1947] | 86 | + radix sort algorithm |
---|
[1945] | 87 | + tolerance.h for working with imprecise numbers |
---|
[1947] | 88 | * Backward incompatibilities/changed namings: |
---|
[1713] | 89 | - Access functions of TimeStamp/Timer |
---|
[1947] | 90 | - Undir graph interface: findUEdge, ConUEdgeIt |
---|
[1945] | 91 | - pred -> predEdge renaming in search algorithms |
---|
| 92 | - SnapShot -> Snapshot in {List,Smart}Graph |
---|
| 93 | - NewEdgeSetAdaptor -> ListEdgeSet |
---|
| 94 | - LP: set{Obj,Row,Col}() -> {obj,row,col}() |
---|
| 95 | - "label" instead of "id" inside the LGF files |
---|
| 96 | - UndirGraph -> UGraph, UndirEdge* -> UEdge* |
---|
| 97 | - BipartiteGraph -> BpGraph, Lower/UpperNode* -> A/BNode* |
---|
[2075] | 98 | * Bugfixes in |
---|
[1668] | 99 | - DFS |
---|
| 100 | - Preflow |
---|
[1945] | 101 | - x86_64 connected bugfixes (lemon_reader.h) |
---|
| 102 | - lp.h |
---|
| 103 | * New demos, benchmarks and tools: |
---|
| 104 | - graph_orientation.cc: A thoroughly documented demo application |
---|
| 105 | - runningTimeTest(): a tool to measure running times more precisely |
---|
| 106 | - Demo for topology |
---|
[2075] | 107 | - counter.h: a tool to measure the number of steps of algorithms |
---|
[1945] | 108 | - Some useful scripts: check-compiler, check-integrity |
---|
| 109 | * Other changes: |
---|
| 110 | - Demos and benchmarks are not built by default now. They can be |
---|
| 111 | enabled with the --enable-demo and --enable-benchmark |
---|
| 112 | configure flags. |
---|
| 113 | - GCC 4.0.3 and ICC 9.0 compatibility |
---|
[1713] | 114 | |
---|
[1668] | 115 | 2005-08-27 Version 0.4 Released |
---|
| 116 | * List of new features and changes |
---|
[1713] | 117 | * Changed namings: |
---|
[1668] | 118 | Wrapper -> Adaptor |
---|
| 119 | kruskalEdgeMap() -> kruskal() |
---|
| 120 | kruskalEdgeMap_IteratorOut() -> kruskal() |
---|
| 121 | * BoundinBox<> |
---|
| 122 | * operator+=() -> add() |
---|
| 123 | + clear() |
---|
| 124 | + More and better graph I/O functionalities |
---|
| 125 | + High level uniform LP solver interface to CPLEX and GLKP |
---|
| 126 | * graphToEps() |
---|
| 127 | + Automatic node size and edge width scaling |
---|
| 128 | + Simple color palette tool (ColorSet) |
---|
| 129 | * Bfs/Dfs/Dijkstra |
---|
| 130 | + Step-by-step execution |
---|
| 131 | + Run from multiple sources |
---|
| 132 | + Used define stop condition |
---|
| 133 | + Improved "named parameters" |
---|
| 134 | * Preflow |
---|
| 135 | + Function type interface |
---|
| 136 | + Changed interface |
---|
| 137 | * ListGraph/SmarGraph |
---|
[1670] | 138 | + split() splits a node |
---|
[1668] | 139 | + SnapShot |
---|
| 140 | + New map adaptors |
---|
[1670] | 141 | + New convenience maps |
---|
[1668] | 142 | + IdMap, DescriptorMap |
---|
| 143 | + InDegMap, OutDegMap |
---|
| 144 | + XMap, YMap |
---|
| 145 | + Default graph maps are iterable |
---|
| 146 | + glemon: a graph editor |
---|
| 147 | + Some new demo codes added, the old ones got polished. |
---|
| 148 | * Better documentation |
---|
| 149 | * Several important bugfixes |
---|
| 150 | * Now lemon should compile without warnings with |
---|
| 151 | * gcc 3.3, 3.4, 4.0 |
---|
| 152 | * Intel C++ Compiler v9.0 |
---|
| 153 | |
---|
| 154 | 2005-03-19 Version 0.3.1 Released |
---|
| 155 | * This release fixes a compilation failure bug under cygwin. |
---|
| 156 | |
---|
| 157 | 2005-02-21 Version 0.3 released |
---|
| 158 | * List of new features and changes |
---|
| 159 | * Redesigned Graph infrastructures |
---|
| 160 | + Standardized LEMON exceptions |
---|
| 161 | + Undirected Graph |
---|
| 162 | + Standard graph file format, input and output classes for it. |
---|
| 163 | * head() -> target(), tail() -> source() |
---|
| 164 | * Some standard namings have changes: |
---|
| 165 | ValueType -> Value, |
---|
| 166 | KeyType -> Key, |
---|
| 167 | ReferenceType ->Reference, |
---|
| 168 | PointerType -> Pointer |
---|
| 169 | + GraphToEps: A simple graph drawer |
---|
| 170 | * Better documentation |
---|
| 171 | |
---|
| 172 | 2004-09-30 Version 0.2 released |
---|
| 173 | |
---|