COIN-OR::LEMON - Graph Library

source: lemon-0.x/NEWS @ 2276:1a8a66b6c6ce

Last change on this file since 2276:1a8a66b6c6ce was 2266:07b533060ec5, checked in by Hegyi Péter, 17 years ago

NEWS updated to Rel0.6 - according to Alpar's instruction, at last

File size: 9.3 KB
Line 
12006-10-27  Version 0.6 Released
2
3#Renamed:
4  *Undir -> U
5  *Minimum -> Min
6  *Work -> Aux
7  *UGraphExtender -> UndirectGraphExtender
8    -UGraphExtenders with changed meaning
9  *GridGraph -> GridUGraph
10  *UNDIRGRAPH_TYPEDEFS -> UGRAPH_TYPEDEFS
11  *LinearHeap -> BucketHeap
12  *UGraphBaseExtender -> UndirGraphExtender
13  *BpUGraphBaseExtender merged into BpUGraphExtender
14  *StaticGraph to Graph
15  *ColorSet to Palette
16  *xy -> dim2::Point
17  *DirPath to Path
18  *concept -> concepts (namespace & directory)
19
20#Reorganized:
21  *bootstrap: quiet option
22  *utility, invalid and traits moved to bits
23  *section readers moved to own group
24  *separate group for matrices
25  *single makefile
26  *glemon is moved to own repository
27  *graph_component.h -> graph_components.h
28  *reference to modules added
29  *disable assertions in default behaviour
30  *BiVariant moved to lemon/bits/variant.h
31  *using abort() instead of exit(1)
32
33#Taken out:
34  *SplitGraph is temporarly deleted
35  *SubBidirGraphAdaptor
36  *obsolote "id" map handling
37  *concepts for extendable and erasable graphs
38  *exceptionName()
39  *bezier.h
40  *functional interfaces
41  *UPath
42
43#Rewritten, modificated, improved
44  *UnionFindEnum revision
45  *countItems
46  *findEdges
47  *IncEdgeIt goes through on loop edges twice.
48  *mining of the clear in heaps
49  *SplitGraphAdaptor
50  *item sets are written in the order sorted by the labels
51  *make explicit constructors
52  *snapshot
53    -rewritten
54    -implemented for SmartUGraph an SmartBpUGraph
55  *Node/Edge::operator<() is required by the concept
56  *Graph Component concepts
57  *disabled the copy constructor and operator- of {List|Smart}[U]Graph.
58  *modificated interface: colType() functions
59  *made public what() in NodeSetError
60  *improvment in exception handling
61    -exception safe erase and clear handler
62    -proper exception handling in the SmartEdgeSet
63    -rethrow of exception missing
64  *signaling alterations in BpUGraphs
65  *UnionFind
66    -takes less space
67    -UnionFindEnum
68      -changed interface
69  *updated the Path concept
70  *item readers and writers
71
72#New
73  *functor usage for writeable map adaptors
74  *MIP support
75    -interface to the cplex MIP solver
76  *data structures
77    -ListBpUGraph
78    -SmartEdgeset
79    -RefPtr: a reference counted pointer class
80    -two state variant
81    -Polinomial template class
82    -SimpleBucketHeap 
83      -even a smaller version
84    -tolerance class
85      -Tolerance<unsigned int> and Tolerance<unsigned long long int> added
86    -the extender system
87      -some UGraphExtender /SubUGraphExtenders, DirectUGraphExtender/
88    -adaptor related
89      -ResGraphAdaptor with Tolerance
90      -SwapBpUGraphAdaptor which swaps the two nodeset of the bipartite graph
91    -map related
92      -SimpleMap and SimpleWriteMap
93      -new map type based on array map for debugging purpose
94      -DynamicAsymMatrixMap
95      -MatrixMapTraits
96  *functions
97    -optimality test on random graph
98    -implementation of the drand48 functions
99    -negative cycle to path converter
100    -reserveNode function
101    -Mersenne Twister random number generator
102    -EdgeLookUp and AllEdgeLookUp
103  *scripts
104    -script that lists all the header files included directly or indirectly by a certain header file
105    -script creates/updates the copyright header of a source file
106  *algorithms
107    -algorithm group for matchings
108      -Bipartite Graph Max Cardinality Matching (Hopcroft-Karp)
109      -MaxWeightedBipartiteMatching
110      -MinCostMaxBipartiteMatching
111    -MaxCardinalitySearch
112    -MinimalCut in UGraph
113    -tabu search
114    -Minimum Cost Arborescence algorithm
115      -dual solution computation and interface for algorithm
116      -Edmonds-Karp MaxFlow
117    -Hao-Orlin algorithm
118
119#Progress in already existing objects:
120  *radix sort to ansi compatible
121  *map creation based on virtual base class is possible
122  *default constructor which allocates empty graphs
123  *defaultMap is introdouced, graph maps should not be inherited from the ObserverBase.
124  *clarifing alteration observing system
125  *resize for static size graph
126  *an additional simplier interface for static size graphs.
127  *Node operator()(int) for getting node by index
128  *int index(Node node) for getting index by node
129  *traits for alteration notifiers
130  *graph adadptors can be alteration observed
131  *count ANodes-BNodes in bipartite graphs
132  *the template assign operators and map iterators can be used for adaptors also
133  *writeable extension of some maps
134  *rot180() added to xy.h
135  *change source and target for the bipartite list graph
136  *findEdge extension also for the BpUGraphs
137  *proper handling of loop edges in the UGraph::findUEdge
138  *exported interface to the Graph class
139  *new random interface
140  *graph imlementations actually provide ReferenceMaps
141  *lgf2ps:
142    -RGB color related stuff is in color.h now
143    -simple class to create .eps figures (eps.h)
144    -"Node shapes" added
145    -some color constants added (BLACK, WHITE, RED etc)
146    -absolute/relative node size/link width scaling
147
148#Compatibility issues:
149  *compilation with G++ -ansi
150  *gcc-4.1
151  *NaN checking to be conform to MinGW32
152  *MinGW, MinGW32
153  *long long just for gnu compilers
154  *CPLEX 9.x support
155  *turned off 32bit specific tests.
156
157#Beyond the aboves several bugfix and documentation improvement is made, new demos, benchmarks are implemented.
158
1592006-02-03  Version 0.5 Released
160        * New features:
161          - Bfs/Dfs/Dijkstra
162            + query functions for the next node/edge to be processed
163            + visitor interface for dfs
164          - topology.h: small functions for discovering graph topology
165            + connected components, strongly connected components
166            + bipartiteness testing
167          - Shortest paths algorithms:
168            bellman_ford.h, floyd_warshall.h, johnson.h
169          - Euler tour iterator for directed and undirected graphs
170          - Other algorithms:
171            + dag_shortest_path.h
172            + fredman_tarjan.h and prim.h for min cost trees
173          - Bipartite graph concept and implementations
174          - Graph maps:
175            + template assign operator
176            + specialized iterable bool map
177            + potential difference map
178            + NodeMatrixMap -- Matrix over the nodes
179          - Maps:
180            + IterableIntMap
181          - GUI:
182            + NewMap window in MapSelector
183            + Algorithm window and some algorithms (eg. Kruskal) added
184          - LemonReader:
185            + exception on non-existent files
186          - LP interface:
187            + (Dual)Expr::simplify(double tolerance) added
188            + getDual()
189          - GraphToEps:
190            + negateY() opt
191            + male/female node shapes :)
192            + correct %%BoundingBox handling
193          - Tools:
194            + Timer can be stop()ed and (re)start()ed
195            + radix sort algorithm
196            + tolerance.h for working with imprecise numbers
197        * Backward incompatibilities/changed namings:
198          - Access functions of TimeStamp/Timer
199          - Undir graph interface: findUEdge, ConUEdgeIt
200          - pred -> predEdge renaming in search algorithms
201          - SnapShot -> Snapshot in {List,Smart}Graph
202          - NewEdgeSetAdaptor -> ListEdgeSet
203          - LP: set{Obj,Row,Col}() -> {obj,row,col}()
204          - "label" instead of "id" inside the LGF files
205          - UndirGraph -> UGraph, UndirEdge* -> UEdge*
206          - BipartiteGraph -> BpGraph, Lower/UpperNode* -> A/BNode*
207        * Bugfixes in
208          - DFS
209          - Preflow
210          - x86_64 connected bugfixes (lemon_reader.h)
211          - lp.h
212        * New demos, benchmarks and tools:
213          - graph_orientation.cc: A thoroughly documented demo application
214          - runningTimeTest(): a tool to measure running times more precisely
215          - Demo for topology
216          - counter.h: a tool to measure the number of steps of algorithms
217          - Some useful scripts: check-compiler, check-integrity
218        * Other changes:
219          - Demos and benchmarks are not built by default now. They can be
220            enabled with the --enable-demo and --enable-benchmark
221            configure flags.
222          - GCC 4.0.3 and ICC 9.0 compatibility
223         
2242005-08-27  Version 0.4 Released
225        * List of new features and changes     
226          * Changed namings:
227            Wrapper -> Adaptor
228            kruskalEdgeMap() -> kruskal()
229            kruskalEdgeMap_IteratorOut() -> kruskal()
230          * BoundinBox<>
231            * operator+=() -> add()
232            + clear()
233          + More and better graph I/O functionalities
234          + High level uniform LP solver interface to CPLEX and GLKP
235          * graphToEps()
236            + Automatic node size and edge width scaling
237            + Simple color palette tool (ColorSet)
238          * Bfs/Dfs/Dijkstra
239            + Step-by-step execution
240            + Run from multiple sources
241            + Used define stop condition
242            + Improved "named parameters"
243          * Preflow
244            + Function type interface
245            + Changed interface
246          * ListGraph/SmarGraph
247            + split() splits a node
248            + SnapShot
249          + New map adaptors
250          + New convenience maps
251            + IdMap, DescriptorMap
252            + InDegMap, OutDegMap
253            + XMap, YMap
254          + Default graph maps are iterable
255          + glemon: a graph editor
256          + Some new demo codes added, the old ones got polished.
257          * Better documentation
258          * Several important bugfixes
259          * Now lemon should compile without warnings with
260            * gcc 3.3, 3.4, 4.0
261            * Intel C++ Compiler v9.0
262
2632005-03-19  Version 0.3.1 Released
264        * This release fixes a compilation failure bug under cygwin.
265
2662005-02-21  Version 0.3 released
267        * List of new features and changes     
268          * Redesigned Graph infrastructures
269          + Standardized LEMON exceptions
270          + Undirected Graph
271          + Standard graph file format, input and output classes for it.
272          * head() -> target(), tail() -> source()
273          * Some standard namings have changes:
274            ValueType -> Value,
275            KeyType -> Key,
276            ReferenceType ->Reference,
277            PointerType -> Pointer
278          + GraphToEps: A simple graph drawer
279          * Better documentation
280       
2812004-09-30  Version 0.2 released
282
Note: See TracBrowser for help on using the repository browser.