1 | 2006-10-27 Version 0.6 Released |
---|
2 | |
---|
3 | #New |
---|
4 | *functor usage for writeable map adaptors |
---|
5 | *MIP support |
---|
6 | -interface to the cplex MIP solver |
---|
7 | *data structures |
---|
8 | -ListBpUGraph |
---|
9 | -SmartEdgeset |
---|
10 | -RefPtr: a reference counted pointer class |
---|
11 | -two state variant |
---|
12 | -Polinomial template class |
---|
13 | -SimpleBucketHeap |
---|
14 | -even a smaller version |
---|
15 | -tolerance class |
---|
16 | -Tolerance<unsigned int> and Tolerance<unsigned long long int> added |
---|
17 | -the extender system |
---|
18 | -some UGraphExtender /SubUGraphExtenders, DirectUGraphExtender/ |
---|
19 | -adaptor related |
---|
20 | -ResGraphAdaptor with Tolerance |
---|
21 | -SwapBpUGraphAdaptor which swaps the two nodeset of the bipartite graph |
---|
22 | -map related |
---|
23 | -SimpleMap and SimpleWriteMap |
---|
24 | -new map type based on array map for debugging purpose |
---|
25 | -DynamicAsymMatrixMap |
---|
26 | -MatrixMapTraits |
---|
27 | *functions |
---|
28 | -optimality test on random graph |
---|
29 | -implementation of the drand48 functions |
---|
30 | -negative cycle to path converter |
---|
31 | -reserveNode function |
---|
32 | -Mersenne Twister random number generator |
---|
33 | -EdgeLookUp and AllEdgeLookUp |
---|
34 | *scripts |
---|
35 | -script that lists all the header files included directly or indirectly by a certain header file |
---|
36 | -script creates/updates the copyright header of a source file |
---|
37 | *algorithms |
---|
38 | -algorithm group for matchings |
---|
39 | -Bipartite Graph Max Cardinality Matching (Hopcroft-Karp) |
---|
40 | -MaxWeightedBipartiteMatching |
---|
41 | -MinCostMaxBipartiteMatching |
---|
42 | -MaxCardinalitySearch |
---|
43 | -MinimalCut in UGraph |
---|
44 | -tabu search |
---|
45 | -Minimum Cost Arborescence algorithm |
---|
46 | -dual solution computation and interface for algorithm |
---|
47 | -Edmonds-Karp MaxFlow |
---|
48 | -Hao-Orlin algorithm |
---|
49 | |
---|
50 | #Progress in already existing objects: |
---|
51 | *radix sort to ansi compatible |
---|
52 | *map creation based on virtual base class is possible |
---|
53 | *default constructor which allocates empty graphs |
---|
54 | *defaultMap is introdouced, graph maps should not be inherited from the ObserverBase. |
---|
55 | *clarifing alteration observing system |
---|
56 | *resize for static size graph |
---|
57 | *an additional simplier interface for static size graphs. |
---|
58 | *Node operator()(int) for getting node by index |
---|
59 | *int index(Node node) for getting index by node |
---|
60 | *traits for alteration notifiers |
---|
61 | *graph adadptors can be alteration observed |
---|
62 | *count ANodes-BNodes in bipartite graphs |
---|
63 | *the template assign operators and map iterators can be used for adaptors also |
---|
64 | *writeable extension of some maps |
---|
65 | *rot180() added to xy.h |
---|
66 | *change source and target for the bipartite list graph |
---|
67 | *findEdge extension also for the BpUGraphs |
---|
68 | *proper handling of loop edges in the UGraph::findUEdge |
---|
69 | *exported interface to the Graph class |
---|
70 | *new random interface |
---|
71 | *graph imlementations actually provide ReferenceMaps |
---|
72 | *lgf2ps: |
---|
73 | -RGB color related stuff is in color.h now |
---|
74 | -simple class to create .eps figures (eps.h) |
---|
75 | -"Node shapes" added |
---|
76 | -some color constants added (BLACK, WHITE, RED etc) |
---|
77 | -absolute/relative node size/link width scaling |
---|
78 | |
---|
79 | #Taken out: |
---|
80 | *SplitGraph is temporarly deleted |
---|
81 | *SubBidirGraphAdaptor |
---|
82 | *obsolote "id" map handling |
---|
83 | *concepts for extendable and erasable graphs |
---|
84 | *exceptionName() |
---|
85 | *bezier.h |
---|
86 | *functional interfaces |
---|
87 | *UPath |
---|
88 | |
---|
89 | #Rewritten, modificated, improved |
---|
90 | *UnionFindEnum revision |
---|
91 | *countItems |
---|
92 | *findEdges |
---|
93 | *IncEdgeIt goes through on loop edges twice. |
---|
94 | *mining of the clear in heaps |
---|
95 | *SplitGraphAdaptor |
---|
96 | *item sets are written in the order sorted by the labels |
---|
97 | *make explicit constructors |
---|
98 | *snapshot |
---|
99 | -rewritten |
---|
100 | -implemented for SmartUGraph an SmartBpUGraph |
---|
101 | *Node/Edge::operator<() is required by the concept |
---|
102 | *Graph Component concepts |
---|
103 | *disabled the copy constructor and operator- of {List|Smart}[U]Graph. |
---|
104 | *modificated interface: colType() functions |
---|
105 | *made public what() in NodeSetError |
---|
106 | *improvment in exception handling |
---|
107 | -exception safe erase and clear handler |
---|
108 | -proper exception handling in the SmartEdgeSet |
---|
109 | -rethrow of exception missing |
---|
110 | *signaling alterations in BpUGraphs |
---|
111 | *UnionFind |
---|
112 | -takes less space |
---|
113 | -UnionFindEnum |
---|
114 | -changed interface |
---|
115 | *updated the Path concept |
---|
116 | *item readers and writers |
---|
117 | |
---|
118 | #Reorganized: |
---|
119 | *bootstrap: quiet option |
---|
120 | *utility, invalid and traits moved to bits |
---|
121 | *section readers moved to own group |
---|
122 | *separate group for matrices |
---|
123 | *single makefile |
---|
124 | *glemon is moved to own repository |
---|
125 | *graph_component.h -> graph_components.h |
---|
126 | *reference to modules added |
---|
127 | *disable assertions in default behaviour |
---|
128 | *BiVariant moved to lemon/bits/variant.h |
---|
129 | *using abort() instead of exit(1) |
---|
130 | |
---|
131 | #Renamed: |
---|
132 | *Undir -> U |
---|
133 | *Minimum -> Min |
---|
134 | *Work -> Aux |
---|
135 | *UGraphExtender -> UndirectGraphExtender |
---|
136 | -UGraphExtenders with changed meaning |
---|
137 | *GridGraph -> GridUGraph |
---|
138 | *UNDIRGRAPH_TYPEDEFS -> UGRAPH_TYPEDEFS |
---|
139 | *LinearHeap -> BucketHeap |
---|
140 | *UGraphBaseExtender -> UndirGraphExtender |
---|
141 | *BpUGraphBaseExtender merged into BpUGraphExtender |
---|
142 | *StaticGraph to Graph |
---|
143 | *ColorSet to Palette |
---|
144 | *xy -> dim2::Point |
---|
145 | *DirPath to Path |
---|
146 | *concept -> concepts (namespace & directory) |
---|
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 | |
---|