1 2006-10-27 Version 0.6 Released |
1 2006-10-31 Version 0.6 Released |
2 |
2 * New Features |
3 #Renamed: |
3 - Mixed Integer Programming (MIP) support |
4 *Undir -> U |
4 - interface to GLPK and CPLEX MIP solvers |
5 *Minimum -> Min |
5 - Data structures |
6 *Work -> Aux |
6 - Bipatrite graph concepts and implementations |
7 *UGraphExtender -> UndirectGraphExtender |
7 - a Polinomial template class |
8 -UGraphExtenders with changed meaning |
8 - RefPtr: a reference counted pointer class |
9 *GridGraph -> GridUGraph |
9 - SimpleBucketHeap |
10 *UNDIRGRAPH_TYPEDEFS -> UGRAPH_TYPEDEFS |
10 - random.h: Mersenne Twister random number generator |
11 *LinearHeap -> BucketHeap |
11 - EdgeLookUp and AllEdgeLookUp |
12 *UGraphBaseExtender -> UndirGraphExtender |
12 - Tools to find edges between to nodes in time O(log d) |
13 *BpUGraphBaseExtender merged into BpUGraphExtender |
13 - new matching algorithms |
14 *StaticGraph to Graph |
14 - Bipartite Graph Max Cardinality Matching (Hopcroft-Karp) |
15 *ColorSet to Palette |
15 - MaxWeightedBipartiteMatching |
16 *xy -> dim2::Point |
16 - MinCostMaxBipartiteMatching |
17 *DirPath to Path |
17 - MaxCardinalitySearch |
18 *concept -> concepts (namespace & directory) |
18 - MinimalCut in UGraph |
19 |
19 - Tabu Search framework |
20 #Reorganized: |
20 - Minimum Cost Arborescence algorithm |
21 *bootstrap: quiet option |
21 - Edmonds-Karp MaxFlow |
22 *utility, invalid and traits moved to bits |
22 - Hao-Orlin algorithm |
23 *section readers moved to own group |
23 - eps.h: A simple tool to create .eps pictures. |
24 *separate group for matrices |
24 * Backward incompatibilities/changed namings: |
25 *single makefile |
25 - UndirXyz -> UXyz |
26 *glemon is moved to own repository |
26 - UNDIRGRAPH_TYPEDEFS -> UGRAPH_TYPEDEFS |
27 *graph_component.h -> graph_components.h |
27 - GridGraph -> GridUGraph |
28 *reference to modules added |
28 - LinearHeap -> BucketHeap |
29 *disable assertions in default behaviour |
29 - ColorSet -> Palette |
30 *BiVariant moved to lemon/bits/variant.h |
30 - xy -> dim2::Point |
31 *using abort() instead of exit(1) |
31 - DirPath -> Path |
32 |
32 - concept -> concepts (namespace & directory) |
33 #Taken out: |
33 - LpSolverBase |
34 *SplitGraph is temporarly deleted |
34 - ColName() -> colName |
35 *SubBidirGraphAdaptor |
35 - Coeff() -> coeff() |
36 *obsolote "id" map handling |
36 - MinCostFlow -> SspMinCostFlow |
37 *concepts for extendable and erasable graphs |
37 * Repository reorganization: |
38 *exceptionName() |
38 - glemon has moved to an separate repository |
39 *bezier.h |
39 - compilation is conducted by a single makefile |
40 *functional interfaces |
40 - internal building blocks are now in a separate directory |
41 *UPath |
41 (lemon/bits) |
42 |
42 * Major improvements many algorithms and data structures. |
43 #Rewritten, modificated, improved |
43 * Several bugfixes |
44 *UnionFindEnum revision |
44 * Compatibility issues: |
45 *countItems |
45 - known to compile with |
46 *findEdges |
46 - GCC 3.3, 3.4, 4.0, 4.1 |
47 *IncEdgeIt goes through on loop edges twice. |
47 - MinGW, MinGW32 |
48 *mining of the clear in heaps |
48 - Intel C++ 9.x support |
49 *SplitGraphAdaptor |
|
50 *item sets are written in the order sorted by the labels |
|
51 *make explicit constructors |
|
52 *snapshot |
|
53 -rewritten |
|
54 -implemented for SmartUGraph an SmartBpUGraph |
|
55 *Node/Edge::operator<() is required by the concept |
|
56 *Graph Component concepts |
|
57 *disabled the copy constructor and operator- of {List|Smart}[U]Graph. |
|
58 *modificated interface: colType() functions |
|
59 *made public what() in NodeSetError |
|
60 *improvment in exception handling |
|
61 -exception safe erase and clear handler |
|
62 -proper exception handling in the SmartEdgeSet |
|
63 -rethrow of exception missing |
|
64 *signaling alterations in BpUGraphs |
|
65 *UnionFind |
|
66 -takes less space |
|
67 -UnionFindEnum |
|
68 -changed interface |
|
69 *updated the Path concept |
|
70 *item readers and writers |
|
71 |
|
72 #New |
|
73 *functor usage for writeable map adaptors |
|
74 *MIP support |
|
75 -interface to the cplex MIP solver |
|
76 *data structures |
|
77 -ListBpUGraph |
|
78 -SmartEdgeset |
|
79 -RefPtr: a reference counted pointer class |
|
80 -two state variant |
|
81 -Polinomial template class |
|
82 -SimpleBucketHeap |
|
83 -even a smaller version |
|
84 -tolerance class |
|
85 -Tolerance<unsigned int> and Tolerance<unsigned long long int> added |
|
86 -the extender system |
|
87 -some UGraphExtender /SubUGraphExtenders, DirectUGraphExtender/ |
|
88 -adaptor related |
|
89 -ResGraphAdaptor with Tolerance |
|
90 -SwapBpUGraphAdaptor which swaps the two nodeset of the bipartite graph |
|
91 -map related |
|
92 -SimpleMap and SimpleWriteMap |
|
93 -new map type based on array map for debugging purpose |
|
94 -DynamicAsymMatrixMap |
|
95 -MatrixMapTraits |
|
96 *functions |
|
97 -optimality test on random graph |
|
98 -implementation of the drand48 functions |
|
99 -negative cycle to path converter |
|
100 -reserveNode function |
|
101 -Mersenne Twister random number generator |
|
102 -EdgeLookUp and AllEdgeLookUp |
|
103 *scripts |
|
104 -script that lists all the header files included directly or indirectly by a certain header file |
|
105 -script creates/updates the copyright header of a source file |
|
106 *algorithms |
|
107 -algorithm group for matchings |
|
108 -Bipartite Graph Max Cardinality Matching (Hopcroft-Karp) |
|
109 -MaxWeightedBipartiteMatching |
|
110 -MinCostMaxBipartiteMatching |
|
111 -MaxCardinalitySearch |
|
112 -MinimalCut in UGraph |
|
113 -tabu search |
|
114 -Minimum Cost Arborescence algorithm |
|
115 -dual solution computation and interface for algorithm |
|
116 -Edmonds-Karp MaxFlow |
|
117 -Hao-Orlin algorithm |
|
118 |
|
119 #Progress in already existing objects: |
|
120 *radix sort to ansi compatible |
|
121 *map creation based on virtual base class is possible |
|
122 *default constructor which allocates empty graphs |
|
123 *defaultMap is introdouced, graph maps should not be inherited from the ObserverBase. |
|
124 *clarifing alteration observing system |
|
125 *resize for static size graph |
|
126 *an additional simplier interface for static size graphs. |
|
127 *Node operator()(int) for getting node by index |
|
128 *int index(Node node) for getting index by node |
|
129 *traits for alteration notifiers |
|
130 *graph adadptors can be alteration observed |
|
131 *count ANodes-BNodes in bipartite graphs |
|
132 *the template assign operators and map iterators can be used for adaptors also |
|
133 *writeable extension of some maps |
|
134 *rot180() added to xy.h |
|
135 *change source and target for the bipartite list graph |
|
136 *findEdge extension also for the BpUGraphs |
|
137 *proper handling of loop edges in the UGraph::findUEdge |
|
138 *exported interface to the Graph class |
|
139 *new random interface |
|
140 *graph imlementations actually provide ReferenceMaps |
|
141 *lgf2ps: |
|
142 -RGB color related stuff is in color.h now |
|
143 -simple class to create .eps figures (eps.h) |
|
144 -"Node shapes" added |
|
145 -some color constants added (BLACK, WHITE, RED etc) |
|
146 -absolute/relative node size/link width scaling |
|
147 |
|
148 #Compatibility issues: |
|
149 *compilation with G++ -ansi |
|
150 *gcc-4.1 |
|
151 *NaN checking to be conform to MinGW32 |
|
152 *MinGW, MinGW32 |
|
153 *long long just for gnu compilers |
|
154 *CPLEX 9.x support |
|
155 *turned off 32bit specific tests. |
|
156 |
|
157 #Beyond the aboves several bugfix and documentation improvement is made, new demos, benchmarks are implemented. |
|
158 |
49 |
159 2006-02-03 Version 0.5 Released |
50 2006-02-03 Version 0.5 Released |
160 * New features: |
51 * New features: |
161 - Bfs/Dfs/Dijkstra |
52 - Bfs/Dfs/Dijkstra |
162 + query functions for the next node/edge to be processed |
53 + query functions for the next node/edge to be processed |