COIN-OR::LEMON - Graph Library

source: lemon-0.x/NEWS @ 2602:1c7790d9e025

Last change on this file since 2602:1c7790d9e025 was 2602:1c7790d9e025, checked in by Hegyi Péter, 16 years ago

Rel.07 NEWS - 3. round

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