source: lemon-0.x/NEWS @ 2448:ab899ae3505f

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