hegyi@2600
|
1 |
2008-02-08 Version 0.7 released
|
hegyi@2601
|
2 |
New Features
|
hegyi@2601
|
3 |
+ new data structures
|
hegyi@2601
|
4 |
* classes
|
hegyi@2601
|
5 |
StaticGraph
|
hegyi@2600
|
6 |
ExtendFindEnum
|
hegyi@2600
|
7 |
BfsVisitor class
|
hegyi@2600
|
8 |
Bipartite partitions based on visitors
|
hegyi@2601
|
9 |
* helper class for checking existence of a nested class
|
hegyi@2601
|
10 |
* general mapping based variant type
|
hegyi@2601
|
11 |
* IntegerMap
|
hegyi@2601
|
12 |
+ new algoritmhs
|
hegyi@2601
|
13 |
* Lagrange relaxation based algorithm for the delay constrained least cost path problem
|
hegyi@2601
|
14 |
* a preflow based general network circulation algorithm
|
hegyi@2601
|
15 |
* 2-approximation of Steiner-tree problem
|
kpeter@2606
|
16 |
* two heuristics for minimum cut algorithms (http://www.avglab.com/andrew/pub/neci-tr-96-132.ps)
|
hegyi@2601
|
17 |
* Gomory-Hu tree algorithm
|
hegyi@2601
|
18 |
* Edmond's Blossom shrinking algorithm
|
hegyi@2601
|
19 |
* minimum mean cycle algorithm
|
hegyi@2601
|
20 |
* Goldberg-Tarjan algorithm (Preflow with Dynamic Trees)
|
hegyi@2601
|
21 |
* Dinitz-Sleator-Tarjan (Blocking flow with Dynamic Tree)
|
hegyi@2601
|
22 |
* min cost flow algorithms:
|
hegyi@2601
|
23 |
* successive shortest path algorithm
|
hegyi@2601
|
24 |
* capacity scaling algorithm
|
hegyi@2601
|
25 |
* simple cycle canceling algorithm
|
hegyi@2601
|
26 |
* minimum mean cycle canceling algorithm
|
hegyi@2601
|
27 |
* cost scaling algorithm
|
hegyi@2601
|
28 |
* network simplex algorithm
|
kpeter@2603
|
29 |
* min cost maximum flow algorithm
|
hegyi@2601
|
30 |
+ new functions and tools
|
kpeter@2603
|
31 |
* ArgParser, a command line argument parser
|
hegyi@2601
|
32 |
* DistLog, a tool for measuring one and two dimensional distributions
|
hegyi@2601
|
33 |
* undirected minimum cut benchmarking
|
hegyi@2601
|
34 |
* tools/lgf-gen.cc, a random graph generator
|
hegyi@2601
|
35 |
* BpUGraphReader and Writer
|
hegyi@2601
|
36 |
* DynEdgeLookUp implementation based on splay trees
|
hegyi@2601
|
37 |
* MACROS for debug map usage
|
hegyi@2601
|
38 |
+ new distributions (Gaussian, exponential, Gamma, two dimensional random, buffered bit generation)
|
hegyi@2601
|
39 |
+ push-relabel type algorithm related additions
|
hegyi@2601
|
40 |
* Elevator, a class for handling item labels in push-relabel type algorithms
|
hegyi@2601
|
41 |
* a push/relabel type max cardinality matching implementation
|
hegyi@2601
|
42 |
* some query function for push-relabel based matching
|
hegyi@2601
|
43 |
+ LP related additions
|
hegyi@2601
|
44 |
* Soplex support
|
hegyi@2601
|
45 |
* ColIt class
|
hegyi@2601
|
46 |
* new functions (simplify(), isFinite(), row and col getter function)
|
hegyi@2601
|
47 |
* _setColCoeff and _setRowCoeff parameters
|
hegyi@2601
|
48 |
* section reader and writer for LEMON IO
|
hegyi@2601
|
49 |
* equality-type constraint can now be added to a LP
|
hegyi@2601
|
50 |
* virtual functions of class LpCplex
|
hegyi@2601
|
51 |
* some query functions for GLPK
|
hegyi@2601
|
52 |
+ demos
|
hegyi@2601
|
53 |
* preflow based general network circulation demo
|
hegyi@2601
|
54 |
* Steiner 2-approximation demo
|
hegyi@2601
|
55 |
* demo for SAT problems
|
hegyi@2601
|
56 |
* sample input for sat-2 and sat demos
|
hegyi@2601
|
57 |
+ tests for
|
hegyi@2601
|
58 |
* graph copies
|
hegyi@2601
|
59 |
* random.h
|
hegyi@2601
|
60 |
* max weighted matchings
|
hegyi@2601
|
61 |
+ planarity related additions
|
hegyi@2601
|
62 |
* checking and embedding
|
hegyi@2601
|
63 |
* planar grid embedding
|
hegyi@2601
|
64 |
* planar graph coloring
|
hegyi@2601
|
65 |
+ bipartite matchings
|
hegyi@2601
|
66 |
* common interface
|
hegyi@2601
|
67 |
* Query functions: aMatching and bMatching
|
hegyi@2601
|
68 |
* ANodeMap<UEdge> matching map
|
hegyi@2601
|
69 |
* BNodeMap<bool> barrier map
|
hegyi@2601
|
70 |
Repository reorganization
|
hegyi@2601
|
71 |
* script for automatic checking of SVN commit's consistency
|
hegyi@2601
|
72 |
* automatic doc generation from the SVN trunk
|
hegyi@2601
|
73 |
* check for gcc version 3.3, 3.4, 4.0 and 4.1.2 as well
|
hegyi@2601
|
74 |
* reorganization of the modules and groups
|
hegyi@2601
|
75 |
* a tools directory added for useful executables codes
|
hegyi@2601
|
76 |
* doxygen
|
hegyi@2601
|
77 |
* renaming topology doxygen group to graph_prop doxygen group
|
hegyi@2601
|
78 |
* introducing planar doxygen group
|
hegyi@2601
|
79 |
Changes
|
hegyi@2601
|
80 |
* redesigned
|
hegyi@2601
|
81 |
* undirected edgesets (like the smart graph or ugraph)
|
hegyi@2601
|
82 |
* interface of MaxMatching and UnionFindEnum
|
hegyi@2601
|
83 |
* interface of maximum flow algorithms
|
hegyi@2601
|
84 |
* Kruskal algorithm
|
hegyi@2601
|
85 |
* augmenting path based bipartite matching
|
hegyi@2601
|
86 |
Improvements
|
hegyi@2601
|
87 |
* graph copy
|
hegyi@2601
|
88 |
* preliminary support for static graphs
|
hegyi@2601
|
89 |
* added BpUGraphCopy
|
hegyi@2601
|
90 |
* Bfs/Dfs/Dijkstra
|
hegyi@2601
|
91 |
* conditional execution until the target is reached
|
hegyi@2601
|
92 |
* modified start() function in Dfs and Dijkstra classes to give back reached edge/node
|
hegyi@2601
|
93 |
* return the temporary distance of the current node
|
kpeter@2603
|
94 |
* using operation traits in Dijkstra
|
hegyi@2601
|
95 |
* patch for retrieving reached/processed node
|
hegyi@2601
|
96 |
* prescaling can be turned off in GraphToEps
|
hegyi@2601
|
97 |
* better handling of inexact computations
|
hegyi@2601
|
98 |
* easier inverse
|
hegyi@2601
|
99 |
* faster geometric minimum spanning tree algorithm
|
hegyi@2601
|
100 |
* new implementation of undirected graphs
|
hegyi@2601
|
101 |
* Hao-Orlin algorithm became epsilon-safe
|
hegyi@2601
|
102 |
* LpSoplex
|
hegyi@2601
|
103 |
* added getter functions
|
hegyi@2601
|
104 |
* better m4 file
|
hegyi@2601
|
105 |
* better handling of unsolved lps
|
hegyi@2601
|
106 |
* allowing 'string' type quoting for item reading and writing
|
hegyi@2601
|
107 |
* clear() function for union-find structures
|
hegyi@2601
|
108 |
* hacking MIP is possible without integer variables
|
hegyi@2601
|
109 |
* space reservation for SmartGraph
|
hegyi@2601
|
110 |
* path
|
hegyi@2601
|
111 |
* PathNodeIt
|
hegyi@2600
|
112 |
PathWriter/Reader structures
|
hegyi@2600
|
113 |
Distinct MapSet readers and writers
|
hegyi@2601
|
114 |
* more simple interface for PathDumper
|
hegyi@2601
|
115 |
Updated
|
hegyi@2601
|
116 |
* tutorial for
|
hegyi@2601
|
117 |
* algorithms
|
hegyi@2601
|
118 |
* graph visualization
|
hegyi@2601
|
119 |
* documentation
|
hegyi@2601
|
120 |
Backward incompatibilities/changed namings
|
hegyi@2601
|
121 |
* min_cut.h => nagamochi_ibaraki.h
|
hegyi@2601
|
122 |
* clone => build
|
hegyi@2601
|
123 |
* RevIt => RevEdgeIt
|
hegyi@2601
|
124 |
* _FixId => LpId
|
hegyi@2601
|
125 |
* setObj => obj
|
hegyi@2601
|
126 |
* is_min => isMin
|
hegyi@2601
|
127 |
* is_max => isMax
|
hegyi@2601
|
128 |
* ball2() => disc()
|
hegyi@2601
|
129 |
* state_enum => State
|
hegyi@2601
|
130 |
* getNotifier => notifier
|
hegyi@2601
|
131 |
* using LEMON_ASSERT instead of LogicError()
|
hegyi@2601
|
132 |
* uedgeset is an alias for edgeset
|
hegyi@2601
|
133 |
* CPXMIP_OPTIMAL_TOL status is considered as OPTIMAL too
|
hegyi@2601
|
134 |
* removed "Type" suffix from typedefs
|
hegyi@2601
|
135 |
* lower case local variables
|
hegyi@2601
|
136 |
Removed
|
hegyi@2600
|
137 |
- template Map template parameter from InvertableMaps
|
kpeter@2603
|
138 |
- union-find Item template parameter
|
hegyi@2600
|
139 |
- strict checking
|
hegyi@2600
|
140 |
- some automatic callback generation
|
hegyi@2601
|
141 |
- '-Wshadow' seemed too strict therefore removed
|
hegyi@2601
|
142 |
Several bugfixes
|
hegyi@2600
|
143 |
|
alpar@2278
|
144 |
2006-10-31 Version 0.6 Released
|
hegyi@2601
|
145 |
GLEMON has moved to a separate repository
|
hegyi@2601
|
146 |
(https://hugo.cs.elte.hu/svn/glemon/trunk)
|
hegyi@2601
|
147 |
New Features
|
hegyi@2601
|
148 |
+ Mixed Integer Programming (MIP) support
|
hegyi@2601
|
149 |
+ interface to GLPK and CPLEX MIP solvers
|
hegyi@2601
|
150 |
+ Data structures
|
hegyi@2601
|
151 |
* Bipatrite graph concepts and implementations
|
hegyi@2601
|
152 |
* a Polinomial template class
|
hegyi@2601
|
153 |
* RefPtr: a reference counted pointer class
|
hegyi@2601
|
154 |
* SimpleBucketHeap
|
hegyi@2601
|
155 |
+ random.h: Mersenne Twister random number generator
|
hegyi@2601
|
156 |
+ EdgeLookUp and AllEdgeLookUp
|
hegyi@2601
|
157 |
+ Tools to find edges between to nodes in time O(log d)
|
hegyi@2601
|
158 |
+ new matching algorithms
|
hegyi@2601
|
159 |
+ Bipartite Graph Max Cardinality Matching (Hopcroft-Karp)
|
hegyi@2601
|
160 |
+ MaxWeightedBipartiteMatching
|
hegyi@2601
|
161 |
+ MinCostMaxBipartiteMatching
|
hegyi@2601
|
162 |
+ MaxCardinalitySearch
|
hegyi@2601
|
163 |
+ MinimalCut in UGraph
|
hegyi@2601
|
164 |
+ Tabu Search framework
|
hegyi@2601
|
165 |
+ Minimum Cost Arborescence algorithm
|
hegyi@2601
|
166 |
+ Edmonds-Karp MaxFlow
|
hegyi@2601
|
167 |
+ Hao-Orlin algorithm
|
hegyi@2601
|
168 |
+ eps.h: A simple tool to create .eps pictures.
|
hegyi@2601
|
169 |
Backward incompatibilities/changed namings:
|
hegyi@2601
|
170 |
* UndirXyz -> UXyz
|
hegyi@2601
|
171 |
* UNDIRGRAPH_TYPEDEFS -> UGRAPH_TYPEDEFS
|
hegyi@2601
|
172 |
* GridGraph -> GridUGraph
|
hegyi@2601
|
173 |
* LinearHeap -> BucketHeap
|
hegyi@2601
|
174 |
* ColorSet -> Palette
|
hegyi@2601
|
175 |
* xy -> dim2::Point
|
hegyi@2601
|
176 |
* DirPath -> Path
|
hegyi@2601
|
177 |
* concept -> concepts (namespace & directory)
|
hegyi@2601
|
178 |
* LpSolverBase
|
hegyi@2601
|
179 |
* ColName() -> colName
|
hegyi@2601
|
180 |
* Coeff() -> coeff()
|
hegyi@2601
|
181 |
* MinCostFlow -> SspMinCostFlow
|
hegyi@2601
|
182 |
Repository reorganization:
|
hegyi@2601
|
183 |
* compilation is conducted by a single makefile
|
hegyi@2601
|
184 |
* internal building blocks are now in a separate directory
|
hegyi@2601
|
185 |
(lemon/bits)
|
hegyi@2601
|
186 |
Major improvements of many algorithms and data structures
|
hegyi@2601
|
187 |
Several bugfixes
|
hegyi@2601
|
188 |
Compatibility issues:
|
hegyi@2601
|
189 |
* known to compile with
|
hegyi@2601
|
190 |
* GCC 3.3, 3.4, 4.0, 4.1
|
hegyi@2601
|
191 |
* MinGW, MinGW32
|
hegyi@2601
|
192 |
* Intel C++ 9.x support
|
hegyi@2265
|
193 |
|
athos@2075
|
194 |
2006-02-03 Version 0.5 Released
|
hegyi@2601
|
195 |
New features
|
hegyi@2601
|
196 |
+ Shortest paths algorithms
|
hegyi@2601
|
197 |
* bellman_ford.h
|
hegyi@2601
|
198 |
* floyd_warshall.h
|
hegyi@2601
|
199 |
* johnson.h
|
hegyi@2601
|
200 |
+ Euler tour iterator for directed and undirected graphs
|
hegyi@2601
|
201 |
+ Other algorithms:
|
hegyi@2601
|
202 |
* dag_shortest_path.h
|
hegyi@2601
|
203 |
* fredman_tarjan.h and prim.h for min cost trees
|
hegyi@2601
|
204 |
+ Bipartite graph concept and implementations
|
hegyi@2601
|
205 |
+ Graph maps:
|
hegyi@2601
|
206 |
* template assign operator
|
hegyi@2601
|
207 |
* specialized iterable bool map
|
hegyi@2601
|
208 |
* potential difference map
|
hegyi@2601
|
209 |
* NodeMatrixMap -- Matrix over the nodes
|
hegyi@2601
|
210 |
+ Maps:
|
hegyi@2601
|
211 |
* IterableIntMap
|
hegyi@2601
|
212 |
+ Tools:
|
hegyi@2601
|
213 |
* Timer can be stop()ed and (re)start()ed
|
hegyi@2601
|
214 |
* radix sort algorithm
|
hegyi@2601
|
215 |
* tolerance.h for working with imprecise numbers
|
hegyi@2601
|
216 |
New demos, benchmarks and tools
|
hegyi@2601
|
217 |
+ graph_orientation.cc: A thoroughly documented demo application
|
hegyi@2601
|
218 |
+ runningTimeTest(): a tool to measure running times more precisely
|
hegyi@2601
|
219 |
+ Demo for topology
|
hegyi@2601
|
220 |
+ counter.h: a tool to measure the number of steps of algorithms
|
hegyi@2601
|
221 |
+ Some useful scripts: check-compiler, check-integrity
|
hegyi@2601
|
222 |
Improvements
|
hegyi@2601
|
223 |
+ Bfs/Dfs/Dijkstra
|
hegyi@2601
|
224 |
* query functions for the next node/edge to be processed
|
hegyi@2601
|
225 |
* visitor interface for dfs
|
hegyi@2601
|
226 |
+ topology.h: small functions for discovering graph topology
|
hegyi@2601
|
227 |
* connected components, strongly connected components
|
hegyi@2601
|
228 |
* bipartiteness testing
|
hegyi@2601
|
229 |
+ GUI:
|
hegyi@2601
|
230 |
* NewMap window in MapSelector
|
hegyi@2601
|
231 |
* Algorithm window and some algorithms (eg. Kruskal) added
|
hegyi@2601
|
232 |
+ LemonReader:
|
hegyi@2601
|
233 |
* exception on non-existent files
|
hegyi@2601
|
234 |
+ LP interface:
|
hegyi@2601
|
235 |
* (Dual)Expr::simplify(double tolerance) added
|
hegyi@2601
|
236 |
* getDual()
|
hegyi@2601
|
237 |
+ GraphToEps:
|
hegyi@2601
|
238 |
* negateY() opt
|
hegyi@2601
|
239 |
* male/female node shapes :)
|
kpeter@2606
|
240 |
* correct %%BoundingBox handling
|
hegyi@2601
|
241 |
Backward incompatibilities/changed namings:
|
hegyi@2601
|
242 |
* Access functions of TimeStamp/Timer
|
kpeter@2603
|
243 |
* Undirected graph interface: findUEdge, ConUEdgeIt
|
hegyi@2601
|
244 |
* pred -> predEdge renaming in search algorithms
|
hegyi@2601
|
245 |
* SnapShot -> Snapshot in {List,Smart}Graph
|
hegyi@2601
|
246 |
* NewEdgeSetAdaptor -> ListEdgeSet
|
hegyi@2601
|
247 |
* LP: set{Obj,Row,Col}() -> {obj,row,col}()
|
hegyi@2601
|
248 |
* "label" instead of "id" inside the LGF files
|
hegyi@2601
|
249 |
* UndirGraph -> UGraph, UndirEdge* -> UEdge*
|
hegyi@2601
|
250 |
* BipartiteGraph -> BpGraph, Lower/UpperNode* -> A/BNode*
|
hegyi@2601
|
251 |
Bugfixes in
|
hegyi@2601
|
252 |
* DFS
|
hegyi@2601
|
253 |
* Preflow
|
hegyi@2601
|
254 |
* x86_64 connected bugfixes (lemon_reader.h)
|
hegyi@2601
|
255 |
* lp.h
|
hegyi@2601
|
256 |
Other changes
|
hegyi@2601
|
257 |
* Demos and benchmarks are not built by default now. They can be
|
hegyi@2601
|
258 |
* enabled with the --enable-demo and --enable-benchmark
|
hegyi@2601
|
259 |
* configure flags.
|
hegyi@2601
|
260 |
* GCC 4.0.3 and ICC 9.0 compatibility
|
hegyi@2601
|
261 |
|
alpar@1668
|
262 |
2005-08-27 Version 0.4 Released
|
hegyi@2601
|
263 |
New features
|
hegyi@2601
|
264 |
+ More and better graph I/O functionalities
|
hegyi@2601
|
265 |
+ High level uniform LP solver interface to CPLEX and GLKP
|
hegyi@2601
|
266 |
+ New map adaptors
|
hegyi@2601
|
267 |
+ New convenience maps
|
hegyi@2601
|
268 |
* IdMap, DescriptorMap
|
hegyi@2601
|
269 |
* InDegMap, OutDegMap
|
hegyi@2601
|
270 |
* XMap, YMap
|
hegyi@2601
|
271 |
+ Default graph maps are iterable
|
hegyi@2601
|
272 |
+ glemon: a graph editor
|
hegyi@2601
|
273 |
+ Some new demo codes added, the old ones got polished.
|
hegyi@2601
|
274 |
Improvements
|
hegyi@2601
|
275 |
+ graphToEps()
|
hegyi@2601
|
276 |
* Automatic node size and edge width scaling
|
hegyi@2601
|
277 |
* Simple color palette tool (ColorSet)
|
hegyi@2601
|
278 |
+ Bfs/Dfs/Dijkstra
|
hegyi@2601
|
279 |
* Step-by-step execution
|
hegyi@2601
|
280 |
* Run from multiple sources
|
hegyi@2601
|
281 |
* Used define stop condition
|
hegyi@2601
|
282 |
* Improved "named parameters"
|
hegyi@2601
|
283 |
+ Preflow
|
kpeter@2603
|
284 |
* Changed interface
|
hegyi@2601
|
285 |
* Function type interface
|
kpeter@2603
|
286 |
+ ListGraph/SmartGraph
|
hegyi@2601
|
287 |
* split() splits a node
|
hegyi@2601
|
288 |
* SnapShot
|
hegyi@2601
|
289 |
Changes
|
hegyi@2601
|
290 |
* Changed namings:
|
hegyi@2601
|
291 |
* Wrapper -> Adaptor
|
hegyi@2601
|
292 |
* kruskalEdgeMap() -> kruskal()
|
hegyi@2601
|
293 |
* kruskalEdgeMap_IteratorOut() -> kruskal()
|
hegyi@2601
|
294 |
* BoundingBox<>
|
hegyi@2601
|
295 |
* operator+=() -> add()
|
hegyi@2601
|
296 |
+ clear()
|
hegyi@2601
|
297 |
* Better documentation
|
hegyi@2601
|
298 |
* Several important bugfixes
|
kpeter@2603
|
299 |
* Now LEMON should compile without warnings with
|
hegyi@2601
|
300 |
* gcc 3.3, 3.4, 4.0
|
hegyi@2601
|
301 |
* Intel C++ Compiler v9.0
|
alpar@1668
|
302 |
|
alpar@1668
|
303 |
2005-03-19 Version 0.3.1 Released
|
hegyi@2601
|
304 |
This release fixes a compilation failure bug under cygwin.
|
alpar@1668
|
305 |
|
alpar@1668
|
306 |
2005-02-21 Version 0.3 released
|
hegyi@2601
|
307 |
New features
|
hegyi@2601
|
308 |
+ Standardized LEMON exceptions
|
hegyi@2601
|
309 |
+ Undirected Graph
|
kpeter@2603
|
310 |
+ Standard graph file format, input and output classes for it
|
hegyi@2601
|
311 |
+ GraphToEps: A simple graph drawer
|
hegyi@2601
|
312 |
Changes
|
hegyi@2601
|
313 |
* Redesigned Graph infrastructures
|
hegyi@2601
|
314 |
* head() -> target(), tail() -> source()
|
hegyi@2601
|
315 |
* Some standard namings have changes:
|
hegyi@2601
|
316 |
ValueType -> Value,
|
hegyi@2601
|
317 |
KeyType -> Key,
|
kpeter@2603
|
318 |
ReferenceType -> Reference,
|
hegyi@2601
|
319 |
PointerType -> Pointer
|
hegyi@2601
|
320 |
* Better documentation
|
hegyi@2601
|
321 |
|
alpar@1668
|
322 |
2004-09-30 Version 0.2 released
|