2008-02-08 Version 0.7 released 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 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) * 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 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 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 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 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 + 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 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. 2005-02-21 Version 0.3 released 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