1.1 --- a/NEWS Fri Oct 27 12:39:13 2006 +0000
1.2 +++ b/NEWS Fri Oct 27 15:08:58 2006 +0000
1.3 @@ -1,3 +1,161 @@
1.4 +2006-10-27 Version 0.6 Released
1.5 +
1.6 +#New
1.7 + *functor usage for writeable map adaptors
1.8 + *MIP support
1.9 + -interface to the cplex MIP solver
1.10 + *data structures
1.11 + -ListBpUGraph
1.12 + -SmartEdgeset
1.13 + -RefPtr: a reference counted pointer class
1.14 + -two state variant
1.15 + -Polinomial template class
1.16 + -SimpleBucketHeap
1.17 + -even a smaller version
1.18 + -tolerance class
1.19 + -Tolerance<unsigned int> and Tolerance<unsigned long long int> added
1.20 + -the extender system
1.21 + -some UGraphExtender /SubUGraphExtenders, DirectUGraphExtender/
1.22 + -adaptor related
1.23 + -ResGraphAdaptor with Tolerance
1.24 + -SwapBpUGraphAdaptor which swaps the two nodeset of the bipartite graph
1.25 + -map related
1.26 + -SimpleMap and SimpleWriteMap
1.27 + -new map type based on array map for debugging purpose
1.28 + -DynamicAsymMatrixMap
1.29 + -MatrixMapTraits
1.30 + *functions
1.31 + -optimality test on random graph
1.32 + -implementation of the drand48 functions
1.33 + -negative cycle to path converter
1.34 + -reserveNode function
1.35 + -Mersenne Twister random number generator
1.36 + -EdgeLookUp and AllEdgeLookUp
1.37 + *scripts
1.38 + -script that lists all the header files included directly or indirectly by a certain header file
1.39 + -script creates/updates the copyright header of a source file
1.40 + *algorithms
1.41 + -algorithm group for matchings
1.42 + -Bipartite Graph Max Cardinality Matching (Hopcroft-Karp)
1.43 + -MaxWeightedBipartiteMatching
1.44 + -MinCostMaxBipartiteMatching
1.45 + -MaxCardinalitySearch
1.46 + -MinimalCut in UGraph
1.47 + -tabu search
1.48 + -Minimum Cost Arborescence algorithm
1.49 + -dual solution computation and interface for algorithm
1.50 + -Edmonds-Karp MaxFlow
1.51 + -Hao-Orlin algorithm
1.52 +
1.53 +#Progress in already existing objects:
1.54 + *radix sort to ansi compatible
1.55 + *map creation based on virtual base class is possible
1.56 + *default constructor which allocates empty graphs
1.57 + *defaultMap is introdouced, graph maps should not be inherited from the ObserverBase.
1.58 + *clarifing alteration observing system
1.59 + *resize for static size graph
1.60 + *an additional simplier interface for static size graphs.
1.61 + *Node operator()(int) for getting node by index
1.62 + *int index(Node node) for getting index by node
1.63 + *traits for alteration notifiers
1.64 + *graph adadptors can be alteration observed
1.65 + *count ANodes-BNodes in bipartite graphs
1.66 + *the template assign operators and map iterators can be used for adaptors also
1.67 + *writeable extension of some maps
1.68 + *rot180() added to xy.h
1.69 + *change source and target for the bipartite list graph
1.70 + *findEdge extension also for the BpUGraphs
1.71 + *proper handling of loop edges in the UGraph::findUEdge
1.72 + *exported interface to the Graph class
1.73 + *new random interface
1.74 + *graph imlementations actually provide ReferenceMaps
1.75 + *lgf2ps:
1.76 + -RGB color related stuff is in color.h now
1.77 + -simple class to create .eps figures (eps.h)
1.78 + -"Node shapes" added
1.79 + -some color constants added (BLACK, WHITE, RED etc)
1.80 + -absolute/relative node size/link width scaling
1.81 +
1.82 +#Taken out:
1.83 + *SplitGraph is temporarly deleted
1.84 + *SubBidirGraphAdaptor
1.85 + *obsolote "id" map handling
1.86 + *concepts for extendable and erasable graphs
1.87 + *exceptionName()
1.88 + *bezier.h
1.89 + *functional interfaces
1.90 + *UPath
1.91 +
1.92 +#Rewritten, modificated, improved
1.93 + *UnionFindEnum revision
1.94 + *countItems
1.95 + *findEdges
1.96 + *IncEdgeIt goes through on loop edges twice.
1.97 + *mining of the clear in heaps
1.98 + *SplitGraphAdaptor
1.99 + *item sets are written in the order sorted by the labels
1.100 + *make explicit constructors
1.101 + *snapshot
1.102 + -rewritten
1.103 + -implemented for SmartUGraph an SmartBpUGraph
1.104 + *Node/Edge::operator<() is required by the concept
1.105 + *Graph Component concepts
1.106 + *disabled the copy constructor and operator- of {List|Smart}[U]Graph.
1.107 + *modificated interface: colType() functions
1.108 + *made public what() in NodeSetError
1.109 + *improvment in exception handling
1.110 + -exception safe erase and clear handler
1.111 + -proper exception handling in the SmartEdgeSet
1.112 + -rethrow of exception missing
1.113 + *signaling alterations in BpUGraphs
1.114 + *UnionFind
1.115 + -takes less space
1.116 + -UnionFindEnum
1.117 + -changed interface
1.118 + *updated the Path concept
1.119 + *item readers and writers
1.120 +
1.121 +#Reorganized:
1.122 + *bootstrap: quiet option
1.123 + *utility, invalid and traits moved to bits
1.124 + *section readers moved to own group
1.125 + *separate group for matrices
1.126 + *single makefile
1.127 + *glemon is moved to own repository
1.128 + *graph_component.h -> graph_components.h
1.129 + *reference to modules added
1.130 + *disable assertions in default behaviour
1.131 + *BiVariant moved to lemon/bits/variant.h
1.132 + *using abort() instead of exit(1)
1.133 +
1.134 +#Renamed:
1.135 + *Undir -> U
1.136 + *Minimum -> Min
1.137 + *Work -> Aux
1.138 + *UGraphExtender -> UndirectGraphExtender
1.139 + -UGraphExtenders with changed meaning
1.140 + *GridGraph -> GridUGraph
1.141 + *UNDIRGRAPH_TYPEDEFS -> UGRAPH_TYPEDEFS
1.142 + *LinearHeap -> BucketHeap
1.143 + *UGraphBaseExtender -> UndirGraphExtender
1.144 + *BpUGraphBaseExtender merged into BpUGraphExtender
1.145 + *StaticGraph to Graph
1.146 + *ColorSet to Palette
1.147 + *xy -> dim2::Point
1.148 + *DirPath to Path
1.149 + *concept -> concepts (namespace & directory)
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 +
1.162 2006-02-03 Version 0.5 Released
1.163 * New features:
1.164 - Bfs/Dfs/Dijkstra