hegyi@2265: 2006-10-27 Version 0.6 Released hegyi@2265: hegyi@2265: #New hegyi@2265: *functor usage for writeable map adaptors hegyi@2265: *MIP support hegyi@2265: -interface to the cplex MIP solver hegyi@2265: *data structures hegyi@2265: -ListBpUGraph hegyi@2265: -SmartEdgeset hegyi@2265: -RefPtr: a reference counted pointer class hegyi@2265: -two state variant hegyi@2265: -Polinomial template class hegyi@2265: -SimpleBucketHeap hegyi@2265: -even a smaller version hegyi@2265: -tolerance class hegyi@2265: -Tolerance and Tolerance added hegyi@2265: -the extender system hegyi@2265: -some UGraphExtender /SubUGraphExtenders, DirectUGraphExtender/ hegyi@2265: -adaptor related hegyi@2265: -ResGraphAdaptor with Tolerance hegyi@2265: -SwapBpUGraphAdaptor which swaps the two nodeset of the bipartite graph hegyi@2265: -map related hegyi@2265: -SimpleMap and SimpleWriteMap hegyi@2265: -new map type based on array map for debugging purpose hegyi@2265: -DynamicAsymMatrixMap hegyi@2265: -MatrixMapTraits hegyi@2265: *functions hegyi@2265: -optimality test on random graph hegyi@2265: -implementation of the drand48 functions hegyi@2265: -negative cycle to path converter hegyi@2265: -reserveNode function hegyi@2265: -Mersenne Twister random number generator hegyi@2265: -EdgeLookUp and AllEdgeLookUp hegyi@2265: *scripts hegyi@2265: -script that lists all the header files included directly or indirectly by a certain header file hegyi@2265: -script creates/updates the copyright header of a source file hegyi@2265: *algorithms hegyi@2265: -algorithm group for matchings hegyi@2265: -Bipartite Graph Max Cardinality Matching (Hopcroft-Karp) hegyi@2265: -MaxWeightedBipartiteMatching hegyi@2265: -MinCostMaxBipartiteMatching hegyi@2265: -MaxCardinalitySearch hegyi@2265: -MinimalCut in UGraph hegyi@2265: -tabu search hegyi@2265: -Minimum Cost Arborescence algorithm hegyi@2265: -dual solution computation and interface for algorithm hegyi@2265: -Edmonds-Karp MaxFlow hegyi@2265: -Hao-Orlin algorithm hegyi@2265: hegyi@2265: #Progress in already existing objects: hegyi@2265: *radix sort to ansi compatible hegyi@2265: *map creation based on virtual base class is possible hegyi@2265: *default constructor which allocates empty graphs hegyi@2265: *defaultMap is introdouced, graph maps should not be inherited from the ObserverBase. hegyi@2265: *clarifing alteration observing system hegyi@2265: *resize for static size graph hegyi@2265: *an additional simplier interface for static size graphs. hegyi@2265: *Node operator()(int) for getting node by index hegyi@2265: *int index(Node node) for getting index by node hegyi@2265: *traits for alteration notifiers hegyi@2265: *graph adadptors can be alteration observed hegyi@2265: *count ANodes-BNodes in bipartite graphs hegyi@2265: *the template assign operators and map iterators can be used for adaptors also hegyi@2265: *writeable extension of some maps hegyi@2265: *rot180() added to xy.h hegyi@2265: *change source and target for the bipartite list graph hegyi@2265: *findEdge extension also for the BpUGraphs hegyi@2265: *proper handling of loop edges in the UGraph::findUEdge hegyi@2265: *exported interface to the Graph class hegyi@2265: *new random interface hegyi@2265: *graph imlementations actually provide ReferenceMaps hegyi@2265: *lgf2ps: hegyi@2265: -RGB color related stuff is in color.h now hegyi@2265: -simple class to create .eps figures (eps.h) hegyi@2265: -"Node shapes" added hegyi@2265: -some color constants added (BLACK, WHITE, RED etc) hegyi@2265: -absolute/relative node size/link width scaling hegyi@2265: hegyi@2265: #Taken out: hegyi@2265: *SplitGraph is temporarly deleted hegyi@2265: *SubBidirGraphAdaptor hegyi@2265: *obsolote "id" map handling hegyi@2265: *concepts for extendable and erasable graphs hegyi@2265: *exceptionName() hegyi@2265: *bezier.h hegyi@2265: *functional interfaces hegyi@2265: *UPath hegyi@2265: hegyi@2265: #Rewritten, modificated, improved hegyi@2265: *UnionFindEnum revision hegyi@2265: *countItems hegyi@2265: *findEdges hegyi@2265: *IncEdgeIt goes through on loop edges twice. hegyi@2265: *mining of the clear in heaps hegyi@2265: *SplitGraphAdaptor hegyi@2265: *item sets are written in the order sorted by the labels hegyi@2265: *make explicit constructors hegyi@2265: *snapshot hegyi@2265: -rewritten hegyi@2265: -implemented for SmartUGraph an SmartBpUGraph hegyi@2265: *Node/Edge::operator<() is required by the concept hegyi@2265: *Graph Component concepts hegyi@2265: *disabled the copy constructor and operator- of {List|Smart}[U]Graph. hegyi@2265: *modificated interface: colType() functions hegyi@2265: *made public what() in NodeSetError hegyi@2265: *improvment in exception handling hegyi@2265: -exception safe erase and clear handler hegyi@2265: -proper exception handling in the SmartEdgeSet hegyi@2265: -rethrow of exception missing hegyi@2265: *signaling alterations in BpUGraphs hegyi@2265: *UnionFind hegyi@2265: -takes less space hegyi@2265: -UnionFindEnum hegyi@2265: -changed interface hegyi@2265: *updated the Path concept hegyi@2265: *item readers and writers hegyi@2265: hegyi@2265: #Reorganized: hegyi@2265: *bootstrap: quiet option hegyi@2265: *utility, invalid and traits moved to bits hegyi@2265: *section readers moved to own group hegyi@2265: *separate group for matrices hegyi@2265: *single makefile hegyi@2265: *glemon is moved to own repository hegyi@2265: *graph_component.h -> graph_components.h hegyi@2265: *reference to modules added hegyi@2265: *disable assertions in default behaviour hegyi@2265: *BiVariant moved to lemon/bits/variant.h hegyi@2265: *using abort() instead of exit(1) hegyi@2265: hegyi@2265: #Renamed: hegyi@2265: *Undir -> U hegyi@2265: *Minimum -> Min hegyi@2265: *Work -> Aux hegyi@2265: *UGraphExtender -> UndirectGraphExtender hegyi@2265: -UGraphExtenders with changed meaning hegyi@2265: *GridGraph -> GridUGraph hegyi@2265: *UNDIRGRAPH_TYPEDEFS -> UGRAPH_TYPEDEFS hegyi@2265: *LinearHeap -> BucketHeap hegyi@2265: *UGraphBaseExtender -> UndirGraphExtender hegyi@2265: *BpUGraphBaseExtender merged into BpUGraphExtender hegyi@2265: *StaticGraph to Graph hegyi@2265: *ColorSet to Palette hegyi@2265: *xy -> dim2::Point hegyi@2265: *DirPath to Path hegyi@2265: *concept -> concepts (namespace & directory) hegyi@2265: hegyi@2265: #Compatibility issues: hegyi@2265: *compilation with G++ -ansi hegyi@2265: *gcc-4.1 hegyi@2265: *NaN checking to be conform to MinGW32 hegyi@2265: *MinGW, MinGW32 hegyi@2265: *long long just for gnu compilers hegyi@2265: *CPLEX 9.x support hegyi@2265: *turned off 32bit specific tests. hegyi@2265: hegyi@2265: #Beyond the aboves several bugfix and documentation improvement is made, new demos, benchmarks are implemented. 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: