COIN-OR::LEMON - Graph Library

source: lemon-0.x/NEWS @ 2600:e5530c0a018c

Last change on this file since 2600:e5530c0a018c was 2600:e5530c0a018c, checked in by Hegyi Péter, 11 years ago

NEWS file updated for Release 0.7

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