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