Changeset 2601:054de623255b in lemon0.x
 Timestamp:
 04/08/08 13:38:17 (16 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@3484
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

NEWS
r2600 r2601 1 1 20080208 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 * 2approximation of Steinertree problem 16 * two heuristics (http://www.avglab.com/andrew/pub/necitr96132.ps) 17 * tsp2, a minimum spanning tree based TSP algorithm 18 * Delaunay triangulation 19 * GomoryHu tree algorithm 20 * Edmond's Blossom shrinking algorithm 21 * minimum mean cycle algorithm 22 * GoldbergTarjan algorithm (Preflow with Dynamic Trees) 23 * DinitzSleatorTarjan (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/lgfgen.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 2approximation of Steinertree problem 25 two heuristics (http://www.avglab.com/andrew/pub/necitr96132.ps) 26 tsp2, a minimum spanning tree based TSP algorithm 27 Delaunay triangulation 28 GomoryHu tree algorithm 29 Edmond's Blossom shrinking algorithm 30 minimum mean cycle algorithm 31 GoldbergTarjan algorithm (Preflow with Dynamic Trees) 32 DinitzSleatorTarjan (Blocking flow with Dynamic Tree) 33  new distributions (Gaussian, exponential, Gamma, two dimensional random, buffered bit generation) 34  pushrelabel type algorithm related additions 35 Elevator, a class for handling item labels in pushrelabel type algorithms 36 a push/relabel type max cardinality matching implementation 37 some query function for pushrelabel 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 equalitytype 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 2approximation demo 50 demo for SAT problems 51 sample input for sat2 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  HaoOrlin algorithm became epsilonsafe 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/lgfgen.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 + pushrelabel type algorithm related additions 41 * Elevator, a class for handling item labels in pushrelabel type algorithms 42 * a push/relabel type max cardinality matching implementation 43 * some query function for pushrelabel 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 * equalitytype 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 2approximation demo 56 * demo for SAT problems 57 * sample input for sat2 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 * HaoOrlin algorithm became epsilonsafe 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 unionfind 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 20061031 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 (HopcroftKarp)166 MaxWeightedBipartiteMatching167 MinCostMaxBipartiteMatching168 MaxCardinalitySearch169 MinimalCut in UGraph170 Tabu Search framework171 Minimum Cost Arborescence algorithm172 EdmondsKarp MaxFlow173 HaoOrlin 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 (HopcroftKarp) 161 + MaxWeightedBipartiteMatching 162 + MinCostMaxBipartiteMatching 163 + MaxCardinalitySearch 164 + MinimalCut in UGraph 165 + Tabu Search framework 166 + Minimum Cost Arborescence algorithm 167 + EdmondsKarp MaxFlow 168 + HaoOrlin 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 20060203 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 nonexistent 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: checkcompiler, checkintegrity 259 * Other changes: 260  Demos and benchmarks are not built by default now. They can be 261 enabled with the enabledemo and enablebenchmark 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: checkcompiler, checkintegrity 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 nonexistent 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 enabledemo and enablebenchmark 260 * configure flags. 261 * GCC 4.0.3 and ICC 9.0 compatibility 262 265 263 20050827 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 + Stepbystep 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 * Stepbystep 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 20050319 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 20050221 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 20040930 Version 0.2 released 323
Note: See TracChangeset
for help on using the changeset viewer.