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