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) * 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 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 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 2005-03-19 Version 0.3.1 Released * 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 2004-09-30 Version 0.2 released