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