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