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