NEWS
changeset 2600 e5530c0a018c
parent 2280 dc726706ea65
child 2601 054de623255b
     1.1 --- a/NEWS	Thu Apr 03 12:06:48 2008 +0000
     1.2 +++ b/NEWS	Mon Apr 07 16:28:20 2008 +0000
     1.3 @@ -1,3 +1,152 @@
     1.4 +2008-02-08 Version 0.7 released
     1.5 +
     1.6 +	* added
     1.7 +		- new data structures
     1.8 +			classes
     1.9 +				StaticGraphBase
    1.10 +				ExtendFindEnum
    1.11 +				BfsVisitor class
    1.12 +					Bipartite partitions based on visitors
    1.13 +			helper class for checking existence of a nested class
    1.14 +			general mapping based variant type
    1.15 +			IntegerMap
    1.16 +		- new functions and tools
    1.17 +			ArgParser, a command line argument parser
    1.18 +			DistLog, a tool for measuring one and two dimensional distributions
    1.19 +			undirected minimum cut benchmarking
    1.20 +			tools/lgf-gen.cc, a random graph generator
    1.21 +			BpUGraphReader and Writer
    1.22 +			DynEdgeLookUp implementation based on splay trees
    1.23 +			MACROS for debug map usage
    1.24 +		- new algoritmhs
    1.25 +			Lagrange relaxation based algorithm for the delay constrained least cost path problem
    1.26 +			a preflow based general network circulation algorithm
    1.27 +			2-approximation of Steiner-tree problem
    1.28 +			two heuristics (http://www.avglab.com/andrew/pub/neci-tr-96-132.ps)
    1.29 +			tsp2, a minimum spanning tree based TSP algorithm
    1.30 +			Delaunay triangulation
    1.31 +			Gomory-Hu tree algorithm
    1.32 +			Edmond's Blossom shrinking algorithm
    1.33 +			minimum mean cycle algorithm
    1.34 +			Goldberg-Tarjan algorithm (Preflow with Dynamic Trees)
    1.35 +			Dinitz-Sleator-Tarjan (Blocking flow with Dynamic Tree)
    1.36 +		- new distributions (Gaussian, exponential, Gamma, two dimensional random, buffered bit generation)
    1.37 +		- push-relabel type algorithm related additions
    1.38 +			Elevator, a class for handling item labels in push-relabel type algorithms
    1.39 +			a push/relabel type max cardinality matching implementation
    1.40 +			some query function for push-relabel based matching
    1.41 +		- LP related additions
    1.42 +			Soplex support
    1.43 +			ColIt class
    1.44 +			new functions (simplify(), isFinite(), row and col getter function)
    1.45 +			_setColCoeff and _setRowCoeff parameters
    1.46 +			section reader and writer for lemon IO
    1.47 +			equality-type constraint can now be added to a LP
    1.48 +			virtual functions of class LpCplex
    1.49 +			some query functions for GLPK
    1.50 +		- demos
    1.51 +			preflow based general network circulation demo
    1.52 +			Steiner 2-approximation demo
    1.53 +			demo for SAT problems
    1.54 +			sample input for sat-2 and sat demos
    1.55 +		- tests for
    1.56 +			graph copies
    1.57 +			random.h
    1.58 +			max weighted matchings
    1.59 +		- rename graphs script
    1.60 +		- planarity related additions
    1.61 +			checking and embedding
    1.62 +			planar grid embedding
    1.63 +			planar graph coloring
    1.64 +		- administrative improvements
    1.65 +			script for automatic checking of SVN commit's consistency
    1.66 +			automatic doc generation from the SVN trunk
    1.67 +			check for gcc version 3.3, 3.4, 4.0 and 4.1.2 as well
    1.68 +			reorganization of the modules and groups
    1.69 +			a tools directory added for useful executables codes
    1.70 +			doxygen
    1.71 +				renaming topology doxygen group to graph_prop doxygen group
    1.72 +				introducing planar doxygen group
    1.73 +		- bipartite matchings
    1.74 +			common interface
    1.75 +			Query functions: aMatching and bMatching
    1.76 +			ANodeMap<UEdge> matching map
    1.77 +			BNodeMap<bool> barrier map
    1.78 +
    1.79 +	* changed, modified, improved
    1.80 +		- redesigned
    1.81 +			undirected edgesets (like the smart or ugraph)
    1.82 +			interface of MaxMatching and UnionFindEnum
    1.83 +			interface of maximum flow algorithms
    1.84 +			Kruskal algorithm
    1.85 +			augmenting path based bipartite matching
    1.86 +		- min cost flows
    1.87 +			various min cost flow solvers
    1.88 +			redesigned CapacityScaling algorithm
    1.89 +		- graph copy
    1.90 +			preliminary support for static graphs
    1.91 +			added BpUGraphCopy
    1.92 +		- execution
    1.93 +			conditional execution until the target is reached 
    1.94 +			modified start() function in Dfs and Dijkstra classes to give back reached edge/node
    1.95 +		- Dijkstra
    1.96 +			return the temporary distance of the current node
    1.97 +			using operation traits
    1.98 +		- patch for retrieving reached/processed node in dijkstra, bfs and dfs
    1.99 +		- prescaling can be turned off in GraphToEps
   1.100 +		- better handling of inexact computation
   1.101 +		- easier inverse
   1.102 +		- faster geometric minimum spanning tree
   1.103 +		- new implementation of undirected graphs
   1.104 +		- Hao-Orlin algorithm became epsilon-safe
   1.105 +		- LpSoplex
   1.106 +			added getter functions
   1.107 +			better m4 file
   1.108 +			better handling of unsolved lps
   1.109 +		- allowing 'string' type quoting
   1.110 +		- clear() function for unionfinds
   1.111 +		- integer parameters also converted to double
   1.112 +		- hacking mip is possible without integer variables
   1.113 +		- space reservation for SmartGraph
   1.114 +		- path
   1.115 +			PathNodeIt
   1.116 +				PathWriter/Reader structures
   1.117 +				Distinct MapSet readers and writers
   1.118 +			more simple interface for PathDumper
   1.119 +
   1.120 +	* updated
   1.121 +		- tutorial for
   1.122 +			algorithms
   1.123 +			graph visualization
   1.124 +		- documentation
   1.125 +
   1.126 +	* rename
   1.127 +		- min_cut.h => nagamochi_ibaraki.h
   1.128 +		- clone => build
   1.129 +		- RevIt => RevEdgeIt
   1.130 +		- _FixId => LpId
   1.131 +		- setObj => obj
   1.132 +		- is_min => isMin
   1.133 +		- is_max => isMax
   1.134 +		- 'hugo' => 'lemon'
   1.135 +		- ball2() => disc()
   1.136 +		- state_enum => State
   1.137 +		- getNotifier => notifier
   1.138 +		- using LEMON_ASSERT instead of LogicError()
   1.139 +		- uedgeset is an alias for edgeset
   1.140 +		- CPXMIP_OPTIMAL_TOL status is considered as OPTIMAL too
   1.141 +		- removed "Type" suffix from typedefs
   1.142 +		- lower case local variables
   1.143 +
   1.144 +	* removed
   1.145 +		- template Map template parameter from InvertableMaps
   1.146 +		- unionfind Item template parameter
   1.147 +		- strict checking
   1.148 +		- some automatic callback generation 
   1.149 +		'-Wshadow' seemed too strict therefore removed
   1.150 +
   1.151 +	* several bugfixes
   1.152 +
   1.153  2006-10-31  Version 0.6 Released
   1.154  	    * GLEMON has moved to a separate repository
   1.155                (https://hugo.cs.elte.hu/svn/glemon/trunk)