diff -r b9905565d185 -r e5530c0a018c NEWS --- a/NEWS Thu Apr 03 12:06:48 2008 +0000 +++ b/NEWS Mon Apr 07 16:28:20 2008 +0000 @@ -1,3 +1,152 @@ +2008-02-08 Version 0.7 released + + * added + - new data structures + classes + StaticGraphBase + ExtendFindEnum + BfsVisitor class + Bipartite partitions based on visitors + helper class for checking existence of a nested class + general mapping based variant type + IntegerMap + - new functions and tools + ArgParser, a command line argument parser + DistLog, a tool for measuring one and two dimensional distributions + undirected minimum cut benchmarking + tools/lgf-gen.cc, a random graph generator + BpUGraphReader and Writer + DynEdgeLookUp implementation based on splay trees + MACROS for debug map usage + - new algoritmhs + Lagrange relaxation based algorithm for the delay constrained least cost path problem + a preflow based general network circulation algorithm + 2-approximation of Steiner-tree problem + two heuristics (http://www.avglab.com/andrew/pub/neci-tr-96-132.ps) + tsp2, a minimum spanning tree based TSP algorithm + Delaunay triangulation + Gomory-Hu tree algorithm + Edmond's Blossom shrinking algorithm + minimum mean cycle algorithm + Goldberg-Tarjan algorithm (Preflow with Dynamic Trees) + Dinitz-Sleator-Tarjan (Blocking flow with Dynamic Tree) + - new distributions (Gaussian, exponential, Gamma, two dimensional random, buffered bit generation) + - push-relabel type algorithm related additions + Elevator, a class for handling item labels in push-relabel type algorithms + a push/relabel type max cardinality matching implementation + some query function for push-relabel based matching + - LP related additions + Soplex support + ColIt class + new functions (simplify(), isFinite(), row and col getter function) + _setColCoeff and _setRowCoeff parameters + section reader and writer for lemon IO + equality-type constraint can now be added to a LP + virtual functions of class LpCplex + some query functions for GLPK + - demos + preflow based general network circulation demo + Steiner 2-approximation demo + demo for SAT problems + sample input for sat-2 and sat demos + - tests for + graph copies + random.h + max weighted matchings + - rename graphs script + - planarity related additions + checking and embedding + planar grid embedding + planar graph coloring + - administrative improvements + script for automatic checking of SVN commit's consistency + automatic doc generation from the SVN trunk + check for gcc version 3.3, 3.4, 4.0 and 4.1.2 as well + reorganization of the modules and groups + a tools directory added for useful executables codes + doxygen + renaming topology doxygen group to graph_prop doxygen group + introducing planar doxygen group + - bipartite matchings + common interface + Query functions: aMatching and bMatching + ANodeMap matching map + BNodeMap barrier map + + * changed, modified, improved + - redesigned + undirected edgesets (like the smart or ugraph) + interface of MaxMatching and UnionFindEnum + interface of maximum flow algorithms + Kruskal algorithm + augmenting path based bipartite matching + - min cost flows + various min cost flow solvers + redesigned CapacityScaling algorithm + - graph copy + preliminary support for static graphs + added BpUGraphCopy + - execution + conditional execution until the target is reached + modified start() function in Dfs and Dijkstra classes to give back reached edge/node + - Dijkstra + return the temporary distance of the current node + using operation traits + - patch for retrieving reached/processed node in dijkstra, bfs and dfs + - prescaling can be turned off in GraphToEps + - better handling of inexact computation + - easier inverse + - faster geometric minimum spanning tree + - new implementation of undirected graphs + - Hao-Orlin algorithm became epsilon-safe + - LpSoplex + added getter functions + better m4 file + better handling of unsolved lps + - allowing 'string' type quoting + - clear() function for unionfinds + - integer parameters also converted to double + - hacking mip is possible without integer variables + - space reservation for SmartGraph + - path + PathNodeIt + PathWriter/Reader structures + Distinct MapSet readers and writers + more simple interface for PathDumper + + * updated + - tutorial for + algorithms + graph visualization + - documentation + + * rename + - min_cut.h => nagamochi_ibaraki.h + - clone => build + - RevIt => RevEdgeIt + - _FixId => LpId + - setObj => obj + - is_min => isMin + - is_max => isMax + - 'hugo' => 'lemon' + - ball2() => disc() + - state_enum => State + - getNotifier => notifier + - using LEMON_ASSERT instead of LogicError() + - uedgeset is an alias for edgeset + - CPXMIP_OPTIMAL_TOL status is considered as OPTIMAL too + - removed "Type" suffix from typedefs + - lower case local variables + + * removed + - template Map template parameter from InvertableMaps + - unionfind Item template parameter + - strict checking + - some automatic callback generation + '-Wshadow' seemed too strict therefore removed + + * several bugfixes + 2006-10-31 Version 0.6 Released * GLEMON has moved to a separate repository (https://hugo.cs.elte.hu/svn/glemon/trunk)