|
alpar@2278
|
1 |
2006-10-31 Version 0.6 Released
|
|
alpar@2278
|
2 |
* New Features
|
|
alpar@2278
|
3 |
- Mixed Integer Programming (MIP) support
|
|
alpar@2278
|
4 |
- interface to GLPK and CPLEX MIP solvers
|
|
alpar@2278
|
5 |
- Data structures
|
|
alpar@2278
|
6 |
- Bipatrite graph concepts and implementations
|
|
alpar@2278
|
7 |
- a Polinomial template class
|
|
alpar@2278
|
8 |
- RefPtr: a reference counted pointer class
|
|
alpar@2278
|
9 |
- SimpleBucketHeap
|
|
alpar@2278
|
10 |
- random.h: Mersenne Twister random number generator
|
|
alpar@2278
|
11 |
- EdgeLookUp and AllEdgeLookUp
|
|
alpar@2278
|
12 |
- Tools to find edges between to nodes in time O(log d)
|
|
alpar@2278
|
13 |
- new matching algorithms
|
|
alpar@2278
|
14 |
- Bipartite Graph Max Cardinality Matching (Hopcroft-Karp)
|
|
alpar@2278
|
15 |
- MaxWeightedBipartiteMatching
|
|
alpar@2278
|
16 |
- MinCostMaxBipartiteMatching
|
|
alpar@2278
|
17 |
- MaxCardinalitySearch
|
|
alpar@2278
|
18 |
- MinimalCut in UGraph
|
|
alpar@2278
|
19 |
- Tabu Search framework
|
|
alpar@2278
|
20 |
- Minimum Cost Arborescence algorithm
|
|
alpar@2278
|
21 |
- Edmonds-Karp MaxFlow
|
|
alpar@2278
|
22 |
- Hao-Orlin algorithm
|
|
alpar@2278
|
23 |
- eps.h: A simple tool to create .eps pictures.
|
|
alpar@2278
|
24 |
* Backward incompatibilities/changed namings:
|
|
alpar@2278
|
25 |
- UndirXyz -> UXyz
|
|
alpar@2278
|
26 |
- UNDIRGRAPH_TYPEDEFS -> UGRAPH_TYPEDEFS
|
|
alpar@2278
|
27 |
- GridGraph -> GridUGraph
|
|
alpar@2278
|
28 |
- LinearHeap -> BucketHeap
|
|
alpar@2278
|
29 |
- ColorSet -> Palette
|
|
alpar@2278
|
30 |
- xy -> dim2::Point
|
|
alpar@2278
|
31 |
- DirPath -> Path
|
|
alpar@2278
|
32 |
- concept -> concepts (namespace & directory)
|
|
alpar@2278
|
33 |
- LpSolverBase
|
|
alpar@2278
|
34 |
- ColName() -> colName
|
|
alpar@2278
|
35 |
- Coeff() -> coeff()
|
|
alpar@2278
|
36 |
- MinCostFlow -> SspMinCostFlow
|
|
alpar@2278
|
37 |
* Repository reorganization:
|
|
alpar@2278
|
38 |
- glemon has moved to an separate repository
|
|
alpar@2278
|
39 |
- compilation is conducted by a single makefile
|
|
alpar@2278
|
40 |
- internal building blocks are now in a separate directory
|
|
alpar@2278
|
41 |
(lemon/bits)
|
|
alpar@2278
|
42 |
* Major improvements many algorithms and data structures.
|
|
alpar@2278
|
43 |
* Several bugfixes
|
|
alpar@2278
|
44 |
* Compatibility issues:
|
|
alpar@2278
|
45 |
- known to compile with
|
|
alpar@2278
|
46 |
- GCC 3.3, 3.4, 4.0, 4.1
|
|
alpar@2278
|
47 |
- MinGW, MinGW32
|
|
alpar@2278
|
48 |
- Intel C++ 9.x support
|
|
hegyi@2265
|
49 |
|
|
athos@2075
|
50 |
2006-02-03 Version 0.5 Released
|
|
klao@1945
|
51 |
* New features:
|
|
klao@1945
|
52 |
- Bfs/Dfs/Dijkstra
|
|
klao@1945
|
53 |
+ query functions for the next node/edge to be processed
|
|
klao@1945
|
54 |
+ visitor interface for dfs
|
|
klao@1945
|
55 |
- topology.h: small functions for discovering graph topology
|
|
klao@1945
|
56 |
+ connected components, strongly connected components
|
|
klao@1945
|
57 |
+ bipartiteness testing
|
|
klao@1945
|
58 |
- Shortest paths algorithms:
|
|
klao@1945
|
59 |
bellman_ford.h, floyd_warshall.h, johnson.h
|
|
klao@1945
|
60 |
- Euler tour iterator for directed and undirected graphs
|
|
klao@1945
|
61 |
- Other algorithms:
|
|
klao@1945
|
62 |
+ dag_shortest_path.h
|
|
klao@1945
|
63 |
+ fredman_tarjan.h and prim.h for min cost trees
|
|
klao@1945
|
64 |
- Bipartite graph concept and implementations
|
|
klao@1945
|
65 |
- Graph maps:
|
|
klao@1945
|
66 |
+ template assign operator
|
|
klao@1945
|
67 |
+ specialized iterable bool map
|
|
athos@2075
|
68 |
+ potential difference map
|
|
klao@1945
|
69 |
+ NodeMatrixMap -- Matrix over the nodes
|
|
klao@1945
|
70 |
- Maps:
|
|
klao@1945
|
71 |
+ IterableIntMap
|
|
klao@1945
|
72 |
- GUI:
|
|
klao@1945
|
73 |
+ NewMap window in MapSelector
|
|
klao@1945
|
74 |
+ Algorithm window and some algorithms (eg. Kruskal) added
|
|
klao@1945
|
75 |
- LemonReader:
|
|
klao@1945
|
76 |
+ exception on non-existent files
|
|
klao@1945
|
77 |
- LP interface:
|
|
klao@1945
|
78 |
+ (Dual)Expr::simplify(double tolerance) added
|
|
klao@1945
|
79 |
+ getDual()
|
|
klao@1945
|
80 |
- GraphToEps:
|
|
klao@1945
|
81 |
+ negateY() opt
|
|
klao@1945
|
82 |
+ male/female node shapes :)
|
|
alpar@1947
|
83 |
+ correct %%BoundingBox handling
|
|
klao@1945
|
84 |
- Tools:
|
|
klao@1945
|
85 |
+ Timer can be stop()ed and (re)start()ed
|
|
alpar@1947
|
86 |
+ radix sort algorithm
|
|
klao@1945
|
87 |
+ tolerance.h for working with imprecise numbers
|
|
alpar@1947
|
88 |
* Backward incompatibilities/changed namings:
|
|
alpar@1713
|
89 |
- Access functions of TimeStamp/Timer
|
|
alpar@1947
|
90 |
- Undir graph interface: findUEdge, ConUEdgeIt
|
|
klao@1945
|
91 |
- pred -> predEdge renaming in search algorithms
|
|
klao@1945
|
92 |
- SnapShot -> Snapshot in {List,Smart}Graph
|
|
klao@1945
|
93 |
- NewEdgeSetAdaptor -> ListEdgeSet
|
|
klao@1945
|
94 |
- LP: set{Obj,Row,Col}() -> {obj,row,col}()
|
|
klao@1945
|
95 |
- "label" instead of "id" inside the LGF files
|
|
klao@1945
|
96 |
- UndirGraph -> UGraph, UndirEdge* -> UEdge*
|
|
klao@1945
|
97 |
- BipartiteGraph -> BpGraph, Lower/UpperNode* -> A/BNode*
|
|
athos@2075
|
98 |
* Bugfixes in
|
|
alpar@1668
|
99 |
- DFS
|
|
alpar@1668
|
100 |
- Preflow
|
|
klao@1945
|
101 |
- x86_64 connected bugfixes (lemon_reader.h)
|
|
klao@1945
|
102 |
- lp.h
|
|
klao@1945
|
103 |
* New demos, benchmarks and tools:
|
|
klao@1945
|
104 |
- graph_orientation.cc: A thoroughly documented demo application
|
|
klao@1945
|
105 |
- runningTimeTest(): a tool to measure running times more precisely
|
|
klao@1945
|
106 |
- Demo for topology
|
|
athos@2075
|
107 |
- counter.h: a tool to measure the number of steps of algorithms
|
|
klao@1945
|
108 |
- Some useful scripts: check-compiler, check-integrity
|
|
klao@1945
|
109 |
* Other changes:
|
|
klao@1945
|
110 |
- Demos and benchmarks are not built by default now. They can be
|
|
klao@1945
|
111 |
enabled with the --enable-demo and --enable-benchmark
|
|
klao@1945
|
112 |
configure flags.
|
|
klao@1945
|
113 |
- GCC 4.0.3 and ICC 9.0 compatibility
|
|
alpar@1713
|
114 |
|
|
alpar@1668
|
115 |
2005-08-27 Version 0.4 Released
|
|
alpar@1668
|
116 |
* List of new features and changes
|
|
alpar@1713
|
117 |
* Changed namings:
|
|
alpar@1668
|
118 |
Wrapper -> Adaptor
|
|
alpar@1668
|
119 |
kruskalEdgeMap() -> kruskal()
|
|
alpar@1668
|
120 |
kruskalEdgeMap_IteratorOut() -> kruskal()
|
|
alpar@1668
|
121 |
* BoundinBox<>
|
|
alpar@1668
|
122 |
* operator+=() -> add()
|
|
alpar@1668
|
123 |
+ clear()
|
|
alpar@1668
|
124 |
+ More and better graph I/O functionalities
|
|
alpar@1668
|
125 |
+ High level uniform LP solver interface to CPLEX and GLKP
|
|
alpar@1668
|
126 |
* graphToEps()
|
|
alpar@1668
|
127 |
+ Automatic node size and edge width scaling
|
|
alpar@1668
|
128 |
+ Simple color palette tool (ColorSet)
|
|
alpar@1668
|
129 |
* Bfs/Dfs/Dijkstra
|
|
alpar@1668
|
130 |
+ Step-by-step execution
|
|
alpar@1668
|
131 |
+ Run from multiple sources
|
|
alpar@1668
|
132 |
+ Used define stop condition
|
|
alpar@1668
|
133 |
+ Improved "named parameters"
|
|
alpar@1668
|
134 |
* Preflow
|
|
alpar@1668
|
135 |
+ Function type interface
|
|
alpar@1668
|
136 |
+ Changed interface
|
|
alpar@1668
|
137 |
* ListGraph/SmarGraph
|
|
ladanyi@1670
|
138 |
+ split() splits a node
|
|
alpar@1668
|
139 |
+ SnapShot
|
|
alpar@1668
|
140 |
+ New map adaptors
|
|
ladanyi@1670
|
141 |
+ New convenience maps
|
|
alpar@1668
|
142 |
+ IdMap, DescriptorMap
|
|
alpar@1668
|
143 |
+ InDegMap, OutDegMap
|
|
alpar@1668
|
144 |
+ XMap, YMap
|
|
alpar@1668
|
145 |
+ Default graph maps are iterable
|
|
alpar@1668
|
146 |
+ glemon: a graph editor
|
|
alpar@1668
|
147 |
+ Some new demo codes added, the old ones got polished.
|
|
alpar@1668
|
148 |
* Better documentation
|
|
alpar@1668
|
149 |
* Several important bugfixes
|
|
alpar@1668
|
150 |
* Now lemon should compile without warnings with
|
|
alpar@1668
|
151 |
* gcc 3.3, 3.4, 4.0
|
|
alpar@1668
|
152 |
* Intel C++ Compiler v9.0
|
|
alpar@1668
|
153 |
|
|
alpar@1668
|
154 |
2005-03-19 Version 0.3.1 Released
|
|
alpar@1668
|
155 |
* This release fixes a compilation failure bug under cygwin.
|
|
alpar@1668
|
156 |
|
|
alpar@1668
|
157 |
2005-02-21 Version 0.3 released
|
|
alpar@1668
|
158 |
* List of new features and changes
|
|
alpar@1668
|
159 |
* Redesigned Graph infrastructures
|
|
alpar@1668
|
160 |
+ Standardized LEMON exceptions
|
|
alpar@1668
|
161 |
+ Undirected Graph
|
|
alpar@1668
|
162 |
+ Standard graph file format, input and output classes for it.
|
|
alpar@1668
|
163 |
* head() -> target(), tail() -> source()
|
|
alpar@1668
|
164 |
* Some standard namings have changes:
|
|
alpar@1668
|
165 |
ValueType -> Value,
|
|
alpar@1668
|
166 |
KeyType -> Key,
|
|
alpar@1668
|
167 |
ReferenceType ->Reference,
|
|
alpar@1668
|
168 |
PointerType -> Pointer
|
|
alpar@1668
|
169 |
+ GraphToEps: A simple graph drawer
|
|
alpar@1668
|
170 |
* Better documentation
|
|
alpar@1668
|
171 |
|
|
alpar@1668
|
172 |
2004-09-30 Version 0.2 released
|
|
alpar@1668
|
173 |
|