NEWS
author deba
Thu, 01 Mar 2007 16:47:49 +0000
changeset 2382 678bea23ed75
parent 2278 a61b7f4534c7
child 2600 e5530c0a018c
permissions -rw-r--r--
2-approximation of Steiner-tree problem
     1 2006-10-31  Version 0.6 Released
     2 	    * GLEMON has moved to a separate repository
     3               (https://hugo.cs.elte.hu/svn/glemon/trunk)
     4 	    * New Features
     5   	      - Mixed Integer Programming (MIP) support
     6     	      	- interface to GLPK and CPLEX MIP solvers
     7   	      - Data structures
     8 	        - Bipatrite graph concepts and implementations
     9     		- a Polinomial template class
    10     		- RefPtr: a reference counted pointer class
    11     		- SimpleBucketHeap  
    12 	      - random.h: Mersenne Twister random number generator
    13               - EdgeLookUp and AllEdgeLookUp
    14 	        - Tools to find edges between to nodes in time O(log d) 
    15     	      - new matching algorithms
    16       	        - Bipartite Graph Max Cardinality Matching (Hopcroft-Karp)
    17       	      	- MaxWeightedBipartiteMatching
    18 	      	- MinCostMaxBipartiteMatching
    19 	      	- MaxCardinalitySearch
    20     	      	- MinimalCut in UGraph
    21     	      - Tabu Search framework 
    22     	      - Minimum Cost Arborescence algorithm 
    23       	      - Edmonds-Karp MaxFlow
    24     	      - Hao-Orlin algorithm
    25 	      - eps.h: A simple tool to create .eps pictures.
    26 	    * Backward incompatibilities/changed namings:
    27 	      - UndirXyz -> UXyz
    28 	      - UNDIRGRAPH_TYPEDEFS -> UGRAPH_TYPEDEFS
    29 	      - GridGraph -> GridUGraph
    30   	      - LinearHeap -> BucketHeap
    31   	      - ColorSet -> Palette
    32   	      - xy -> dim2::Point
    33   	      - DirPath -> Path
    34     	      - concept -> concepts (namespace & directory)
    35 	      - LpSolverBase
    36 	        - ColName() -> colName
    37 		- Coeff() -> coeff()
    38 	      - MinCostFlow -> SspMinCostFlow
    39 	    * Repository reorganization:
    40   	      - compilation is conducted by a single makefile
    41 	      - internal building blocks are now in a separate directory
    42                 (lemon/bits)
    43 	    * Major improvements many algorithms and data structures.
    44 	    * Several bugfixes
    45 	    * Compatibility issues:
    46 	      - known to compile with
    47 	        - GCC 3.3, 3.4, 4.0, 4.1 
    48 		- MinGW, MinGW32
    49 		- Intel C++ 9.x support
    50 
    51 2006-02-03  Version 0.5 Released
    52 	* New features:
    53 	  - Bfs/Dfs/Dijkstra
    54 	    + query functions for the next node/edge to be processed
    55 	    + visitor interface for dfs
    56 	  - topology.h: small functions for discovering graph topology
    57 	    + connected components, strongly connected components
    58 	    + bipartiteness testing
    59 	  - Shortest paths algorithms:
    60 	    bellman_ford.h, floyd_warshall.h, johnson.h
    61 	  - Euler tour iterator for directed and undirected graphs
    62 	  - Other algorithms:
    63 	    + dag_shortest_path.h
    64 	    + fredman_tarjan.h and prim.h for min cost trees
    65 	  - Bipartite graph concept and implementations
    66 	  - Graph maps:
    67 	    + template assign operator
    68 	    + specialized iterable bool map
    69 	    + potential difference map
    70 	    + NodeMatrixMap -- Matrix over the nodes
    71 	  - Maps:
    72 	    + IterableIntMap
    73 	  - GUI:
    74 	    + NewMap window in MapSelector
    75 	    + Algorithm window and some algorithms (eg. Kruskal) added
    76 	  - LemonReader:
    77 	    + exception on non-existent files
    78 	  - LP interface:
    79 	    + (Dual)Expr::simplify(double tolerance) added
    80 	    + getDual()
    81 	  - GraphToEps:
    82 	    + negateY() opt
    83 	    + male/female node shapes :)
    84 	    + correct %%BoundingBox handling
    85 	  - Tools:
    86 	    + Timer can be stop()ed and (re)start()ed
    87 	    + radix sort algorithm
    88 	    + tolerance.h for working with imprecise numbers
    89 	* Backward incompatibilities/changed namings:
    90 	  - Access functions of TimeStamp/Timer
    91 	  - Undir graph interface: findUEdge, ConUEdgeIt
    92 	  - pred -> predEdge renaming in search algorithms
    93 	  - SnapShot -> Snapshot in {List,Smart}Graph
    94 	  - NewEdgeSetAdaptor -> ListEdgeSet
    95 	  - LP: set{Obj,Row,Col}() -> {obj,row,col}()
    96 	  - "label" instead of "id" inside the LGF files
    97 	  - UndirGraph -> UGraph, UndirEdge* -> UEdge*
    98 	  - BipartiteGraph -> BpGraph, Lower/UpperNode* -> A/BNode*
    99 	* Bugfixes in
   100 	  - DFS
   101 	  - Preflow
   102 	  - x86_64 connected bugfixes (lemon_reader.h)
   103 	  - lp.h
   104 	* New demos, benchmarks and tools:
   105 	  - graph_orientation.cc: A thoroughly documented demo application
   106 	  - runningTimeTest(): a tool to measure running times more precisely
   107 	  - Demo for topology
   108 	  - counter.h: a tool to measure the number of steps of algorithms
   109 	  - Some useful scripts: check-compiler, check-integrity
   110 	* Other changes:
   111 	  - Demos and benchmarks are not built by default now. They can be
   112 	    enabled with the --enable-demo and --enable-benchmark
   113 	    configure flags.
   114 	  - GCC 4.0.3 and ICC 9.0 compatibility
   115 	  
   116 2005-08-27  Version 0.4 Released
   117 	* List of new features and changes	
   118 	  * Changed namings:
   119 	    Wrapper -> Adaptor
   120 	    kruskalEdgeMap() -> kruskal()
   121 	    kruskalEdgeMap_IteratorOut() -> kruskal()
   122 	  * BoundinBox<>
   123 	    * operator+=() -> add()
   124 	    + clear()
   125 	  + More and better graph I/O functionalities
   126 	  + High level uniform LP solver interface to CPLEX and GLKP
   127 	  * graphToEps()
   128 	    + Automatic node size and edge width scaling
   129 	    + Simple color palette tool (ColorSet)
   130 	  * Bfs/Dfs/Dijkstra
   131 	    + Step-by-step execution
   132 	    + Run from multiple sources
   133 	    + Used define stop condition
   134 	    + Improved "named parameters"
   135 	  * Preflow
   136 	    + Function type interface
   137 	    + Changed interface
   138 	  * ListGraph/SmarGraph
   139 	    + split() splits a node
   140 	    + SnapShot
   141 	  + New map adaptors
   142 	  + New convenience maps
   143 	    + IdMap, DescriptorMap
   144 	    + InDegMap, OutDegMap
   145 	    + XMap, YMap
   146 	  + Default graph maps are iterable
   147 	  + glemon: a graph editor
   148 	  + Some new demo codes added, the old ones got polished.
   149 	  * Better documentation
   150 	  * Several important bugfixes
   151 	  * Now lemon should compile without warnings with
   152 	    * gcc 3.3, 3.4, 4.0
   153 	    * Intel C++ Compiler v9.0 
   154 
   155 2005-03-19  Version 0.3.1 Released
   156 	* This release fixes a compilation failure bug under cygwin. 
   157 
   158 2005-02-21  Version 0.3 released
   159 	* List of new features and changes	
   160 	  * Redesigned Graph infrastructures
   161 	  + Standardized LEMON exceptions
   162 	  + Undirected Graph
   163 	  + Standard graph file format, input and output classes for it.
   164 	  * head() -> target(), tail() -> source()
   165 	  * Some standard namings have changes:
   166 	    ValueType -> Value, 
   167 	    KeyType -> Key,
   168 	    ReferenceType ->Reference,
   169 	    PointerType -> Pointer
   170 	  + GraphToEps: A simple graph drawer
   171 	  * Better documentation
   172 	
   173 2004-09-30  Version 0.2 released
   174