alpar@2391
|
1 |
/* -*- C++ -*-
|
alpar@2391
|
2 |
*
|
alpar@2391
|
3 |
* This file is a part of LEMON, a generic C++ optimization library
|
alpar@2391
|
4 |
*
|
alpar@2553
|
5 |
* Copyright (C) 2003-2008
|
alpar@2391
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
alpar@2391
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
alpar@2391
|
8 |
*
|
alpar@2391
|
9 |
* Permission to use, modify and distribute this software is granted
|
alpar@2391
|
10 |
* provided that this copyright notice appears in all copies. For
|
alpar@2391
|
11 |
* precise terms see the accompanying LICENSE file.
|
alpar@2391
|
12 |
*
|
alpar@2391
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
alpar@2391
|
14 |
* express or implied, and with no claim as to its suitability for any
|
alpar@2391
|
15 |
* purpose.
|
alpar@2391
|
16 |
*
|
alpar@2391
|
17 |
*/
|
alpar@814
|
18 |
|
alpar@678
|
19 |
/**
|
alpar@678
|
20 |
@defgroup datas Data Structures
|
alpar@921
|
21 |
This group describes the several graph structures implemented in LEMON.
|
alpar@678
|
22 |
*/
|
alpar@430
|
23 |
|
alpar@678
|
24 |
/**
|
alpar@678
|
25 |
@defgroup graphs Graph Structures
|
alpar@678
|
26 |
@ingroup datas
|
alpar@921
|
27 |
\brief Graph structures implemented in LEMON.
|
alpar@430
|
28 |
|
marci@1172
|
29 |
The implementation of combinatorial algorithms heavily relies on
|
marci@1172
|
30 |
efficient graph implementations. LEMON offers data structures which are
|
marci@1172
|
31 |
planned to be easily used in an experimental phase of implementation studies,
|
marci@1172
|
32 |
and thereafter the program code can be made efficient by small modifications.
|
alpar@430
|
33 |
|
deba@2084
|
34 |
The most efficient implementation of diverse applications require the
|
deba@2084
|
35 |
usage of different physical graph implementations. These differences
|
deba@2084
|
36 |
appear in the size of graph we require to handle, memory or time usage
|
deba@2084
|
37 |
limitations or in the set of operations through which the graph can be
|
deba@2084
|
38 |
accessed. LEMON provides several physical graph structures to meet
|
deba@2084
|
39 |
the diverging requirements of the possible users. In order to save on
|
deba@2084
|
40 |
running time or on memory usage, some structures may fail to provide
|
deba@2084
|
41 |
some graph features like edge or node deletion.
|
marci@1172
|
42 |
|
marci@1172
|
43 |
Alteration of standard containers need a very limited number of
|
marci@1172
|
44 |
operations, these together satisfy the everyday requirements.
|
alpar@2117
|
45 |
In the case of graph structures, different operations are needed which do
|
alpar@2006
|
46 |
not alter the physical graph, but gives another view. If some nodes or
|
marci@1172
|
47 |
edges have to be hidden or the reverse oriented graph have to be used, then
|
alpar@2117
|
48 |
this is the case. It also may happen that in a flow implementation
|
alpar@2006
|
49 |
the residual graph can be accessed by another algorithm, or a node-set
|
alpar@2006
|
50 |
is to be shrunk for another algorithm.
|
marci@1172
|
51 |
LEMON also provides a variety of graphs for these requirements called
|
alpar@1401
|
52 |
\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
|
marci@1172
|
53 |
in conjunction with other graph representation.
|
alpar@430
|
54 |
|
alpar@678
|
55 |
You are free to use the graph structure that fit your requirements
|
alpar@678
|
56 |
the best, most graph algorithms and auxiliary data structures can be used
|
marci@1172
|
57 |
with any graph structures.
|
alpar@678
|
58 |
*/
|
alpar@430
|
59 |
|
alpar@678
|
60 |
/**
|
deba@1866
|
61 |
@defgroup semi_adaptors Semi-Adaptors Classes for Graphs
|
deba@1866
|
62 |
@ingroup graphs
|
deba@1866
|
63 |
\brief Graph types between real graphs and graph adaptors.
|
deba@1866
|
64 |
|
alpar@2117
|
65 |
Graph types between real graphs and graph adaptors. These classes wrap
|
alpar@2117
|
66 |
graphs to give new functionality as the adaptors do it. On the other
|
alpar@2117
|
67 |
hand they are not light-weight structures as the adaptors.
|
deba@1866
|
68 |
*/
|
deba@1866
|
69 |
|
deba@1866
|
70 |
/**
|
alpar@1043
|
71 |
@defgroup maps Maps
|
alpar@1043
|
72 |
@ingroup datas
|
alpar@1043
|
73 |
\brief Some special purpose map to make life easier.
|
alpar@1043
|
74 |
|
alpar@1043
|
75 |
LEMON provides several special maps that e.g. combine
|
alpar@1043
|
76 |
new maps from existing ones.
|
alpar@1043
|
77 |
*/
|
alpar@1043
|
78 |
|
alpar@1402
|
79 |
/**
|
alpar@1402
|
80 |
@defgroup graph_maps Graph Maps
|
alpar@1402
|
81 |
@ingroup maps
|
alpar@1402
|
82 |
\brief Special Graph-Related Maps.
|
alpar@1402
|
83 |
|
alpar@1402
|
84 |
These maps are specifically designed to assign values to the nodes and edges of
|
alpar@1402
|
85 |
graphs.
|
alpar@1402
|
86 |
*/
|
alpar@1402
|
87 |
|
alpar@1402
|
88 |
|
alpar@1402
|
89 |
/**
|
alpar@1402
|
90 |
\defgroup map_adaptors Map Adaptors
|
alpar@1402
|
91 |
\ingroup maps
|
alpar@1402
|
92 |
\brief Tools to create new maps from existing ones
|
alpar@1402
|
93 |
|
alpar@1402
|
94 |
Map adaptors are used to create "implicit" maps from other maps.
|
alpar@1402
|
95 |
|
alpar@2260
|
96 |
Most of them are \ref lemon::concepts::ReadMap "ReadMap"s. They can
|
alpar@2117
|
97 |
make arithmetic operations between one or two maps (negation, scaling,
|
alpar@1402
|
98 |
addition, multiplication etc.) or e.g. convert a map to another one
|
alpar@1402
|
99 |
of different Value type.
|
deba@2489
|
100 |
|
deba@2489
|
101 |
The typical usage of this classes is the passing implicit maps to
|
deba@2489
|
102 |
algorithms. If a function type algorithm is called then the function
|
deba@2489
|
103 |
type map adaptors can be used comfortable. For example let's see the
|
deba@2489
|
104 |
usage of map adaptors with the \c graphToEps() function:
|
deba@2489
|
105 |
\code
|
deba@2489
|
106 |
Color nodeColor(int deg) {
|
deba@2489
|
107 |
if (deg >= 2) {
|
deba@2489
|
108 |
return Color(0.5, 0.0, 0.5);
|
deba@2489
|
109 |
} else if (deg == 1) {
|
deba@2489
|
110 |
return Color(1.0, 0.5, 1.0);
|
deba@2489
|
111 |
} else {
|
deba@2489
|
112 |
return Color(0.0, 0.0, 0.0);
|
deba@2489
|
113 |
}
|
deba@2489
|
114 |
}
|
deba@2489
|
115 |
|
deba@2489
|
116 |
Graph::NodeMap<int> degree_map(graph);
|
deba@2489
|
117 |
|
deba@2489
|
118 |
graphToEps(graph, "graph.eps")
|
deba@2489
|
119 |
.coords(coords).scaleToA4().undirected()
|
deba@2489
|
120 |
.nodeColors(composeMap(functorMap(nodeColor), degree_map))
|
deba@2489
|
121 |
.run();
|
deba@2489
|
122 |
\endcode
|
deba@2489
|
123 |
The \c functorMap() function makes an \c int to \c Color map from the
|
deba@2489
|
124 |
\e nodeColor() function. The \c composeMap() compose the \e degree_map
|
deba@2489
|
125 |
and the previous created map. The composed map is proper function to
|
deba@2489
|
126 |
get color of each node.
|
deba@2489
|
127 |
|
deba@2489
|
128 |
The usage with class type algorithms is little bit harder. In this
|
deba@2489
|
129 |
case the function type map adaptors can not be used, because the
|
deba@2489
|
130 |
function map adaptors give back temporarly objects.
|
deba@2489
|
131 |
\code
|
deba@2489
|
132 |
Graph graph;
|
deba@2489
|
133 |
|
deba@2489
|
134 |
typedef Graph::EdgeMap<double> DoubleEdgeMap;
|
deba@2489
|
135 |
DoubleEdgeMap length(graph);
|
deba@2489
|
136 |
DoubleEdgeMap speed(graph);
|
deba@2489
|
137 |
|
deba@2489
|
138 |
typedef DivMap<DoubleEdgeMap, DoubleEdgeMap> TimeMap;
|
deba@2489
|
139 |
|
deba@2489
|
140 |
TimeMap time(length, speed);
|
deba@2489
|
141 |
|
deba@2489
|
142 |
Dijkstra<Graph, TimeMap> dijkstra(graph, time);
|
deba@2489
|
143 |
dijkstra.run(source, target);
|
deba@2489
|
144 |
\endcode
|
deba@2489
|
145 |
|
deba@2489
|
146 |
We have a length map and a maximum speed map on a graph. The minimum
|
deba@2489
|
147 |
time to pass the edge can be calculated as the division of the two
|
deba@2489
|
148 |
maps which can be done implicitly with the \c DivMap template
|
deba@2489
|
149 |
class. We use the implicit minimum time map as the length map of the
|
deba@2489
|
150 |
\c Dijkstra algorithm.
|
alpar@1402
|
151 |
*/
|
alpar@1402
|
152 |
|
alpar@1043
|
153 |
/**
|
alpar@2072
|
154 |
@defgroup matrices Matrices
|
alpar@2072
|
155 |
@ingroup datas
|
alpar@2072
|
156 |
\brief Two dimensional data storages.
|
alpar@2072
|
157 |
|
deba@2084
|
158 |
Two dimensional data storages.
|
alpar@2072
|
159 |
*/
|
alpar@2072
|
160 |
|
deba@2084
|
161 |
/**
|
deba@2084
|
162 |
@defgroup paths Path Structures
|
deba@2084
|
163 |
@ingroup datas
|
deba@2084
|
164 |
\brief Path structures implemented in LEMON.
|
deba@2084
|
165 |
|
deba@2084
|
166 |
LEMON provides flexible data structures
|
deba@2084
|
167 |
to work with paths.
|
deba@2084
|
168 |
|
deba@2489
|
169 |
All of them have similar interfaces, and it can be copied easily with
|
deba@2489
|
170 |
assignment operator and copy constructor. This make it easy and
|
deba@2489
|
171 |
efficient to have e.g. the Dijkstra algorithm to store its result in
|
deba@2489
|
172 |
any kind of path structure.
|
deba@2084
|
173 |
|
alpar@2260
|
174 |
\sa lemon::concepts::Path
|
deba@2084
|
175 |
|
deba@2084
|
176 |
*/
|
alpar@2072
|
177 |
|
alpar@2072
|
178 |
/**
|
alpar@678
|
179 |
@defgroup auxdat Auxiliary Data Structures
|
alpar@678
|
180 |
@ingroup datas
|
alpar@921
|
181 |
\brief Some data structures implemented in LEMON.
|
alpar@406
|
182 |
|
alpar@921
|
183 |
This group describes the data structures implemented in LEMON in
|
alpar@678
|
184 |
order to make it easier to implement combinatorial algorithms.
|
alpar@678
|
185 |
*/
|
alpar@406
|
186 |
|
alpar@785
|
187 |
|
alpar@785
|
188 |
/**
|
deba@2084
|
189 |
@defgroup algs Algorithms
|
deba@2084
|
190 |
\brief This group describes the several algorithms
|
alpar@921
|
191 |
implemented in LEMON.
|
alpar@947
|
192 |
|
deba@2084
|
193 |
This group describes the several algorithms
|
alpar@947
|
194 |
implemented in LEMON.
|
alpar@947
|
195 |
*/
|
alpar@947
|
196 |
|
alpar@947
|
197 |
/**
|
deba@2376
|
198 |
@defgroup search Graph Search
|
deba@2084
|
199 |
@ingroup algs
|
deba@2376
|
200 |
\brief This group contains the common graph
|
deba@2376
|
201 |
search algorithms.
|
alpar@947
|
202 |
|
deba@2376
|
203 |
This group contains the common graph
|
deba@2376
|
204 |
search algorithms like Bfs and Dfs.
|
alpar@678
|
205 |
*/
|
alpar@678
|
206 |
|
alpar@678
|
207 |
/**
|
deba@2376
|
208 |
@defgroup shortest_path Shortest Path algorithms
|
deba@2084
|
209 |
@ingroup algs
|
alpar@758
|
210 |
\brief This group describes the algorithms
|
deba@2376
|
211 |
for finding shortest paths.
|
deba@2060
|
212 |
|
deba@2376
|
213 |
This group describes the algorithms for finding shortest paths in
|
deba@2376
|
214 |
graphs.
|
deba@2376
|
215 |
|
deba@2376
|
216 |
*/
|
deba@2376
|
217 |
|
deba@2376
|
218 |
/**
|
deba@2376
|
219 |
@defgroup max_flow Maximum Flow algorithms
|
deba@2376
|
220 |
@ingroup algs
|
deba@2376
|
221 |
\brief This group describes the algorithms for finding maximum flows.
|
deba@2376
|
222 |
|
deba@2377
|
223 |
This group describes the algorithms for finding maximum flows and
|
deba@2377
|
224 |
feasible circulations.
|
deba@2060
|
225 |
|
deba@2514
|
226 |
The maximum flow problem is to find a flow between a single-source and
|
deba@2514
|
227 |
single-target that is maximum. Formally, there is \f$G=(V,A)\f$
|
deba@2514
|
228 |
directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
|
deba@2514
|
229 |
function and given \f$s, t \in V\f$ source and target node. The
|
deba@2514
|
230 |
maximum flow is the solution of the next optimization problem:
|
deba@2514
|
231 |
|
deba@2514
|
232 |
\f[ 0 \le f_a \le c_a \f]
|
deba@2514
|
233 |
\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \quad u \in V \setminus \{s,t\}\f]
|
deba@2514
|
234 |
\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
|
deba@2514
|
235 |
|
deba@2514
|
236 |
The lemon contains several algorithms for solve maximum flow problems:
|
deba@2514
|
237 |
- \ref lemon::EdmondsKarp "Edmonds-Karp"
|
deba@2514
|
238 |
- \ref lemon::Preflow "Goldberg's Preflow algorithm"
|
deba@2514
|
239 |
- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic tree"
|
deba@2514
|
240 |
- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
|
deba@2514
|
241 |
|
deba@2514
|
242 |
In most cases the \ref lemon::Preflow "preflow" algorithm provides the
|
deba@2514
|
243 |
fastest method to compute the maximum flow. All impelementations
|
deba@2514
|
244 |
provides functions for query the minimum cut, which is the dual linear
|
deba@2514
|
245 |
programming probelm of the maximum flow.
|
deba@2514
|
246 |
|
alpar@678
|
247 |
*/
|
alpar@678
|
248 |
|
alpar@678
|
249 |
/**
|
deba@2376
|
250 |
@defgroup min_cost_flow Minimum Cost Flow algorithms
|
deba@2376
|
251 |
@ingroup algs
|
deba@2376
|
252 |
|
deba@2376
|
253 |
\brief This group describes the algorithms
|
deba@2376
|
254 |
for finding minimum cost flows and circulations.
|
deba@2376
|
255 |
|
deba@2376
|
256 |
This group describes the algorithms for finding minimum cost flows and
|
deba@2376
|
257 |
circulations.
|
deba@2376
|
258 |
*/
|
deba@2376
|
259 |
|
deba@2376
|
260 |
/**
|
deba@2530
|
261 |
@defgroup min_cut Minimum Cut algorithms
|
deba@2530
|
262 |
@ingroup algs
|
deba@2376
|
263 |
|
deba@2530
|
264 |
\brief This group describes the algorithms for finding minimum cut in
|
deba@2530
|
265 |
graphs.
|
deba@2530
|
266 |
|
deba@2530
|
267 |
This group describes the algorithms for finding minimum cut in graphs.
|
deba@2530
|
268 |
|
deba@2530
|
269 |
The minimum cut problem is to find a non-empty and non-complete
|
deba@2530
|
270 |
\f$X\f$ subset of the vertices with minimum overall capacity on
|
deba@2530
|
271 |
outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
|
deba@2530
|
272 |
\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
|
deba@2530
|
273 |
cut is the solution of the next optimization problem:
|
deba@2530
|
274 |
|
deba@2530
|
275 |
\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
|
deba@2530
|
276 |
|
deba@2530
|
277 |
The lemon contains several algorithms related to minimum cut problems:
|
deba@2530
|
278 |
|
deba@2530
|
279 |
- \ref lemon::HaoOrlin "Hao-Orlin algorithm" for calculate minimum cut
|
deba@2530
|
280 |
in directed graphs
|
deba@2530
|
281 |
- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
|
deba@2530
|
282 |
calculate minimum cut in undirected graphs
|
deba@2530
|
283 |
- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" for calculate all
|
deba@2530
|
284 |
pairs minimum cut in undirected graphs
|
deba@2530
|
285 |
|
deba@2530
|
286 |
If you want to find minimum cut just between two distinict nodes,
|
deba@2530
|
287 |
please see the \ref max_flow "Maximum Flow page".
|
deba@2530
|
288 |
|
deba@2376
|
289 |
*/
|
deba@2376
|
290 |
|
deba@2376
|
291 |
/**
|
deba@2429
|
292 |
@defgroup graph_prop Connectivity and other graph properties
|
deba@2084
|
293 |
@ingroup algs
|
deba@1750
|
294 |
\brief This group describes the algorithms
|
deba@2429
|
295 |
for discover the graph properties
|
deba@2060
|
296 |
|
deba@2429
|
297 |
This group describes the algorithms for discover the graph properties
|
deba@2429
|
298 |
like connectivity, bipartiteness, euler property, simplicity, etc...
|
deba@2060
|
299 |
|
deba@2060
|
300 |
\image html edge_biconnected_components.png
|
deba@2060
|
301 |
\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
|
deba@1750
|
302 |
*/
|
deba@1750
|
303 |
|
deba@1750
|
304 |
/**
|
deba@2500
|
305 |
@defgroup planar Planarity embedding and drawing
|
deba@2500
|
306 |
@ingroup algs
|
deba@2500
|
307 |
\brief This group contains algorithms for planarity embedding and drawing
|
deba@2500
|
308 |
|
deba@2500
|
309 |
This group contains algorithms for planarity checking, embedding and drawing.
|
deba@2500
|
310 |
|
deba@2500
|
311 |
\image html planar.png
|
deba@2500
|
312 |
\image latex planar.eps "Plane graph" width=\textwidth
|
deba@2500
|
313 |
*/
|
deba@2500
|
314 |
|
deba@2500
|
315 |
/**
|
deba@2376
|
316 |
@defgroup matching Matching algorithms
|
deba@2084
|
317 |
@ingroup algs
|
deba@2042
|
318 |
\brief This group describes the algorithms
|
deba@2042
|
319 |
for find matchings in graphs and bipartite graphs.
|
deba@2060
|
320 |
|
deba@2548
|
321 |
This group provides some algorithm objects and function to calculate
|
deba@2548
|
322 |
matchings in graphs and bipartite graphs. The general matching problem is
|
deba@2548
|
323 |
finding a subset of the edges which does not shares common endpoints.
|
deba@2548
|
324 |
|
deba@2548
|
325 |
There are several different algorithms for calculate matchings in
|
deba@2548
|
326 |
graphs. The matching problems in bipartite graphs are generally
|
deba@2548
|
327 |
easier than in general graphs. The goal of the matching optimization
|
deba@2548
|
328 |
can be the finding maximum cardinality, maximum weight or minimum cost
|
deba@2548
|
329 |
matching. The search can be constrained to find perfect or
|
deba@2548
|
330 |
maximum cardinality matching.
|
deba@2548
|
331 |
|
deba@2548
|
332 |
Lemon contains the next algorithms:
|
deba@2548
|
333 |
- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
|
deba@2548
|
334 |
augmenting path algorithm for calculate maximum cardinality matching in
|
deba@2548
|
335 |
bipartite graphs
|
deba@2548
|
336 |
- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
|
deba@2548
|
337 |
algorithm for calculate maximum cardinality matching in bipartite graphs
|
deba@2548
|
338 |
- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
|
deba@2548
|
339 |
Successive shortest path algorithm for calculate maximum weighted matching
|
deba@2548
|
340 |
and maximum weighted bipartite matching in bipartite graph
|
deba@2548
|
341 |
- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
|
deba@2548
|
342 |
Successive shortest path algorithm for calculate minimum cost maximum
|
deba@2548
|
343 |
matching in bipartite graph
|
deba@2548
|
344 |
- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
|
deba@2548
|
345 |
for calculate maximum cardinality matching in general graph
|
deba@2548
|
346 |
- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
|
deba@2548
|
347 |
shrinking algorithm for calculate maximum weighted matching in general
|
deba@2548
|
348 |
graph
|
deba@2548
|
349 |
- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
|
deba@2548
|
350 |
Edmond's blossom shrinking algorithm for calculate maximum weighted
|
deba@2548
|
351 |
perfect matching in general graph
|
deba@2060
|
352 |
|
deba@2060
|
353 |
\image html bipartite_matching.png
|
deba@2060
|
354 |
\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
|
deba@2060
|
355 |
|
deba@2042
|
356 |
*/
|
deba@2042
|
357 |
|
deba@2042
|
358 |
/**
|
deba@2376
|
359 |
@defgroup spantree Minimum Spanning Tree algorithms
|
deba@2084
|
360 |
@ingroup algs
|
alpar@2117
|
361 |
\brief This group contains the algorithms for finding a minimum cost spanning
|
deba@2084
|
362 |
tree in a graph
|
deba@2084
|
363 |
|
alpar@2117
|
364 |
This group contains the algorithms for finding a minimum cost spanning
|
deba@2084
|
365 |
tree in a graph
|
deba@2084
|
366 |
*/
|
deba@2084
|
367 |
|
deba@2084
|
368 |
|
deba@2084
|
369 |
/**
|
deba@2376
|
370 |
@defgroup auxalg Auxiliary algorithms
|
deba@2084
|
371 |
@ingroup algs
|
deba@2084
|
372 |
\brief Some algorithms implemented in LEMON.
|
deba@2084
|
373 |
|
deba@2084
|
374 |
This group describes the algorithms in LEMON in order to make
|
deba@2084
|
375 |
it easier to implement complex algorithms.
|
deba@2376
|
376 |
*/
|
deba@2084
|
377 |
|
deba@2376
|
378 |
/**
|
deba@2376
|
379 |
@defgroup approx Approximation algorithms
|
deba@2376
|
380 |
\brief Approximation algorithms
|
deba@2376
|
381 |
|
deba@2376
|
382 |
Approximation and heuristic algorithms
|
deba@2084
|
383 |
*/
|
deba@2084
|
384 |
|
deba@2084
|
385 |
/**
|
deba@2084
|
386 |
@defgroup gen_opt_group General Optimization Tools
|
deba@2084
|
387 |
\brief This group describes some general optimization frameworks
|
deba@2084
|
388 |
implemented in LEMON.
|
deba@2084
|
389 |
|
deba@2084
|
390 |
This group describes some general optimization frameworks
|
deba@2084
|
391 |
implemented in LEMON.
|
deba@2084
|
392 |
|
alpar@1151
|
393 |
*/
|
alpar@1151
|
394 |
|
deba@2370
|
395 |
/**
|
deba@2371
|
396 |
@defgroup lp_group Lp and Mip solvers
|
deba@2370
|
397 |
@ingroup gen_opt_group
|
deba@2370
|
398 |
\brief Lp and Mip solver interfaces for LEMON.
|
deba@2370
|
399 |
|
deba@2370
|
400 |
This group describes Lp and Mip solver interfaces for LEMON. The
|
deba@2370
|
401 |
various LP solvers could be used in the same manner with this
|
deba@2370
|
402 |
interface.
|
deba@2370
|
403 |
|
deba@2370
|
404 |
*/
|
deba@2370
|
405 |
|
deba@2368
|
406 |
/**
|
deba@2370
|
407 |
@defgroup lp_utils Tools for Lp and Mip solvers
|
deba@2370
|
408 |
@ingroup lp_group
|
deba@2370
|
409 |
\brief This group adds some helper tools to the Lp and Mip solvers
|
deba@2370
|
410 |
implemented in LEMON.
|
deba@2368
|
411 |
|
deba@2368
|
412 |
This group adds some helper tools to general optimization framework
|
deba@2368
|
413 |
implemented in LEMON.
|
deba@2368
|
414 |
*/
|
deba@2368
|
415 |
|
alpar@1151
|
416 |
/**
|
deba@2370
|
417 |
@defgroup metah Metaheuristics
|
deba@2370
|
418 |
@ingroup gen_opt_group
|
deba@2370
|
419 |
\brief Metaheuristics for LEMON library.
|
deba@2370
|
420 |
|
deba@2370
|
421 |
This group contains some metaheuristic optimization tools.
|
deba@2370
|
422 |
*/
|
deba@2370
|
423 |
|
deba@2370
|
424 |
/**
|
deba@2376
|
425 |
@defgroup utils Tools and Utilities
|
deba@2376
|
426 |
\brief Tools and Utilities for Programming in LEMON
|
deba@2376
|
427 |
|
deba@2376
|
428 |
Tools and Utilities for Programming in LEMON
|
deba@2376
|
429 |
*/
|
deba@2376
|
430 |
|
deba@2376
|
431 |
/**
|
deba@2376
|
432 |
@defgroup gutils Basic Graph Utilities
|
deba@2376
|
433 |
@ingroup utils
|
deba@2376
|
434 |
\brief This group describes some simple basic graph utilities.
|
deba@2376
|
435 |
|
deba@2376
|
436 |
This group describes some simple basic graph utilities.
|
deba@2376
|
437 |
*/
|
deba@2376
|
438 |
|
deba@2376
|
439 |
/**
|
alpar@678
|
440 |
@defgroup misc Miscellaneous Tools
|
deba@2376
|
441 |
@ingroup utils
|
alpar@678
|
442 |
Here you can find several useful tools for development,
|
alpar@678
|
443 |
debugging and testing.
|
alpar@678
|
444 |
*/
|
alpar@678
|
445 |
|
deba@2376
|
446 |
|
alpar@678
|
447 |
/**
|
alpar@1847
|
448 |
@defgroup timecount Time measuring and Counting
|
alpar@1847
|
449 |
@ingroup misc
|
alpar@1847
|
450 |
Here you can find simple tools for measuring the performance
|
alpar@1847
|
451 |
of algorithms.
|
alpar@1847
|
452 |
*/
|
alpar@1847
|
453 |
|
alpar@1847
|
454 |
/**
|
deba@2376
|
455 |
@defgroup graphbits Tools for Graph Implementation
|
deba@2376
|
456 |
@ingroup utils
|
deba@2376
|
457 |
\brief Tools to Make It Easier to Make Graphs.
|
deba@2376
|
458 |
|
deba@2376
|
459 |
This group describes the tools that makes it easier to make graphs and
|
deba@2376
|
460 |
the maps that dynamically update with the graph changes.
|
deba@2376
|
461 |
*/
|
deba@2376
|
462 |
|
deba@2376
|
463 |
/**
|
deba@2376
|
464 |
@defgroup exceptions Exceptions
|
deba@2376
|
465 |
@ingroup utils
|
deba@2376
|
466 |
This group contains the exceptions thrown by LEMON library
|
deba@2376
|
467 |
*/
|
deba@2376
|
468 |
|
deba@2376
|
469 |
/**
|
deba@2016
|
470 |
@defgroup io_group Input-Output
|
deba@2084
|
471 |
\brief Several Graph Input-Output methods
|
deba@2084
|
472 |
|
deba@2084
|
473 |
Here you can find tools for importing and exporting graphs
|
deba@2084
|
474 |
and graph related data. Now it supports the LEMON format, the
|
alpar@2117
|
475 |
\c DIMACS format and the encapsulated postscript format.
|
deba@2084
|
476 |
*/
|
deba@2084
|
477 |
|
deba@2084
|
478 |
/**
|
deba@2084
|
479 |
@defgroup lemon_io Lemon Input-Output
|
deba@2084
|
480 |
@ingroup io_group
|
deba@2084
|
481 |
\brief Reading and writing LEMON format
|
deba@2084
|
482 |
|
deba@2084
|
483 |
Methods for reading and writing LEMON format. More about this
|
deba@2084
|
484 |
format you can find on the \ref graph-io-page "Graph Input-Output"
|
deba@2084
|
485 |
tutorial pages.
|
alpar@1287
|
486 |
*/
|
alpar@1287
|
487 |
|
alpar@1287
|
488 |
/**
|
deba@2016
|
489 |
@defgroup section_io Section readers and writers
|
deba@2084
|
490 |
@ingroup lemon_io
|
deba@2016
|
491 |
\brief Section readers and writers for lemon Input-Output.
|
deba@2016
|
492 |
|
deba@2016
|
493 |
Here you can find which section readers and writers can attach to
|
deba@2016
|
494 |
the LemonReader and LemonWriter.
|
deba@2016
|
495 |
*/
|
deba@2016
|
496 |
|
deba@2016
|
497 |
/**
|
deba@2016
|
498 |
@defgroup item_io Item Readers and Writers
|
deba@2084
|
499 |
@ingroup lemon_io
|
deba@2016
|
500 |
\brief Item readers and writers for lemon Input-Output.
|
deba@2016
|
501 |
|
deba@2016
|
502 |
The Input-Output classes can handle more data type by example
|
deba@2016
|
503 |
as map or attribute value. Each of these should be written and
|
deba@2016
|
504 |
read some way. The module make possible to do this.
|
deba@2016
|
505 |
*/
|
deba@2016
|
506 |
|
deba@2016
|
507 |
/**
|
deba@2084
|
508 |
@defgroup eps_io Postscript exporting
|
deba@2084
|
509 |
@ingroup io_group
|
alpar@2117
|
510 |
\brief General \c EPS drawer and graph exporter
|
deba@2084
|
511 |
|
alpar@2117
|
512 |
This group contains general \c EPS drawing methods and special
|
deba@2084
|
513 |
graph exporting tools.
|
deba@2084
|
514 |
*/
|
deba@2084
|
515 |
|
deba@2084
|
516 |
|
deba@2084
|
517 |
/**
|
klao@1030
|
518 |
@defgroup concept Concepts
|
klao@959
|
519 |
\brief Skeleton classes and concept checking classes
|
alpar@794
|
520 |
|
klao@959
|
521 |
This group describes the data/algorithm skeletons and concept checking
|
klao@1030
|
522 |
classes implemented in LEMON.
|
klao@1030
|
523 |
|
alpar@2117
|
524 |
The purpose of the classes in this group is fourfold.
|
alpar@2117
|
525 |
|
alpar@2117
|
526 |
- These classes contain the documentations of the concepts. In order
|
alpar@2117
|
527 |
to avoid document multiplications, an implementation of a concept
|
alpar@2117
|
528 |
simply refers to the corresponding concept class.
|
klao@1030
|
529 |
|
alpar@2233
|
530 |
- These classes declare every functions, <tt>typedef</tt>s etc. an
|
alpar@2117
|
531 |
implementation of the concepts should provide, however completely
|
alpar@2117
|
532 |
without implementations and real data structures behind the
|
alpar@2117
|
533 |
interface. On the other hand they should provide nothing else. All
|
alpar@2117
|
534 |
the algorithms working on a data structure meeting a certain concept
|
alpar@2117
|
535 |
should compile with these classes. (Though it will not run properly,
|
alpar@2117
|
536 |
of course.) In this way it is easily to check if an algorithm
|
alpar@2117
|
537 |
doesn't use any extra feature of a certain implementation.
|
alpar@2117
|
538 |
|
alpar@2233
|
539 |
- The concept descriptor classes also provide a <em>checker class</em>
|
alpar@2117
|
540 |
that makes it possible check whether a certain implementation of a
|
alpar@2117
|
541 |
concept indeed provides all the required features.
|
alpar@2117
|
542 |
|
alpar@2117
|
543 |
- Finally, They can serve as a skeleton of a new implementation of a concept.
|
klao@1030
|
544 |
|
alpar@794
|
545 |
*/
|
alpar@794
|
546 |
|
deba@2084
|
547 |
|
klao@1030
|
548 |
/**
|
klao@1030
|
549 |
@defgroup graph_concepts Graph Structure Concepts
|
klao@1030
|
550 |
@ingroup concept
|
klao@1030
|
551 |
\brief Skeleton and concept checking classes for graph structures
|
klao@1030
|
552 |
|
klao@1030
|
553 |
This group contains the skeletons and concept checking classes of LEMON's
|
klao@1030
|
554 |
graph structures and helper classes used to implement these.
|
klao@1030
|
555 |
*/
|
alpar@794
|
556 |
|
alpar@1587
|
557 |
/* --- Unused group
|
alpar@678
|
558 |
@defgroup experimental Experimental Structures and Algorithms
|
alpar@678
|
559 |
This group contains some Experimental structures and algorithms.
|
alpar@678
|
560 |
The stuff here is subject to change.
|
alpar@678
|
561 |
*/
|
alpar@1151
|
562 |
|
alpar@1558
|
563 |
/**
|
athos@1582
|
564 |
\anchor demoprograms
|
athos@1582
|
565 |
|
alpar@1558
|
566 |
@defgroup demos Demo programs
|
alpar@1558
|
567 |
|
alpar@1559
|
568 |
Some demo programs are listed here. Their full source codes can be found in
|
alpar@1558
|
569 |
the \c demo subdirectory of the source tree.
|
alpar@1558
|
570 |
|
ladanyi@1639
|
571 |
The standard compilation procedure (<tt>./configure;make</tt>) will compile
|
ladanyi@1639
|
572 |
them, as well.
|
alpar@1558
|
573 |
|
alpar@1558
|
574 |
*/
|
alpar@1558
|
575 |
|
deba@2491
|
576 |
/**
|
deba@2491
|
577 |
@defgroup tools Standalone utility applications
|
deba@2491
|
578 |
|
deba@2491
|
579 |
Some utility applications are listed here.
|
deba@2491
|
580 |
|
deba@2491
|
581 |
The standard compilation procedure (<tt>./configure;make</tt>) will compile
|
deba@2491
|
582 |
them, as well.
|
deba@2491
|
583 |
|
deba@2491
|
584 |
*/
|
deba@2491
|
585 |
|