| 1 | 2006-10-27 Version 0.6 Released |
|---|
| 2 | |
|---|
| 3 | #Renamed: |
|---|
| 4 | *Undir -> U |
|---|
| 5 | *Minimum -> Min |
|---|
| 6 | *Work -> Aux |
|---|
| 7 | *UGraphExtender -> UndirectGraphExtender |
|---|
| 8 | -UGraphExtenders with changed meaning |
|---|
| 9 | *GridGraph -> GridUGraph |
|---|
| 10 | *UNDIRGRAPH_TYPEDEFS -> UGRAPH_TYPEDEFS |
|---|
| 11 | *LinearHeap -> BucketHeap |
|---|
| 12 | *UGraphBaseExtender -> UndirGraphExtender |
|---|
| 13 | *BpUGraphBaseExtender merged into BpUGraphExtender |
|---|
| 14 | *StaticGraph to Graph |
|---|
| 15 | *ColorSet to Palette |
|---|
| 16 | *xy -> dim2::Point |
|---|
| 17 | *DirPath to Path |
|---|
| 18 | *concept -> concepts (namespace & directory) |
|---|
| 19 | |
|---|
| 20 | #Reorganized: |
|---|
| 21 | *bootstrap: quiet option |
|---|
| 22 | *utility, invalid and traits moved to bits |
|---|
| 23 | *section readers moved to own group |
|---|
| 24 | *separate group for matrices |
|---|
| 25 | *single makefile |
|---|
| 26 | *glemon is moved to own repository |
|---|
| 27 | *graph_component.h -> graph_components.h |
|---|
| 28 | *reference to modules added |
|---|
| 29 | *disable assertions in default behaviour |
|---|
| 30 | *BiVariant moved to lemon/bits/variant.h |
|---|
| 31 | *using abort() instead of exit(1) |
|---|
| 32 | |
|---|
| 33 | #Taken out: |
|---|
| 34 | *SplitGraph is temporarly deleted |
|---|
| 35 | *SubBidirGraphAdaptor |
|---|
| 36 | *obsolote "id" map handling |
|---|
| 37 | *concepts for extendable and erasable graphs |
|---|
| 38 | *exceptionName() |
|---|
| 39 | *bezier.h |
|---|
| 40 | *functional interfaces |
|---|
| 41 | *UPath |
|---|
| 42 | |
|---|
| 43 | #Rewritten, modificated, improved |
|---|
| 44 | *UnionFindEnum revision |
|---|
| 45 | *countItems |
|---|
| 46 | *findEdges |
|---|
| 47 | *IncEdgeIt goes through on loop edges twice. |
|---|
| 48 | *mining of the clear in heaps |
|---|
| 49 | *SplitGraphAdaptor |
|---|
| 50 | *item sets are written in the order sorted by the labels |
|---|
| 51 | *make explicit constructors |
|---|
| 52 | *snapshot |
|---|
| 53 | -rewritten |
|---|
| 54 | -implemented for SmartUGraph an SmartBpUGraph |
|---|
| 55 | *Node/Edge::operator<() is required by the concept |
|---|
| 56 | *Graph Component concepts |
|---|
| 57 | *disabled the copy constructor and operator- of {List|Smart}[U]Graph. |
|---|
| 58 | *modificated interface: colType() functions |
|---|
| 59 | *made public what() in NodeSetError |
|---|
| 60 | *improvment in exception handling |
|---|
| 61 | -exception safe erase and clear handler |
|---|
| 62 | -proper exception handling in the SmartEdgeSet |
|---|
| 63 | -rethrow of exception missing |
|---|
| 64 | *signaling alterations in BpUGraphs |
|---|
| 65 | *UnionFind |
|---|
| 66 | -takes less space |
|---|
| 67 | -UnionFindEnum |
|---|
| 68 | -changed interface |
|---|
| 69 | *updated the Path concept |
|---|
| 70 | *item readers and writers |
|---|
| 71 | |
|---|
| 72 | #New |
|---|
| 73 | *functor usage for writeable map adaptors |
|---|
| 74 | *MIP support |
|---|
| 75 | -interface to the cplex MIP solver |
|---|
| 76 | *data structures |
|---|
| 77 | -ListBpUGraph |
|---|
| 78 | -SmartEdgeset |
|---|
| 79 | -RefPtr: a reference counted pointer class |
|---|
| 80 | -two state variant |
|---|
| 81 | -Polinomial template class |
|---|
| 82 | -SimpleBucketHeap |
|---|
| 83 | -even a smaller version |
|---|
| 84 | -tolerance class |
|---|
| 85 | -Tolerance<unsigned int> and Tolerance<unsigned long long int> added |
|---|
| 86 | -the extender system |
|---|
| 87 | -some UGraphExtender /SubUGraphExtenders, DirectUGraphExtender/ |
|---|
| 88 | -adaptor related |
|---|
| 89 | -ResGraphAdaptor with Tolerance |
|---|
| 90 | -SwapBpUGraphAdaptor which swaps the two nodeset of the bipartite graph |
|---|
| 91 | -map related |
|---|
| 92 | -SimpleMap and SimpleWriteMap |
|---|
| 93 | -new map type based on array map for debugging purpose |
|---|
| 94 | -DynamicAsymMatrixMap |
|---|
| 95 | -MatrixMapTraits |
|---|
| 96 | *functions |
|---|
| 97 | -optimality test on random graph |
|---|
| 98 | -implementation of the drand48 functions |
|---|
| 99 | -negative cycle to path converter |
|---|
| 100 | -reserveNode function |
|---|
| 101 | -Mersenne Twister random number generator |
|---|
| 102 | -EdgeLookUp and AllEdgeLookUp |
|---|
| 103 | *scripts |
|---|
| 104 | -script that lists all the header files included directly or indirectly by a certain header file |
|---|
| 105 | -script creates/updates the copyright header of a source file |
|---|
| 106 | *algorithms |
|---|
| 107 | -algorithm group for matchings |
|---|
| 108 | -Bipartite Graph Max Cardinality Matching (Hopcroft-Karp) |
|---|
| 109 | -MaxWeightedBipartiteMatching |
|---|
| 110 | -MinCostMaxBipartiteMatching |
|---|
| 111 | -MaxCardinalitySearch |
|---|
| 112 | -MinimalCut in UGraph |
|---|
| 113 | -tabu search |
|---|
| 114 | -Minimum Cost Arborescence algorithm |
|---|
| 115 | -dual solution computation and interface for algorithm |
|---|
| 116 | -Edmonds-Karp MaxFlow |
|---|
| 117 | -Hao-Orlin algorithm |
|---|
| 118 | |
|---|
| 119 | #Progress in already existing objects: |
|---|
| 120 | *radix sort to ansi compatible |
|---|
| 121 | *map creation based on virtual base class is possible |
|---|
| 122 | *default constructor which allocates empty graphs |
|---|
| 123 | *defaultMap is introdouced, graph maps should not be inherited from the ObserverBase. |
|---|
| 124 | *clarifing alteration observing system |
|---|
| 125 | *resize for static size graph |
|---|
| 126 | *an additional simplier interface for static size graphs. |
|---|
| 127 | *Node operator()(int) for getting node by index |
|---|
| 128 | *int index(Node node) for getting index by node |
|---|
| 129 | *traits for alteration notifiers |
|---|
| 130 | *graph adadptors can be alteration observed |
|---|
| 131 | *count ANodes-BNodes in bipartite graphs |
|---|
| 132 | *the template assign operators and map iterators can be used for adaptors also |
|---|
| 133 | *writeable extension of some maps |
|---|
| 134 | *rot180() added to xy.h |
|---|
| 135 | *change source and target for the bipartite list graph |
|---|
| 136 | *findEdge extension also for the BpUGraphs |
|---|
| 137 | *proper handling of loop edges in the UGraph::findUEdge |
|---|
| 138 | *exported interface to the Graph class |
|---|
| 139 | *new random interface |
|---|
| 140 | *graph imlementations actually provide ReferenceMaps |
|---|
| 141 | *lgf2ps: |
|---|
| 142 | -RGB color related stuff is in color.h now |
|---|
| 143 | -simple class to create .eps figures (eps.h) |
|---|
| 144 | -"Node shapes" added |
|---|
| 145 | -some color constants added (BLACK, WHITE, RED etc) |
|---|
| 146 | -absolute/relative node size/link width scaling |
|---|
| 147 | |
|---|
| 148 | #Compatibility issues: |
|---|
| 149 | *compilation with G++ -ansi |
|---|
| 150 | *gcc-4.1 |
|---|
| 151 | *NaN checking to be conform to MinGW32 |
|---|
| 152 | *MinGW, MinGW32 |
|---|
| 153 | *long long just for gnu compilers |
|---|
| 154 | *CPLEX 9.x support |
|---|
| 155 | *turned off 32bit specific tests. |
|---|
| 156 | |
|---|
| 157 | #Beyond the aboves several bugfix and documentation improvement is made, new demos, benchmarks are implemented. |
|---|
| 158 | |
|---|
| 159 | 2006-02-03 Version 0.5 Released |
|---|
| 160 | * New features: |
|---|
| 161 | - Bfs/Dfs/Dijkstra |
|---|
| 162 | + query functions for the next node/edge to be processed |
|---|
| 163 | + visitor interface for dfs |
|---|
| 164 | - topology.h: small functions for discovering graph topology |
|---|
| 165 | + connected components, strongly connected components |
|---|
| 166 | + bipartiteness testing |
|---|
| 167 | - Shortest paths algorithms: |
|---|
| 168 | bellman_ford.h, floyd_warshall.h, johnson.h |
|---|
| 169 | - Euler tour iterator for directed and undirected graphs |
|---|
| 170 | - Other algorithms: |
|---|
| 171 | + dag_shortest_path.h |
|---|
| 172 | + fredman_tarjan.h and prim.h for min cost trees |
|---|
| 173 | - Bipartite graph concept and implementations |
|---|
| 174 | - Graph maps: |
|---|
| 175 | + template assign operator |
|---|
| 176 | + specialized iterable bool map |
|---|
| 177 | + potential difference map |
|---|
| 178 | + NodeMatrixMap -- Matrix over the nodes |
|---|
| 179 | - Maps: |
|---|
| 180 | + IterableIntMap |
|---|
| 181 | - GUI: |
|---|
| 182 | + NewMap window in MapSelector |
|---|
| 183 | + Algorithm window and some algorithms (eg. Kruskal) added |
|---|
| 184 | - LemonReader: |
|---|
| 185 | + exception on non-existent files |
|---|
| 186 | - LP interface: |
|---|
| 187 | + (Dual)Expr::simplify(double tolerance) added |
|---|
| 188 | + getDual() |
|---|
| 189 | - GraphToEps: |
|---|
| 190 | + negateY() opt |
|---|
| 191 | + male/female node shapes :) |
|---|
| 192 | + correct %%BoundingBox handling |
|---|
| 193 | - Tools: |
|---|
| 194 | + Timer can be stop()ed and (re)start()ed |
|---|
| 195 | + radix sort algorithm |
|---|
| 196 | + tolerance.h for working with imprecise numbers |
|---|
| 197 | * Backward incompatibilities/changed namings: |
|---|
| 198 | - Access functions of TimeStamp/Timer |
|---|
| 199 | - Undir graph interface: findUEdge, ConUEdgeIt |
|---|
| 200 | - pred -> predEdge renaming in search algorithms |
|---|
| 201 | - SnapShot -> Snapshot in {List,Smart}Graph |
|---|
| 202 | - NewEdgeSetAdaptor -> ListEdgeSet |
|---|
| 203 | - LP: set{Obj,Row,Col}() -> {obj,row,col}() |
|---|
| 204 | - "label" instead of "id" inside the LGF files |
|---|
| 205 | - UndirGraph -> UGraph, UndirEdge* -> UEdge* |
|---|
| 206 | - BipartiteGraph -> BpGraph, Lower/UpperNode* -> A/BNode* |
|---|
| 207 | * Bugfixes in |
|---|
| 208 | - DFS |
|---|
| 209 | - Preflow |
|---|
| 210 | - x86_64 connected bugfixes (lemon_reader.h) |
|---|
| 211 | - lp.h |
|---|
| 212 | * New demos, benchmarks and tools: |
|---|
| 213 | - graph_orientation.cc: A thoroughly documented demo application |
|---|
| 214 | - runningTimeTest(): a tool to measure running times more precisely |
|---|
| 215 | - Demo for topology |
|---|
| 216 | - counter.h: a tool to measure the number of steps of algorithms |
|---|
| 217 | - Some useful scripts: check-compiler, check-integrity |
|---|
| 218 | * Other changes: |
|---|
| 219 | - Demos and benchmarks are not built by default now. They can be |
|---|
| 220 | enabled with the --enable-demo and --enable-benchmark |
|---|
| 221 | configure flags. |
|---|
| 222 | - GCC 4.0.3 and ICC 9.0 compatibility |
|---|
| 223 | |
|---|
| 224 | 2005-08-27 Version 0.4 Released |
|---|
| 225 | * List of new features and changes |
|---|
| 226 | * Changed namings: |
|---|
| 227 | Wrapper -> Adaptor |
|---|
| 228 | kruskalEdgeMap() -> kruskal() |
|---|
| 229 | kruskalEdgeMap_IteratorOut() -> kruskal() |
|---|
| 230 | * BoundinBox<> |
|---|
| 231 | * operator+=() -> add() |
|---|
| 232 | + clear() |
|---|
| 233 | + More and better graph I/O functionalities |
|---|
| 234 | + High level uniform LP solver interface to CPLEX and GLKP |
|---|
| 235 | * graphToEps() |
|---|
| 236 | + Automatic node size and edge width scaling |
|---|
| 237 | + Simple color palette tool (ColorSet) |
|---|
| 238 | * Bfs/Dfs/Dijkstra |
|---|
| 239 | + Step-by-step execution |
|---|
| 240 | + Run from multiple sources |
|---|
| 241 | + Used define stop condition |
|---|
| 242 | + Improved "named parameters" |
|---|
| 243 | * Preflow |
|---|
| 244 | + Function type interface |
|---|
| 245 | + Changed interface |
|---|
| 246 | * ListGraph/SmarGraph |
|---|
| 247 | + split() splits a node |
|---|
| 248 | + SnapShot |
|---|
| 249 | + New map adaptors |
|---|
| 250 | + New convenience maps |
|---|
| 251 | + IdMap, DescriptorMap |
|---|
| 252 | + InDegMap, OutDegMap |
|---|
| 253 | + XMap, YMap |
|---|
| 254 | + Default graph maps are iterable |
|---|
| 255 | + glemon: a graph editor |
|---|
| 256 | + Some new demo codes added, the old ones got polished. |
|---|
| 257 | * Better documentation |
|---|
| 258 | * Several important bugfixes |
|---|
| 259 | * Now lemon should compile without warnings with |
|---|
| 260 | * gcc 3.3, 3.4, 4.0 |
|---|
| 261 | * Intel C++ Compiler v9.0 |
|---|
| 262 | |
|---|
| 263 | 2005-03-19 Version 0.3.1 Released |
|---|
| 264 | * This release fixes a compilation failure bug under cygwin. |
|---|
| 265 | |
|---|
| 266 | 2005-02-21 Version 0.3 released |
|---|
| 267 | * List of new features and changes |
|---|
| 268 | * Redesigned Graph infrastructures |
|---|
| 269 | + Standardized LEMON exceptions |
|---|
| 270 | + Undirected Graph |
|---|
| 271 | + Standard graph file format, input and output classes for it. |
|---|
| 272 | * head() -> target(), tail() -> source() |
|---|
| 273 | * Some standard namings have changes: |
|---|
| 274 | ValueType -> Value, |
|---|
| 275 | KeyType -> Key, |
|---|
| 276 | ReferenceType ->Reference, |
|---|
| 277 | PointerType -> Pointer |
|---|
| 278 | + GraphToEps: A simple graph drawer |
|---|
| 279 | * Better documentation |
|---|
| 280 | |
|---|
| 281 | 2004-09-30 Version 0.2 released |
|---|
| 282 | |
|---|
