lemon-0.x: NEWS@d239741cfd44

     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

   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

   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

   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

   304 2005-03-19  Version 0.3.1 Released

   305 	This release fixes a compilation failure bug under cygwin.

   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

   323 2004-09-30  Version 0.2 released

author	kpeter
	Thu, 13 Nov 2008 16:17:50 +0000
changeset 2630	d239741cfd44
parent 2606	710c714a7dd3
permissions	-rw-r--r--