1.1 --- a/NEWS Tue Oct 31 08:28:55 2006 +0000
1.2 +++ b/NEWS Tue Oct 31 08:32:28 2006 +0000
1.3 @@ -1,160 +1,51 @@
1.4 -2006-10-27 Version 0.6 Released
1.5 -
1.6 -#Renamed:
1.7 - *Undir -> U
1.8 - *Minimum -> Min
1.9 - *Work -> Aux
1.10 - *UGraphExtender -> UndirectGraphExtender
1.11 - -UGraphExtenders with changed meaning
1.12 - *GridGraph -> GridUGraph
1.13 - *UNDIRGRAPH_TYPEDEFS -> UGRAPH_TYPEDEFS
1.14 - *LinearHeap -> BucketHeap
1.15 - *UGraphBaseExtender -> UndirGraphExtender
1.16 - *BpUGraphBaseExtender merged into BpUGraphExtender
1.17 - *StaticGraph to Graph
1.18 - *ColorSet to Palette
1.19 - *xy -> dim2::Point
1.20 - *DirPath to Path
1.21 - *concept -> concepts (namespace & directory)
1.22 -
1.23 -#Reorganized:
1.24 - *bootstrap: quiet option
1.25 - *utility, invalid and traits moved to bits
1.26 - *section readers moved to own group
1.27 - *separate group for matrices
1.28 - *single makefile
1.29 - *glemon is moved to own repository
1.30 - *graph_component.h -> graph_components.h
1.31 - *reference to modules added
1.32 - *disable assertions in default behaviour
1.33 - *BiVariant moved to lemon/bits/variant.h
1.34 - *using abort() instead of exit(1)
1.35 -
1.36 -#Taken out:
1.37 - *SplitGraph is temporarly deleted
1.38 - *SubBidirGraphAdaptor
1.39 - *obsolote "id" map handling
1.40 - *concepts for extendable and erasable graphs
1.41 - *exceptionName()
1.42 - *bezier.h
1.43 - *functional interfaces
1.44 - *UPath
1.45 -
1.46 -#Rewritten, modificated, improved
1.47 - *UnionFindEnum revision
1.48 - *countItems
1.49 - *findEdges
1.50 - *IncEdgeIt goes through on loop edges twice.
1.51 - *mining of the clear in heaps
1.52 - *SplitGraphAdaptor
1.53 - *item sets are written in the order sorted by the labels
1.54 - *make explicit constructors
1.55 - *snapshot
1.56 - -rewritten
1.57 - -implemented for SmartUGraph an SmartBpUGraph
1.58 - *Node/Edge::operator<() is required by the concept
1.59 - *Graph Component concepts
1.60 - *disabled the copy constructor and operator- of {List|Smart}[U]Graph.
1.61 - *modificated interface: colType() functions
1.62 - *made public what() in NodeSetError
1.63 - *improvment in exception handling
1.64 - -exception safe erase and clear handler
1.65 - -proper exception handling in the SmartEdgeSet
1.66 - -rethrow of exception missing
1.67 - *signaling alterations in BpUGraphs
1.68 - *UnionFind
1.69 - -takes less space
1.70 - -UnionFindEnum
1.71 - -changed interface
1.72 - *updated the Path concept
1.73 - *item readers and writers
1.74 -
1.75 -#New
1.76 - *functor usage for writeable map adaptors
1.77 - *MIP support
1.78 - -interface to the cplex MIP solver
1.79 - *data structures
1.80 - -ListBpUGraph
1.81 - -SmartEdgeset
1.82 - -RefPtr: a reference counted pointer class
1.83 - -two state variant
1.84 - -Polinomial template class
1.85 - -SimpleBucketHeap
1.86 - -even a smaller version
1.87 - -tolerance class
1.88 - -Tolerance<unsigned int> and Tolerance<unsigned long long int> added
1.89 - -the extender system
1.90 - -some UGraphExtender /SubUGraphExtenders, DirectUGraphExtender/
1.91 - -adaptor related
1.92 - -ResGraphAdaptor with Tolerance
1.93 - -SwapBpUGraphAdaptor which swaps the two nodeset of the bipartite graph
1.94 - -map related
1.95 - -SimpleMap and SimpleWriteMap
1.96 - -new map type based on array map for debugging purpose
1.97 - -DynamicAsymMatrixMap
1.98 - -MatrixMapTraits
1.99 - *functions
1.100 - -optimality test on random graph
1.101 - -implementation of the drand48 functions
1.102 - -negative cycle to path converter
1.103 - -reserveNode function
1.104 - -Mersenne Twister random number generator
1.105 - -EdgeLookUp and AllEdgeLookUp
1.106 - *scripts
1.107 - -script that lists all the header files included directly or indirectly by a certain header file
1.108 - -script creates/updates the copyright header of a source file
1.109 - *algorithms
1.110 - -algorithm group for matchings
1.111 - -Bipartite Graph Max Cardinality Matching (Hopcroft-Karp)
1.112 - -MaxWeightedBipartiteMatching
1.113 - -MinCostMaxBipartiteMatching
1.114 - -MaxCardinalitySearch
1.115 - -MinimalCut in UGraph
1.116 - -tabu search
1.117 - -Minimum Cost Arborescence algorithm
1.118 - -dual solution computation and interface for algorithm
1.119 - -Edmonds-Karp MaxFlow
1.120 - -Hao-Orlin algorithm
1.121 -
1.122 -#Progress in already existing objects:
1.123 - *radix sort to ansi compatible
1.124 - *map creation based on virtual base class is possible
1.125 - *default constructor which allocates empty graphs
1.126 - *defaultMap is introdouced, graph maps should not be inherited from the ObserverBase.
1.127 - *clarifing alteration observing system
1.128 - *resize for static size graph
1.129 - *an additional simplier interface for static size graphs.
1.130 - *Node operator()(int) for getting node by index
1.131 - *int index(Node node) for getting index by node
1.132 - *traits for alteration notifiers
1.133 - *graph adadptors can be alteration observed
1.134 - *count ANodes-BNodes in bipartite graphs
1.135 - *the template assign operators and map iterators can be used for adaptors also
1.136 - *writeable extension of some maps
1.137 - *rot180() added to xy.h
1.138 - *change source and target for the bipartite list graph
1.139 - *findEdge extension also for the BpUGraphs
1.140 - *proper handling of loop edges in the UGraph::findUEdge
1.141 - *exported interface to the Graph class
1.142 - *new random interface
1.143 - *graph imlementations actually provide ReferenceMaps
1.144 - *lgf2ps:
1.145 - -RGB color related stuff is in color.h now
1.146 - -simple class to create .eps figures (eps.h)
1.147 - -"Node shapes" added
1.148 - -some color constants added (BLACK, WHITE, RED etc)
1.149 - -absolute/relative node size/link width scaling
1.150 -
1.151 -#Compatibility issues:
1.152 - *compilation with G++ -ansi
1.153 - *gcc-4.1
1.154 - *NaN checking to be conform to MinGW32
1.155 - *MinGW, MinGW32
1.156 - *long long just for gnu compilers
1.157 - *CPLEX 9.x support
1.158 - *turned off 32bit specific tests.
1.159 -
1.160 -#Beyond the aboves several bugfix and documentation improvement is made, new demos, benchmarks are implemented.
1.161 +2006-10-31 Version 0.6 Released
1.162 + * New Features
1.163 + - Mixed Integer Programming (MIP) support
1.164 + - interface to GLPK and CPLEX MIP solvers
1.165 + - Data structures
1.166 + - Bipatrite graph concepts and implementations
1.167 + - a Polinomial template class
1.168 + - RefPtr: a reference counted pointer class
1.169 + - SimpleBucketHeap
1.170 + - random.h: Mersenne Twister random number generator
1.171 + - EdgeLookUp and AllEdgeLookUp
1.172 + - Tools to find edges between to nodes in time O(log d)
1.173 + - new matching algorithms
1.174 + - Bipartite Graph Max Cardinality Matching (Hopcroft-Karp)
1.175 + - MaxWeightedBipartiteMatching
1.176 + - MinCostMaxBipartiteMatching
1.177 + - MaxCardinalitySearch
1.178 + - MinimalCut in UGraph
1.179 + - Tabu Search framework
1.180 + - Minimum Cost Arborescence algorithm
1.181 + - Edmonds-Karp MaxFlow
1.182 + - Hao-Orlin algorithm
1.183 + - eps.h: A simple tool to create .eps pictures.
1.184 + * Backward incompatibilities/changed namings:
1.185 + - UndirXyz -> UXyz
1.186 + - UNDIRGRAPH_TYPEDEFS -> UGRAPH_TYPEDEFS
1.187 + - GridGraph -> GridUGraph
1.188 + - LinearHeap -> BucketHeap
1.189 + - ColorSet -> Palette
1.190 + - xy -> dim2::Point
1.191 + - DirPath -> Path
1.192 + - concept -> concepts (namespace & directory)
1.193 + - LpSolverBase
1.194 + - ColName() -> colName
1.195 + - Coeff() -> coeff()
1.196 + - MinCostFlow -> SspMinCostFlow
1.197 + * Repository reorganization:
1.198 + - glemon has moved to an separate repository
1.199 + - compilation is conducted by a single makefile
1.200 + - internal building blocks are now in a separate directory
1.201 + (lemon/bits)
1.202 + * Major improvements many algorithms and data structures.
1.203 + * Several bugfixes
1.204 + * Compatibility issues:
1.205 + - known to compile with
1.206 + - GCC 3.3, 3.4, 4.0, 4.1
1.207 + - MinGW, MinGW32
1.208 + - Intel C++ 9.x support
1.209
1.210 2006-02-03 Version 0.5 Released
1.211 * New features: