COIN-OR::LEMON - Graph Library

source: lemon-0.x/NEWS @ 2603:5f36105d656b

Last change on this file since 2603:5f36105d656b was 2603:5f36105d656b, checked in by Peter Kovacs, 16 years ago

Small fixes in NEWS file

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