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