NEWS
changeset 2600 e5530c0a018c
parent 2280 dc726706ea65
child 2601 054de623255b
equal deleted inserted replaced
11:205e59c1ffe8 12:efbac2f0ea56
       
     1 2008-02-08 Version 0.7 released
       
     2 
       
     3 	* added
       
     4 		- new data structures
       
     5 			classes
       
     6 				StaticGraphBase
       
     7 				ExtendFindEnum
       
     8 				BfsVisitor class
       
     9 					Bipartite partitions based on visitors
       
    10 			helper class for checking existence of a nested class
       
    11 			general mapping based variant type
       
    12 			IntegerMap
       
    13 		- new functions and tools
       
    14 			ArgParser, a command line argument parser
       
    15 			DistLog, a tool for measuring one and two dimensional distributions
       
    16 			undirected minimum cut benchmarking
       
    17 			tools/lgf-gen.cc, a random graph generator
       
    18 			BpUGraphReader and Writer
       
    19 			DynEdgeLookUp implementation based on splay trees
       
    20 			MACROS for debug map usage
       
    21 		- new algoritmhs
       
    22 			Lagrange relaxation based algorithm for the delay constrained least cost path problem
       
    23 			a preflow based general network circulation algorithm
       
    24 			2-approximation of Steiner-tree problem
       
    25 			two heuristics (http://www.avglab.com/andrew/pub/neci-tr-96-132.ps)
       
    26 			tsp2, a minimum spanning tree based TSP algorithm
       
    27 			Delaunay triangulation
       
    28 			Gomory-Hu tree algorithm
       
    29 			Edmond's Blossom shrinking algorithm
       
    30 			minimum mean cycle algorithm
       
    31 			Goldberg-Tarjan algorithm (Preflow with Dynamic Trees)
       
    32 			Dinitz-Sleator-Tarjan (Blocking flow with Dynamic Tree)
       
    33 		- new distributions (Gaussian, exponential, Gamma, two dimensional random, buffered bit generation)
       
    34 		- push-relabel type algorithm related additions
       
    35 			Elevator, a class for handling item labels in push-relabel type algorithms
       
    36 			a push/relabel type max cardinality matching implementation
       
    37 			some query function for push-relabel based matching
       
    38 		- LP related additions
       
    39 			Soplex support
       
    40 			ColIt class
       
    41 			new functions (simplify(), isFinite(), row and col getter function)
       
    42 			_setColCoeff and _setRowCoeff parameters
       
    43 			section reader and writer for lemon IO
       
    44 			equality-type constraint can now be added to a LP
       
    45 			virtual functions of class LpCplex
       
    46 			some query functions for GLPK
       
    47 		- demos
       
    48 			preflow based general network circulation demo
       
    49 			Steiner 2-approximation demo
       
    50 			demo for SAT problems
       
    51 			sample input for sat-2 and sat demos
       
    52 		- tests for
       
    53 			graph copies
       
    54 			random.h
       
    55 			max weighted matchings
       
    56 		- rename graphs script
       
    57 		- planarity related additions
       
    58 			checking and embedding
       
    59 			planar grid embedding
       
    60 			planar graph coloring
       
    61 		- administrative improvements
       
    62 			script for automatic checking of SVN commit's consistency
       
    63 			automatic doc generation from the SVN trunk
       
    64 			check for gcc version 3.3, 3.4, 4.0 and 4.1.2 as well
       
    65 			reorganization of the modules and groups
       
    66 			a tools directory added for useful executables codes
       
    67 			doxygen
       
    68 				renaming topology doxygen group to graph_prop doxygen group
       
    69 				introducing planar doxygen group
       
    70 		- bipartite matchings
       
    71 			common interface
       
    72 			Query functions: aMatching and bMatching
       
    73 			ANodeMap<UEdge> matching map
       
    74 			BNodeMap<bool> barrier map
       
    75 
       
    76 	* changed, modified, improved
       
    77 		- redesigned
       
    78 			undirected edgesets (like the smart or ugraph)
       
    79 			interface of MaxMatching and UnionFindEnum
       
    80 			interface of maximum flow algorithms
       
    81 			Kruskal algorithm
       
    82 			augmenting path based bipartite matching
       
    83 		- min cost flows
       
    84 			various min cost flow solvers
       
    85 			redesigned CapacityScaling algorithm
       
    86 		- graph copy
       
    87 			preliminary support for static graphs
       
    88 			added BpUGraphCopy
       
    89 		- execution
       
    90 			conditional execution until the target is reached 
       
    91 			modified start() function in Dfs and Dijkstra classes to give back reached edge/node
       
    92 		- Dijkstra
       
    93 			return the temporary distance of the current node
       
    94 			using operation traits
       
    95 		- patch for retrieving reached/processed node in dijkstra, bfs and dfs
       
    96 		- prescaling can be turned off in GraphToEps
       
    97 		- better handling of inexact computation
       
    98 		- easier inverse
       
    99 		- faster geometric minimum spanning tree
       
   100 		- new implementation of undirected graphs
       
   101 		- Hao-Orlin algorithm became epsilon-safe
       
   102 		- LpSoplex
       
   103 			added getter functions
       
   104 			better m4 file
       
   105 			better handling of unsolved lps
       
   106 		- allowing 'string' type quoting
       
   107 		- clear() function for unionfinds
       
   108 		- integer parameters also converted to double
       
   109 		- hacking mip is possible without integer variables
       
   110 		- space reservation for SmartGraph
       
   111 		- path
       
   112 			PathNodeIt
       
   113 				PathWriter/Reader structures
       
   114 				Distinct MapSet readers and writers
       
   115 			more simple interface for PathDumper
       
   116 
       
   117 	* updated
       
   118 		- tutorial for
       
   119 			algorithms
       
   120 			graph visualization
       
   121 		- documentation
       
   122 
       
   123 	* rename
       
   124 		- min_cut.h => nagamochi_ibaraki.h
       
   125 		- clone => build
       
   126 		- RevIt => RevEdgeIt
       
   127 		- _FixId => LpId
       
   128 		- setObj => obj
       
   129 		- is_min => isMin
       
   130 		- is_max => isMax
       
   131 		- 'hugo' => 'lemon'
       
   132 		- ball2() => disc()
       
   133 		- state_enum => State
       
   134 		- getNotifier => notifier
       
   135 		- using LEMON_ASSERT instead of LogicError()
       
   136 		- uedgeset is an alias for edgeset
       
   137 		- CPXMIP_OPTIMAL_TOL status is considered as OPTIMAL too
       
   138 		- removed "Type" suffix from typedefs
       
   139 		- lower case local variables
       
   140 
       
   141 	* removed
       
   142 		- template Map template parameter from InvertableMaps
       
   143 		- unionfind Item template parameter
       
   144 		- strict checking
       
   145 		- some automatic callback generation 
       
   146 		'-Wshadow' seemed too strict therefore removed
       
   147 
       
   148 	* several bugfixes
       
   149 
     1 2006-10-31  Version 0.6 Released
   150 2006-10-31  Version 0.6 Released
     2 	    * GLEMON has moved to a separate repository
   151 	    * GLEMON has moved to a separate repository
     3               (https://hugo.cs.elte.hu/svn/glemon/trunk)
   152               (https://hugo.cs.elte.hu/svn/glemon/trunk)
     4 	    * New Features
   153 	    * New Features
     5   	      - Mixed Integer Programming (MIP) support
   154   	      - Mixed Integer Programming (MIP) support