hegyi@2600: 2008-02-08 Version 0.7 released hegyi@2600: hegyi@2600: * added hegyi@2600: - new data structures hegyi@2600: classes hegyi@2600: StaticGraphBase hegyi@2600: ExtendFindEnum hegyi@2600: BfsVisitor class hegyi@2600: Bipartite partitions based on visitors hegyi@2600: helper class for checking existence of a nested class hegyi@2600: general mapping based variant type hegyi@2600: IntegerMap hegyi@2600: - new functions and tools hegyi@2600: ArgParser, a command line argument parser hegyi@2600: DistLog, a tool for measuring one and two dimensional distributions hegyi@2600: undirected minimum cut benchmarking hegyi@2600: tools/lgf-gen.cc, a random graph generator hegyi@2600: BpUGraphReader and Writer hegyi@2600: DynEdgeLookUp implementation based on splay trees hegyi@2600: MACROS for debug map usage hegyi@2600: - new algoritmhs hegyi@2600: Lagrange relaxation based algorithm for the delay constrained least cost path problem hegyi@2600: a preflow based general network circulation algorithm hegyi@2600: 2-approximation of Steiner-tree problem hegyi@2600: two heuristics (http://www.avglab.com/andrew/pub/neci-tr-96-132.ps) hegyi@2600: tsp2, a minimum spanning tree based TSP algorithm hegyi@2600: Delaunay triangulation hegyi@2600: Gomory-Hu tree algorithm hegyi@2600: Edmond's Blossom shrinking algorithm hegyi@2600: minimum mean cycle algorithm hegyi@2600: Goldberg-Tarjan algorithm (Preflow with Dynamic Trees) hegyi@2600: Dinitz-Sleator-Tarjan (Blocking flow with Dynamic Tree) hegyi@2600: - new distributions (Gaussian, exponential, Gamma, two dimensional random, buffered bit generation) hegyi@2600: - push-relabel type algorithm related additions hegyi@2600: Elevator, a class for handling item labels in push-relabel type algorithms hegyi@2600: a push/relabel type max cardinality matching implementation hegyi@2600: some query function for push-relabel based matching hegyi@2600: - LP related additions hegyi@2600: Soplex support hegyi@2600: ColIt class hegyi@2600: new functions (simplify(), isFinite(), row and col getter function) hegyi@2600: _setColCoeff and _setRowCoeff parameters hegyi@2600: section reader and writer for lemon IO hegyi@2600: equality-type constraint can now be added to a LP hegyi@2600: virtual functions of class LpCplex hegyi@2600: some query functions for GLPK hegyi@2600: - demos hegyi@2600: preflow based general network circulation demo hegyi@2600: Steiner 2-approximation demo hegyi@2600: demo for SAT problems hegyi@2600: sample input for sat-2 and sat demos hegyi@2600: - tests for hegyi@2600: graph copies hegyi@2600: random.h hegyi@2600: max weighted matchings hegyi@2600: - rename graphs script hegyi@2600: - planarity related additions hegyi@2600: checking and embedding hegyi@2600: planar grid embedding hegyi@2600: planar graph coloring hegyi@2600: - administrative improvements hegyi@2600: script for automatic checking of SVN commit's consistency hegyi@2600: automatic doc generation from the SVN trunk hegyi@2600: check for gcc version 3.3, 3.4, 4.0 and 4.1.2 as well hegyi@2600: reorganization of the modules and groups hegyi@2600: a tools directory added for useful executables codes hegyi@2600: doxygen hegyi@2600: renaming topology doxygen group to graph_prop doxygen group hegyi@2600: introducing planar doxygen group hegyi@2600: - bipartite matchings hegyi@2600: common interface hegyi@2600: Query functions: aMatching and bMatching hegyi@2600: ANodeMap matching map hegyi@2600: BNodeMap barrier map hegyi@2600: hegyi@2600: * changed, modified, improved hegyi@2600: - redesigned hegyi@2600: undirected edgesets (like the smart or ugraph) hegyi@2600: interface of MaxMatching and UnionFindEnum hegyi@2600: interface of maximum flow algorithms hegyi@2600: Kruskal algorithm hegyi@2600: augmenting path based bipartite matching hegyi@2600: - min cost flows hegyi@2600: various min cost flow solvers hegyi@2600: redesigned CapacityScaling algorithm hegyi@2600: - graph copy hegyi@2600: preliminary support for static graphs hegyi@2600: added BpUGraphCopy hegyi@2600: - execution hegyi@2600: conditional execution until the target is reached hegyi@2600: modified start() function in Dfs and Dijkstra classes to give back reached edge/node hegyi@2600: - Dijkstra hegyi@2600: return the temporary distance of the current node hegyi@2600: using operation traits hegyi@2600: - patch for retrieving reached/processed node in dijkstra, bfs and dfs hegyi@2600: - prescaling can be turned off in GraphToEps hegyi@2600: - better handling of inexact computation hegyi@2600: - easier inverse hegyi@2600: - faster geometric minimum spanning tree hegyi@2600: - new implementation of undirected graphs hegyi@2600: - Hao-Orlin algorithm became epsilon-safe hegyi@2600: - LpSoplex hegyi@2600: added getter functions hegyi@2600: better m4 file hegyi@2600: better handling of unsolved lps hegyi@2600: - allowing 'string' type quoting hegyi@2600: - clear() function for unionfinds hegyi@2600: - integer parameters also converted to double hegyi@2600: - hacking mip is possible without integer variables hegyi@2600: - space reservation for SmartGraph hegyi@2600: - path hegyi@2600: PathNodeIt hegyi@2600: PathWriter/Reader structures hegyi@2600: Distinct MapSet readers and writers hegyi@2600: more simple interface for PathDumper hegyi@2600: hegyi@2600: * updated hegyi@2600: - tutorial for hegyi@2600: algorithms hegyi@2600: graph visualization hegyi@2600: - documentation hegyi@2600: hegyi@2600: * rename hegyi@2600: - min_cut.h => nagamochi_ibaraki.h hegyi@2600: - clone => build hegyi@2600: - RevIt => RevEdgeIt hegyi@2600: - _FixId => LpId hegyi@2600: - setObj => obj hegyi@2600: - is_min => isMin hegyi@2600: - is_max => isMax hegyi@2600: - 'hugo' => 'lemon' hegyi@2600: - ball2() => disc() hegyi@2600: - state_enum => State hegyi@2600: - getNotifier => notifier hegyi@2600: - using LEMON_ASSERT instead of LogicError() hegyi@2600: - uedgeset is an alias for edgeset hegyi@2600: - CPXMIP_OPTIMAL_TOL status is considered as OPTIMAL too hegyi@2600: - removed "Type" suffix from typedefs hegyi@2600: - lower case local variables hegyi@2600: hegyi@2600: * removed hegyi@2600: - template Map template parameter from InvertableMaps hegyi@2600: - unionfind Item template parameter hegyi@2600: - strict checking hegyi@2600: - some automatic callback generation hegyi@2600: '-Wshadow' seemed too strict therefore removed hegyi@2600: hegyi@2600: * several bugfixes hegyi@2600: alpar@2278: 2006-10-31 Version 0.6 Released alpar@2280: * GLEMON has moved to a separate repository alpar@2280: (https://hugo.cs.elte.hu/svn/glemon/trunk) alpar@2278: * New Features alpar@2278: - Mixed Integer Programming (MIP) support alpar@2278: - interface to GLPK and CPLEX MIP solvers alpar@2278: - Data structures alpar@2278: - Bipatrite graph concepts and implementations alpar@2278: - a Polinomial template class alpar@2278: - RefPtr: a reference counted pointer class alpar@2278: - SimpleBucketHeap alpar@2278: - random.h: Mersenne Twister random number generator alpar@2278: - EdgeLookUp and AllEdgeLookUp alpar@2278: - Tools to find edges between to nodes in time O(log d) alpar@2278: - new matching algorithms alpar@2278: - Bipartite Graph Max Cardinality Matching (Hopcroft-Karp) alpar@2278: - MaxWeightedBipartiteMatching alpar@2278: - MinCostMaxBipartiteMatching alpar@2278: - MaxCardinalitySearch alpar@2278: - MinimalCut in UGraph alpar@2278: - Tabu Search framework alpar@2278: - Minimum Cost Arborescence algorithm alpar@2278: - Edmonds-Karp MaxFlow alpar@2278: - Hao-Orlin algorithm alpar@2278: - eps.h: A simple tool to create .eps pictures. alpar@2278: * Backward incompatibilities/changed namings: alpar@2278: - UndirXyz -> UXyz alpar@2278: - UNDIRGRAPH_TYPEDEFS -> UGRAPH_TYPEDEFS alpar@2278: - GridGraph -> GridUGraph alpar@2278: - LinearHeap -> BucketHeap alpar@2278: - ColorSet -> Palette alpar@2278: - xy -> dim2::Point alpar@2278: - DirPath -> Path alpar@2278: - concept -> concepts (namespace & directory) alpar@2278: - LpSolverBase alpar@2278: - ColName() -> colName alpar@2278: - Coeff() -> coeff() alpar@2278: - MinCostFlow -> SspMinCostFlow alpar@2278: * Repository reorganization: alpar@2278: - compilation is conducted by a single makefile alpar@2278: - internal building blocks are now in a separate directory alpar@2278: (lemon/bits) alpar@2278: * Major improvements many algorithms and data structures. alpar@2278: * Several bugfixes alpar@2278: * Compatibility issues: alpar@2278: - known to compile with alpar@2278: - GCC 3.3, 3.4, 4.0, 4.1 alpar@2278: - MinGW, MinGW32 alpar@2278: - Intel C++ 9.x support hegyi@2265: athos@2075: 2006-02-03 Version 0.5 Released klao@1945: * New features: klao@1945: - Bfs/Dfs/Dijkstra klao@1945: + query functions for the next node/edge to be processed klao@1945: + visitor interface for dfs klao@1945: - topology.h: small functions for discovering graph topology klao@1945: + connected components, strongly connected components klao@1945: + bipartiteness testing klao@1945: - Shortest paths algorithms: klao@1945: bellman_ford.h, floyd_warshall.h, johnson.h klao@1945: - Euler tour iterator for directed and undirected graphs klao@1945: - Other algorithms: klao@1945: + dag_shortest_path.h klao@1945: + fredman_tarjan.h and prim.h for min cost trees klao@1945: - Bipartite graph concept and implementations klao@1945: - Graph maps: klao@1945: + template assign operator klao@1945: + specialized iterable bool map athos@2075: + potential difference map klao@1945: + NodeMatrixMap -- Matrix over the nodes klao@1945: - Maps: klao@1945: + IterableIntMap klao@1945: - GUI: klao@1945: + NewMap window in MapSelector klao@1945: + Algorithm window and some algorithms (eg. Kruskal) added klao@1945: - LemonReader: klao@1945: + exception on non-existent files klao@1945: - LP interface: klao@1945: + (Dual)Expr::simplify(double tolerance) added klao@1945: + getDual() klao@1945: - GraphToEps: klao@1945: + negateY() opt klao@1945: + male/female node shapes :) alpar@1947: + correct %%BoundingBox handling klao@1945: - Tools: klao@1945: + Timer can be stop()ed and (re)start()ed alpar@1947: + radix sort algorithm klao@1945: + tolerance.h for working with imprecise numbers alpar@1947: * Backward incompatibilities/changed namings: alpar@1713: - Access functions of TimeStamp/Timer alpar@1947: - Undir graph interface: findUEdge, ConUEdgeIt klao@1945: - pred -> predEdge renaming in search algorithms klao@1945: - SnapShot -> Snapshot in {List,Smart}Graph klao@1945: - NewEdgeSetAdaptor -> ListEdgeSet klao@1945: - LP: set{Obj,Row,Col}() -> {obj,row,col}() klao@1945: - "label" instead of "id" inside the LGF files klao@1945: - UndirGraph -> UGraph, UndirEdge* -> UEdge* klao@1945: - BipartiteGraph -> BpGraph, Lower/UpperNode* -> A/BNode* athos@2075: * Bugfixes in alpar@1668: - DFS alpar@1668: - Preflow klao@1945: - x86_64 connected bugfixes (lemon_reader.h) klao@1945: - lp.h klao@1945: * New demos, benchmarks and tools: klao@1945: - graph_orientation.cc: A thoroughly documented demo application klao@1945: - runningTimeTest(): a tool to measure running times more precisely klao@1945: - Demo for topology athos@2075: - counter.h: a tool to measure the number of steps of algorithms klao@1945: - Some useful scripts: check-compiler, check-integrity klao@1945: * Other changes: klao@1945: - Demos and benchmarks are not built by default now. They can be klao@1945: enabled with the --enable-demo and --enable-benchmark klao@1945: configure flags. klao@1945: - GCC 4.0.3 and ICC 9.0 compatibility alpar@1713: alpar@1668: 2005-08-27 Version 0.4 Released alpar@1668: * List of new features and changes alpar@1713: * Changed namings: alpar@1668: Wrapper -> Adaptor alpar@1668: kruskalEdgeMap() -> kruskal() alpar@1668: kruskalEdgeMap_IteratorOut() -> kruskal() alpar@1668: * BoundinBox<> alpar@1668: * operator+=() -> add() alpar@1668: + clear() alpar@1668: + More and better graph I/O functionalities alpar@1668: + High level uniform LP solver interface to CPLEX and GLKP alpar@1668: * graphToEps() alpar@1668: + Automatic node size and edge width scaling alpar@1668: + Simple color palette tool (ColorSet) alpar@1668: * Bfs/Dfs/Dijkstra alpar@1668: + Step-by-step execution alpar@1668: + Run from multiple sources alpar@1668: + Used define stop condition alpar@1668: + Improved "named parameters" alpar@1668: * Preflow alpar@1668: + Function type interface alpar@1668: + Changed interface alpar@1668: * ListGraph/SmarGraph ladanyi@1670: + split() splits a node alpar@1668: + SnapShot alpar@1668: + New map adaptors ladanyi@1670: + New convenience maps alpar@1668: + IdMap, DescriptorMap alpar@1668: + InDegMap, OutDegMap alpar@1668: + XMap, YMap alpar@1668: + Default graph maps are iterable alpar@1668: + glemon: a graph editor alpar@1668: + Some new demo codes added, the old ones got polished. alpar@1668: * Better documentation alpar@1668: * Several important bugfixes alpar@1668: * Now lemon should compile without warnings with alpar@1668: * gcc 3.3, 3.4, 4.0 alpar@1668: * Intel C++ Compiler v9.0 alpar@1668: alpar@1668: 2005-03-19 Version 0.3.1 Released alpar@1668: * This release fixes a compilation failure bug under cygwin. alpar@1668: alpar@1668: 2005-02-21 Version 0.3 released alpar@1668: * List of new features and changes alpar@1668: * Redesigned Graph infrastructures alpar@1668: + Standardized LEMON exceptions alpar@1668: + Undirected Graph alpar@1668: + Standard graph file format, input and output classes for it. alpar@1668: * head() -> target(), tail() -> source() alpar@1668: * Some standard namings have changes: alpar@1668: ValueType -> Value, alpar@1668: KeyType -> Key, alpar@1668: ReferenceType ->Reference, alpar@1668: PointerType -> Pointer alpar@1668: + GraphToEps: A simple graph drawer alpar@1668: * Better documentation alpar@1668: alpar@1668: 2004-09-30 Version 0.2 released alpar@1668: