NEWS
author kpeter
Thu, 13 Nov 2008 15:29:04 +0000
changeset 2629 84354c78b068
parent 2606 710c714a7dd3
permissions -rw-r--r--
Improved constructors for min cost flow classes
Removing the non-zero lower bounds is faster
     1 2008-02-08 Version 0.7 released
     2 	New Features
     3 		+ new data structures
     4 			* classes
     5 				StaticGraph
     6 				ExtendFindEnum
     7 				BfsVisitor class
     8 					Bipartite partitions based on visitors
     9 			* helper class for checking existence of a nested class
    10 			* general mapping based variant type
    11 			* IntegerMap
    12 		+ new algoritmhs
    13 			* Lagrange relaxation based algorithm for the delay constrained least cost path problem
    14 			* a preflow based general network circulation algorithm
    15 			* 2-approximation of Steiner-tree problem
    16 			* two heuristics for minimum cut algorithms (http://www.avglab.com/andrew/pub/neci-tr-96-132.ps)
    17 			* Gomory-Hu tree algorithm
    18 			* Edmond's Blossom shrinking algorithm
    19 			* minimum mean cycle algorithm
    20 			* Goldberg-Tarjan algorithm (Preflow with Dynamic Trees)
    21 			* Dinitz-Sleator-Tarjan (Blocking flow with Dynamic Tree)
    22 			* min cost flow algorithms:
    23 				* successive shortest path algorithm
    24 				* capacity scaling algorithm
    25 				* simple cycle canceling algorithm
    26 				* minimum mean cycle canceling algorithm
    27 				* cost scaling algorithm
    28 				* network simplex algorithm
    29 			* min cost maximum flow algorithm
    30 		+ new functions and tools
    31 			* ArgParser, a command line argument parser
    32 			* DistLog, a tool for measuring one and two dimensional distributions
    33 			* undirected minimum cut benchmarking
    34 			* tools/lgf-gen.cc, a random graph generator
    35 			* BpUGraphReader and Writer
    36 			* DynEdgeLookUp implementation based on splay trees
    37 			* MACROS for debug map usage
    38 		+ new distributions (Gaussian, exponential, Gamma, two dimensional random, buffered bit generation)
    39 		+ push-relabel type algorithm related additions
    40 			* Elevator, a class for handling item labels in push-relabel type algorithms
    41 			* a push/relabel type max cardinality matching implementation
    42 			* some query function for push-relabel based matching
    43 		+ LP related additions
    44 			* Soplex support
    45 			* ColIt class
    46 			* new functions (simplify(), isFinite(), row and col getter function)
    47 			* _setColCoeff and _setRowCoeff parameters
    48 			* section reader and writer for LEMON IO
    49 			* equality-type constraint can now be added to a LP
    50 			* virtual functions of class LpCplex
    51 			* some query functions for GLPK
    52 		+ demos
    53 			* preflow based general network circulation demo
    54 			* Steiner 2-approximation demo
    55 			* demo for SAT problems
    56 			* sample input for sat-2 and sat demos
    57 		+ tests for
    58 			* graph copies
    59 			* random.h
    60 			* max weighted matchings
    61 		+ planarity related additions
    62 			* checking and embedding
    63 			* planar grid embedding
    64 			* planar graph coloring
    65 		+ bipartite matchings
    66 			* common interface
    67 			* Query functions: aMatching and bMatching
    68 			* ANodeMap<UEdge> matching map
    69 			* BNodeMap<bool> barrier map
    70 	Repository reorganization
    71 		* script for automatic checking of SVN commit's consistency
    72 		* automatic doc generation from the SVN trunk
    73 		* check for gcc version 3.3, 3.4, 4.0 and 4.1.2 as well
    74 		* reorganization of the modules and groups
    75 		* a tools directory added for useful executables codes
    76 		* doxygen
    77 			* renaming topology doxygen group to graph_prop doxygen group
    78 			* introducing planar doxygen group
    79 	Changes
    80 		*  redesigned
    81 			* undirected edgesets (like the smart graph or ugraph)
    82 			* interface of MaxMatching and UnionFindEnum
    83 			* interface of maximum flow algorithms
    84 			* Kruskal algorithm
    85 			* augmenting path based bipartite matching
    86 	Improvements
    87 		* graph copy
    88 			* preliminary support for static graphs
    89 			* added BpUGraphCopy
    90 		* Bfs/Dfs/Dijkstra
    91 			* conditional execution until the target is reached 
    92 			* modified start() function in Dfs and Dijkstra classes to give back reached edge/node
    93 			* return the temporary distance of the current node
    94 			* using operation traits in Dijkstra
    95 			* patch for retrieving reached/processed node
    96 		* prescaling can be turned off in GraphToEps
    97 		* better handling of inexact computations
    98 		* easier inverse
    99 		* faster geometric minimum spanning tree algorithm
   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 for item reading and writing
   107 		* clear() function for union-find structures
   108 		* hacking MIP is possible without integer variables
   109 		* space reservation for SmartGraph
   110 		* path
   111 			* PathNodeIt
   112 				PathWriter/Reader structures
   113 				Distinct MapSet readers and writers
   114 			* more simple interface for PathDumper
   115 	Updated
   116 		* tutorial for
   117 			* algorithms
   118 			* graph visualization
   119 		* documentation
   120 	Backward incompatibilities/changed namings
   121 		* min_cut.h => nagamochi_ibaraki.h
   122 		* clone => build
   123 		* RevIt => RevEdgeIt
   124 		* _FixId => LpId
   125 		* setObj => obj
   126 		* is_min => isMin
   127 		* is_max => isMax
   128 		* ball2() => disc()
   129 		* state_enum => State
   130 		* getNotifier => notifier
   131 		* using LEMON_ASSERT instead of LogicError()
   132 		* uedgeset is an alias for edgeset
   133 		* CPXMIP_OPTIMAL_TOL status is considered as OPTIMAL too
   134 		* removed "Type" suffix from typedefs
   135 		* lower case local variables
   136 	Removed
   137 		- SspMinCostFlow
   138 		- template Map template parameter from InvertableMaps
   139 		- union-find Item template parameter
   140 		- strict checking
   141 		- some automatic callback generation 
   142 		- '-Wshadow' seemed too strict therefore removed
   143 	Several bugfixes
   144 
   145 2006-10-31  Version 0.6 Released
   146 	GLEMON has moved to a separate repository
   147 		(https://hugo.cs.elte.hu/svn/glemon/trunk)
   148 	New Features
   149 		+ Mixed Integer Programming (MIP) support
   150 		+ interface to GLPK and CPLEX MIP solvers
   151 		+ Data structures
   152 			* Bipatrite graph concepts and implementations
   153 			* a Polinomial template class
   154 			* RefPtr: a reference counted pointer class
   155 			* SimpleBucketHeap  
   156 		+ random.h: Mersenne Twister random number generator
   157 		+ EdgeLookUp and AllEdgeLookUp
   158 		+ Tools to find edges between to nodes in time O(log d) 
   159 		+ new matching algorithms
   160 		+ Bipartite Graph Max Cardinality Matching (Hopcroft-Karp)
   161 		+ MaxWeightedBipartiteMatching
   162 		+ MinCostMaxBipartiteMatching
   163 		+ MaxCardinalitySearch
   164 		+ MinimalCut in UGraph
   165 		+ Tabu Search framework 
   166 		+ Minimum Cost Arborescence algorithm 
   167 		+ Edmonds-Karp MaxFlow
   168 		+ Hao-Orlin algorithm
   169 		+ eps.h: A simple tool to create .eps pictures.
   170 	Backward incompatibilities/changed namings:
   171 		* UndirXyz -> UXyz
   172 		* UNDIRGRAPH_TYPEDEFS -> UGRAPH_TYPEDEFS
   173 		* GridGraph -> GridUGraph
   174 		* LinearHeap -> BucketHeap
   175 		* ColorSet -> Palette
   176 		* xy -> dim2::Point
   177 		* DirPath -> Path
   178 		* concept -> concepts (namespace & directory)
   179 		* LpSolverBase
   180 			* ColName() -> colName
   181 			* Coeff() -> coeff()
   182 		* MinCostFlow -> SspMinCostFlow
   183 	Repository reorganization:
   184 		* compilation is conducted by a single makefile
   185 		* internal building blocks are now in a separate directory
   186 		(lemon/bits)
   187 	Major improvements of many algorithms and data structures
   188 	Several bugfixes
   189 	Compatibility issues:
   190 		* known to compile with
   191 			* GCC 3.3, 3.4, 4.0, 4.1 
   192 			* MinGW, MinGW32
   193 			* Intel C++ 9.x support
   194 
   195 2006-02-03  Version 0.5 Released
   196 	New features
   197 		+ Shortest paths algorithms
   198 			* bellman_ford.h
   199 			* floyd_warshall.h
   200 			* johnson.h
   201 		+ Euler tour iterator for directed and undirected graphs
   202 		+ Other algorithms:
   203 			* dag_shortest_path.h
   204 			* fredman_tarjan.h and prim.h for min cost trees
   205 		+ Bipartite graph concept and implementations
   206 		+ Graph maps:
   207 			* template assign operator
   208 			* specialized iterable bool map
   209 			* potential difference map
   210 			* NodeMatrixMap -- Matrix over the nodes
   211 		+ Maps:
   212 			* IterableIntMap
   213 		+ Tools:
   214 			* Timer can be stop()ed and (re)start()ed
   215 			* radix sort algorithm
   216 			* tolerance.h for working with imprecise numbers
   217 	New demos, benchmarks and tools
   218 		+ graph_orientation.cc: A thoroughly documented demo application
   219 		+ runningTimeTest(): a tool to measure running times more precisely
   220 		+ Demo for topology
   221 		+ counter.h: a tool to measure the number of steps of algorithms
   222 		+ Some useful scripts: check-compiler, check-integrity
   223 	Improvements
   224 		+ Bfs/Dfs/Dijkstra
   225 			* query functions for the next node/edge to be processed
   226 			* visitor interface for dfs
   227 		+ topology.h: small functions for discovering graph topology
   228 			* connected components, strongly connected components
   229 			* bipartiteness testing
   230 		+ GUI:
   231 			* NewMap window in MapSelector
   232 			* Algorithm window and some algorithms (eg. Kruskal) added
   233 		+ LemonReader:
   234 			* exception on non-existent files
   235 		+ LP interface:
   236 			* (Dual)Expr::simplify(double tolerance) added
   237 			* getDual()
   238 		+ GraphToEps:
   239 			* negateY() opt
   240 			* male/female node shapes :)
   241 			* correct %%BoundingBox handling
   242 	Backward incompatibilities/changed namings:
   243 		* Access functions of TimeStamp/Timer
   244 		* Undirected graph interface: findUEdge, ConUEdgeIt
   245 		* pred -> predEdge renaming in search algorithms
   246 		* SnapShot -> Snapshot in {List,Smart}Graph
   247 		* NewEdgeSetAdaptor -> ListEdgeSet
   248 		* LP: set{Obj,Row,Col}() -> {obj,row,col}()
   249 		* "label" instead of "id" inside the LGF files
   250 		* UndirGraph -> UGraph, UndirEdge* -> UEdge*
   251 		* BipartiteGraph -> BpGraph, Lower/UpperNode* -> A/BNode*
   252 	Bugfixes in
   253 		* DFS
   254 		* Preflow
   255 		* x86_64 connected bugfixes (lemon_reader.h)
   256 		* lp.h
   257 	Other changes
   258 		* Demos and benchmarks are not built by default now. They can be
   259 			* enabled with the --enable-demo and --enable-benchmark
   260 			* configure flags.
   261 		* GCC 4.0.3 and ICC 9.0 compatibility
   262 
   263 2005-08-27  Version 0.4 Released
   264 	New features
   265 		+ More and better graph I/O functionalities
   266 		+ High level uniform LP solver interface to CPLEX and GLKP
   267 		+ New map adaptors
   268 		+ New convenience maps
   269 			* IdMap, DescriptorMap
   270 			* InDegMap, OutDegMap
   271 			* XMap, YMap
   272 		+ Default graph maps are iterable
   273 		+ glemon: a graph editor
   274 		+ Some new demo codes added, the old ones got polished.
   275 	Improvements
   276 		+ graphToEps()
   277 			* Automatic node size and edge width scaling
   278 			* Simple color palette tool (ColorSet)
   279 		+ Bfs/Dfs/Dijkstra
   280 			* Step-by-step execution
   281 			* Run from multiple sources
   282 			* Used define stop condition
   283 			* Improved "named parameters"
   284 		+ Preflow
   285 			* Changed interface
   286 			* Function type interface
   287 		+ ListGraph/SmartGraph
   288 			* split() splits a node
   289 			* SnapShot
   290 	Changes
   291 		* Changed namings:
   292 			* Wrapper -> Adaptor
   293 			* kruskalEdgeMap() -> kruskal()
   294 			* kruskalEdgeMap_IteratorOut() -> kruskal()
   295 		* BoundingBox<>
   296 			* operator+=() -> add()
   297 			+ clear()
   298 		* Better documentation
   299 		* Several important bugfixes
   300 		* Now LEMON should compile without warnings with
   301 			* gcc 3.3, 3.4, 4.0
   302 			* Intel C++ Compiler v9.0 
   303 
   304 2005-03-19  Version 0.3.1 Released
   305 	This release fixes a compilation failure bug under cygwin. 
   306 
   307 2005-02-21  Version 0.3 released
   308 	New features
   309 		+ Standardized LEMON exceptions
   310 		+ Undirected Graph
   311 		+ Standard graph file format, input and output classes for it
   312 		+ GraphToEps: A simple graph drawer
   313 	Changes
   314 		* Redesigned Graph infrastructures
   315 		* head() -> target(), tail() -> source()
   316 		* Some standard namings have changes:
   317 			ValueType -> Value, 
   318 			KeyType -> Key,
   319 			ReferenceType -> Reference,
   320 			PointerType -> Pointer
   321 		* Better documentation
   322 
   323 2004-09-30  Version 0.2 released