diff -r e5530c0a018c -r 054de623255b NEWS --- a/NEWS Mon Apr 07 16:28:20 2008 +0000 +++ b/NEWS Tue Apr 08 11:38:17 2008 +0000 @@ -1,323 +1,324 @@ 2008-02-08 Version 0.7 released - - * added - - new data structures - classes - StaticGraphBase + New Features + + new data structures + * classes + StaticGraph 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 + * helper class for checking existence of a nested class + * general mapping based variant type + * IntegerMap + + 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) + * min cost flow algorithms: + * successive shortest path algorithm + * capacity scaling algorithm + * simple cycle canceling algorithm + * minimum mean cycle canceling algorithm + * cost scaling algorithm + * network simplex algorithm + + 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 + * 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 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 + + planarity related additions + * checking and embedding + * planar grid embedding + * planar graph coloring + + bipartite matchings + * common interface + * Query functions: aMatching and bMatching + * ANodeMap matching map + * BNodeMap barrier map + Repository reorganization + * 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 + Changes + * redesigned + * undirected edgesets (like the smart graph or ugraph) + * interface of MaxMatching and UnionFindEnum + * interface of maximum flow algorithms + * Kruskal algorithm + * augmenting path based bipartite matching + Improvements + * graph copy + * preliminary support for static graphs + * added BpUGraphCopy + * Bfs/Dfs/Dijkstra + * conditional execution until the target is reached + * modified start() function in Dfs and Dijkstra classes to give back reached edge/node + * return the temporary distance of the current node + * using operation traits + * patch for retrieving reached/processed node + * prescaling can be turned off in GraphToEps + * better handling of inexact computations + * easier inverse + * faster geometric minimum spanning tree algorithm + * 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 for item reading and writing + * clear() function for union-find structures + * 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 + * more simple interface for PathDumper + Updated + * tutorial for + * algorithms + * graph visualization + * documentation + Backward incompatibilities/changed namings + * min_cut.h => nagamochi_ibaraki.h + * clone => build + * RevIt => RevEdgeIt + * _FixId => LpId + * setObj => obj + * is_min => isMin + * is_max => isMax + * 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 + - '-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) - * New Features - - Mixed Integer Programming (MIP) support - - interface to GLPK and CPLEX MIP solvers - - Data structures - - Bipatrite graph concepts and implementations - - a Polinomial template class - - RefPtr: a reference counted pointer class - - SimpleBucketHeap - - random.h: Mersenne Twister random number generator - - EdgeLookUp and AllEdgeLookUp - - Tools to find edges between to nodes in time O(log d) - - new matching algorithms - - Bipartite Graph Max Cardinality Matching (Hopcroft-Karp) - - MaxWeightedBipartiteMatching - - MinCostMaxBipartiteMatching - - MaxCardinalitySearch - - MinimalCut in UGraph - - Tabu Search framework - - Minimum Cost Arborescence algorithm - - Edmonds-Karp MaxFlow - - Hao-Orlin algorithm - - eps.h: A simple tool to create .eps pictures. - * Backward incompatibilities/changed namings: - - UndirXyz -> UXyz - - UNDIRGRAPH_TYPEDEFS -> UGRAPH_TYPEDEFS - - GridGraph -> GridUGraph - - LinearHeap -> BucketHeap - - ColorSet -> Palette - - xy -> dim2::Point - - DirPath -> Path - - concept -> concepts (namespace & directory) - - LpSolverBase - - ColName() -> colName - - Coeff() -> coeff() - - MinCostFlow -> SspMinCostFlow - * Repository reorganization: - - compilation is conducted by a single makefile - - internal building blocks are now in a separate directory - (lemon/bits) - * Major improvements many algorithms and data structures. - * Several bugfixes - * Compatibility issues: - - known to compile with - - GCC 3.3, 3.4, 4.0, 4.1 - - MinGW, MinGW32 - - Intel C++ 9.x support + GLEMON has moved to a separate repository + (https://hugo.cs.elte.hu/svn/glemon/trunk) + New Features + + Mixed Integer Programming (MIP) support + + interface to GLPK and CPLEX MIP solvers + + Data structures + * Bipatrite graph concepts and implementations + * a Polinomial template class + * RefPtr: a reference counted pointer class + * SimpleBucketHeap + + random.h: Mersenne Twister random number generator + + EdgeLookUp and AllEdgeLookUp + + Tools to find edges between to nodes in time O(log d) + + new matching algorithms + + Bipartite Graph Max Cardinality Matching (Hopcroft-Karp) + + MaxWeightedBipartiteMatching + + MinCostMaxBipartiteMatching + + MaxCardinalitySearch + + MinimalCut in UGraph + + Tabu Search framework + + Minimum Cost Arborescence algorithm + + Edmonds-Karp MaxFlow + + Hao-Orlin algorithm + + eps.h: A simple tool to create .eps pictures. + Backward incompatibilities/changed namings: + * UndirXyz -> UXyz + * UNDIRGRAPH_TYPEDEFS -> UGRAPH_TYPEDEFS + * GridGraph -> GridUGraph + * LinearHeap -> BucketHeap + * ColorSet -> Palette + * xy -> dim2::Point + * DirPath -> Path + * concept -> concepts (namespace & directory) + * LpSolverBase + * ColName() -> colName + * Coeff() -> coeff() + * MinCostFlow -> SspMinCostFlow + Repository reorganization: + * compilation is conducted by a single makefile + * internal building blocks are now in a separate directory + (lemon/bits) + Major improvements of many algorithms and data structures + Several bugfixes + Compatibility issues: + * known to compile with + * GCC 3.3, 3.4, 4.0, 4.1 + * MinGW, MinGW32 + * Intel C++ 9.x support 2006-02-03 Version 0.5 Released - * New features: - - Bfs/Dfs/Dijkstra - + query functions for the next node/edge to be processed - + visitor interface for dfs - - topology.h: small functions for discovering graph topology - + connected components, strongly connected components - + bipartiteness testing - - Shortest paths algorithms: - bellman_ford.h, floyd_warshall.h, johnson.h - - Euler tour iterator for directed and undirected graphs - - Other algorithms: - + dag_shortest_path.h - + fredman_tarjan.h and prim.h for min cost trees - - Bipartite graph concept and implementations - - Graph maps: - + template assign operator - + specialized iterable bool map - + potential difference map - + NodeMatrixMap -- Matrix over the nodes - - Maps: - + IterableIntMap - - GUI: - + NewMap window in MapSelector - + Algorithm window and some algorithms (eg. Kruskal) added - - LemonReader: - + exception on non-existent files - - LP interface: - + (Dual)Expr::simplify(double tolerance) added - + getDual() - - GraphToEps: - + negateY() opt - + male/female node shapes :) - + correct %%BoundingBox handling - - Tools: - + Timer can be stop()ed and (re)start()ed - + radix sort algorithm - + tolerance.h for working with imprecise numbers - * Backward incompatibilities/changed namings: - - Access functions of TimeStamp/Timer - - Undir graph interface: findUEdge, ConUEdgeIt - - pred -> predEdge renaming in search algorithms - - SnapShot -> Snapshot in {List,Smart}Graph - - NewEdgeSetAdaptor -> ListEdgeSet - - LP: set{Obj,Row,Col}() -> {obj,row,col}() - - "label" instead of "id" inside the LGF files - - UndirGraph -> UGraph, UndirEdge* -> UEdge* - - BipartiteGraph -> BpGraph, Lower/UpperNode* -> A/BNode* - * Bugfixes in - - DFS - - Preflow - - x86_64 connected bugfixes (lemon_reader.h) - - lp.h - * New demos, benchmarks and tools: - - graph_orientation.cc: A thoroughly documented demo application - - runningTimeTest(): a tool to measure running times more precisely - - Demo for topology - - counter.h: a tool to measure the number of steps of algorithms - - Some useful scripts: check-compiler, check-integrity - * Other changes: - - Demos and benchmarks are not built by default now. They can be - enabled with the --enable-demo and --enable-benchmark - configure flags. - - GCC 4.0.3 and ICC 9.0 compatibility - + New features + + Shortest paths algorithms + * bellman_ford.h + * floyd_warshall.h + * johnson.h + + Euler tour iterator for directed and undirected graphs + + Other algorithms: + * dag_shortest_path.h + * fredman_tarjan.h and prim.h for min cost trees + + Bipartite graph concept and implementations + + Graph maps: + * template assign operator + * specialized iterable bool map + * potential difference map + * NodeMatrixMap -- Matrix over the nodes + + Maps: + * IterableIntMap + + Tools: + * Timer can be stop()ed and (re)start()ed + * radix sort algorithm + * tolerance.h for working with imprecise numbers + New demos, benchmarks and tools + + graph_orientation.cc: A thoroughly documented demo application + + runningTimeTest(): a tool to measure running times more precisely + + Demo for topology + + counter.h: a tool to measure the number of steps of algorithms + + Some useful scripts: check-compiler, check-integrity + Improvements + + Bfs/Dfs/Dijkstra + * query functions for the next node/edge to be processed + * visitor interface for dfs + + topology.h: small functions for discovering graph topology + * connected components, strongly connected components + * bipartiteness testing + + GUI: + * NewMap window in MapSelector + * Algorithm window and some algorithms (eg. Kruskal) added + + LemonReader: + * exception on non-existent files + + LP interface: + * (Dual)Expr::simplify(double tolerance) added + * getDual() + + GraphToEps: + * negateY() opt + * male/female node shapes :) + * correct %%BoundingBox handling + Backward incompatibilities/changed namings: + * Access functions of TimeStamp/Timer + * Undir graph interface: findUEdge, ConUEdgeIt + * pred -> predEdge renaming in search algorithms + * SnapShot -> Snapshot in {List,Smart}Graph + * NewEdgeSetAdaptor -> ListEdgeSet + * LP: set{Obj,Row,Col}() -> {obj,row,col}() + * "label" instead of "id" inside the LGF files + * UndirGraph -> UGraph, UndirEdge* -> UEdge* + * BipartiteGraph -> BpGraph, Lower/UpperNode* -> A/BNode* + Bugfixes in + * DFS + * Preflow + * x86_64 connected bugfixes (lemon_reader.h) + * lp.h + Other changes + * Demos and benchmarks are not built by default now. They can be + * enabled with the --enable-demo and --enable-benchmark + * configure flags. + * GCC 4.0.3 and ICC 9.0 compatibility + 2005-08-27 Version 0.4 Released - * List of new features and changes - * Changed namings: - Wrapper -> Adaptor - kruskalEdgeMap() -> kruskal() - kruskalEdgeMap_IteratorOut() -> kruskal() - * BoundinBox<> - * operator+=() -> add() - + clear() - + More and better graph I/O functionalities - + High level uniform LP solver interface to CPLEX and GLKP - * graphToEps() - + Automatic node size and edge width scaling - + Simple color palette tool (ColorSet) - * Bfs/Dfs/Dijkstra - + Step-by-step execution - + Run from multiple sources - + Used define stop condition - + Improved "named parameters" - * Preflow - + Function type interface - + Changed interface - * ListGraph/SmarGraph - + split() splits a node - + SnapShot - + New map adaptors - + New convenience maps - + IdMap, DescriptorMap - + InDegMap, OutDegMap - + XMap, YMap - + Default graph maps are iterable - + glemon: a graph editor - + Some new demo codes added, the old ones got polished. - * Better documentation - * Several important bugfixes - * Now lemon should compile without warnings with - * gcc 3.3, 3.4, 4.0 - * Intel C++ Compiler v9.0 + New features + + More and better graph I/O functionalities + + High level uniform LP solver interface to CPLEX and GLKP + + New map adaptors + + New convenience maps + * IdMap, DescriptorMap + * InDegMap, OutDegMap + * XMap, YMap + + Default graph maps are iterable + + glemon: a graph editor + + Some new demo codes added, the old ones got polished. + Improvements + + graphToEps() + * Automatic node size and edge width scaling + * Simple color palette tool (ColorSet) + + Bfs/Dfs/Dijkstra + * Step-by-step execution + * Run from multiple sources + * Used define stop condition + * Improved "named parameters" + + Preflow + * Function type interface + * Changed interface + + ListGraph/SmarGraph + * split() splits a node + * SnapShot + Changes + * Changed namings: + * Wrapper -> Adaptor + * kruskalEdgeMap() -> kruskal() + * kruskalEdgeMap_IteratorOut() -> kruskal() + * BoundingBox<> + * operator+=() -> add() + + clear() + * Better documentation + * Several important bugfixes + * Now lemon should compile without warnings with + * gcc 3.3, 3.4, 4.0 + * Intel C++ Compiler v9.0 2005-03-19 Version 0.3.1 Released - * This release fixes a compilation failure bug under cygwin. + This release fixes a compilation failure bug under cygwin. 2005-02-21 Version 0.3 released - * List of new features and changes - * Redesigned Graph infrastructures - + Standardized LEMON exceptions - + Undirected Graph - + Standard graph file format, input and output classes for it. - * head() -> target(), tail() -> source() - * Some standard namings have changes: - ValueType -> Value, - KeyType -> Key, - ReferenceType ->Reference, - PointerType -> Pointer - + GraphToEps: A simple graph drawer - * Better documentation - + + New features + + Standardized LEMON exceptions + + Undirected Graph + + Standard graph file format, input and output classes for it. + + GraphToEps: A simple graph drawer + Changes + * Redesigned Graph infrastructures + * head() -> target(), tail() -> source() + * Some standard namings have changes: + ValueType -> Value, + KeyType -> Key, + ReferenceType ->Reference, + PointerType -> Pointer + * Better documentation + 2004-09-30 Version 0.2 released -