COIN-OR::LEMON - Graph Library

source: lemon-0.x/NEWS @ 2278:a61b7f4534c7

Last change on this file since 2278:a61b7f4534c7 was 2278:a61b7f4534c7, checked in by Alpar Juttner, 17 years ago

update for version 0.6

File size: 6.0 KB
Line 
12006-10-31  Version 0.6 Released
2            * New Features
3              - Mixed Integer Programming (MIP) support
4                - interface to GLPK and CPLEX MIP solvers
5              - Data structures
6                - Bipatrite graph concepts and implementations
7                - a Polinomial template class
8                - RefPtr: a reference counted pointer class
9                - SimpleBucketHeap 
10              - random.h: Mersenne Twister random number generator
11              - EdgeLookUp and AllEdgeLookUp
12                - Tools to find edges between to nodes in time O(log d)
13              - new matching algorithms
14                - Bipartite Graph Max Cardinality Matching (Hopcroft-Karp)
15                - MaxWeightedBipartiteMatching
16                - MinCostMaxBipartiteMatching
17                - MaxCardinalitySearch
18                - MinimalCut in UGraph
19              - Tabu Search framework
20              - Minimum Cost Arborescence algorithm
21              - Edmonds-Karp MaxFlow
22              - Hao-Orlin algorithm
23              - eps.h: A simple tool to create .eps pictures.
24            * Backward incompatibilities/changed namings:
25              - UndirXyz -> UXyz
26              - UNDIRGRAPH_TYPEDEFS -> UGRAPH_TYPEDEFS
27              - GridGraph -> GridUGraph
28              - LinearHeap -> BucketHeap
29              - ColorSet -> Palette
30              - xy -> dim2::Point
31              - DirPath -> Path
32              - concept -> concepts (namespace & directory)
33              - LpSolverBase
34                - ColName() -> colName
35                - Coeff() -> coeff()
36              - MinCostFlow -> SspMinCostFlow
37            * Repository reorganization:
38              - glemon has moved to an separate repository
39              - compilation is conducted by a single makefile
40              - internal building blocks are now in a separate directory
41                (lemon/bits)
42            * Major improvements many algorithms and data structures.
43            * Several bugfixes
44            * Compatibility issues:
45              - known to compile with
46                - GCC 3.3, 3.4, 4.0, 4.1
47                - MinGW, MinGW32
48                - Intel C++ 9.x support
49
502006-02-03  Version 0.5 Released
51        * New features:
52          - Bfs/Dfs/Dijkstra
53            + query functions for the next node/edge to be processed
54            + visitor interface for dfs
55          - topology.h: small functions for discovering graph topology
56            + connected components, strongly connected components
57            + bipartiteness testing
58          - Shortest paths algorithms:
59            bellman_ford.h, floyd_warshall.h, johnson.h
60          - Euler tour iterator for directed and undirected graphs
61          - Other algorithms:
62            + dag_shortest_path.h
63            + fredman_tarjan.h and prim.h for min cost trees
64          - Bipartite graph concept and implementations
65          - Graph maps:
66            + template assign operator
67            + specialized iterable bool map
68            + potential difference map
69            + NodeMatrixMap -- Matrix over the nodes
70          - Maps:
71            + IterableIntMap
72          - GUI:
73            + NewMap window in MapSelector
74            + Algorithm window and some algorithms (eg. Kruskal) added
75          - LemonReader:
76            + exception on non-existent files
77          - LP interface:
78            + (Dual)Expr::simplify(double tolerance) added
79            + getDual()
80          - GraphToEps:
81            + negateY() opt
82            + male/female node shapes :)
83            + correct %%BoundingBox handling
84          - Tools:
85            + Timer can be stop()ed and (re)start()ed
86            + radix sort algorithm
87            + tolerance.h for working with imprecise numbers
88        * Backward incompatibilities/changed namings:
89          - Access functions of TimeStamp/Timer
90          - Undir graph interface: findUEdge, ConUEdgeIt
91          - pred -> predEdge renaming in search algorithms
92          - SnapShot -> Snapshot in {List,Smart}Graph
93          - NewEdgeSetAdaptor -> ListEdgeSet
94          - LP: set{Obj,Row,Col}() -> {obj,row,col}()
95          - "label" instead of "id" inside the LGF files
96          - UndirGraph -> UGraph, UndirEdge* -> UEdge*
97          - BipartiteGraph -> BpGraph, Lower/UpperNode* -> A/BNode*
98        * Bugfixes in
99          - DFS
100          - Preflow
101          - x86_64 connected bugfixes (lemon_reader.h)
102          - lp.h
103        * New demos, benchmarks and tools:
104          - graph_orientation.cc: A thoroughly documented demo application
105          - runningTimeTest(): a tool to measure running times more precisely
106          - Demo for topology
107          - counter.h: a tool to measure the number of steps of algorithms
108          - Some useful scripts: check-compiler, check-integrity
109        * Other changes:
110          - Demos and benchmarks are not built by default now. They can be
111            enabled with the --enable-demo and --enable-benchmark
112            configure flags.
113          - GCC 4.0.3 and ICC 9.0 compatibility
114         
1152005-08-27  Version 0.4 Released
116        * List of new features and changes     
117          * Changed namings:
118            Wrapper -> Adaptor
119            kruskalEdgeMap() -> kruskal()
120            kruskalEdgeMap_IteratorOut() -> kruskal()
121          * BoundinBox<>
122            * operator+=() -> add()
123            + clear()
124          + More and better graph I/O functionalities
125          + High level uniform LP solver interface to CPLEX and GLKP
126          * graphToEps()
127            + Automatic node size and edge width scaling
128            + Simple color palette tool (ColorSet)
129          * Bfs/Dfs/Dijkstra
130            + Step-by-step execution
131            + Run from multiple sources
132            + Used define stop condition
133            + Improved "named parameters"
134          * Preflow
135            + Function type interface
136            + Changed interface
137          * ListGraph/SmarGraph
138            + split() splits a node
139            + SnapShot
140          + New map adaptors
141          + New convenience maps
142            + IdMap, DescriptorMap
143            + InDegMap, OutDegMap
144            + XMap, YMap
145          + Default graph maps are iterable
146          + glemon: a graph editor
147          + Some new demo codes added, the old ones got polished.
148          * Better documentation
149          * Several important bugfixes
150          * Now lemon should compile without warnings with
151            * gcc 3.3, 3.4, 4.0
152            * Intel C++ Compiler v9.0
153
1542005-03-19  Version 0.3.1 Released
155        * This release fixes a compilation failure bug under cygwin.
156
1572005-02-21  Version 0.3 released
158        * List of new features and changes     
159          * Redesigned Graph infrastructures
160          + Standardized LEMON exceptions
161          + Undirected Graph
162          + Standard graph file format, input and output classes for it.
163          * head() -> target(), tail() -> source()
164          * Some standard namings have changes:
165            ValueType -> Value,
166            KeyType -> Key,
167            ReferenceType ->Reference,
168            PointerType -> Pointer
169          + GraphToEps: A simple graph drawer
170          * Better documentation
171       
1722004-09-30  Version 0.2 released
173
Note: See TracBrowser for help on using the repository browser.