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@956
|
5 |
* Copyright (C) 2003-2010
|
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 |
|
kpeter@422
|
19 |
namespace lemon {
|
kpeter@422
|
20 |
|
alpar@40
|
21 |
/**
|
alpar@40
|
22 |
@defgroup datas Data Structures
|
kpeter@606
|
23 |
This group contains the several data structures implemented in LEMON.
|
alpar@40
|
24 |
*/
|
alpar@40
|
25 |
|
alpar@40
|
26 |
/**
|
alpar@40
|
27 |
@defgroup graphs Graph Structures
|
alpar@40
|
28 |
@ingroup datas
|
alpar@40
|
29 |
\brief Graph structures implemented in LEMON.
|
alpar@40
|
30 |
|
alpar@209
|
31 |
The implementation of combinatorial algorithms heavily relies on
|
alpar@209
|
32 |
efficient graph implementations. LEMON offers data structures which are
|
alpar@209
|
33 |
planned to be easily used in an experimental phase of implementation studies,
|
alpar@209
|
34 |
and thereafter the program code can be made efficient by small modifications.
|
alpar@40
|
35 |
|
alpar@40
|
36 |
The most efficient implementation of diverse applications require the
|
alpar@40
|
37 |
usage of different physical graph implementations. These differences
|
alpar@40
|
38 |
appear in the size of graph we require to handle, memory or time usage
|
alpar@40
|
39 |
limitations or in the set of operations through which the graph can be
|
alpar@40
|
40 |
accessed. LEMON provides several physical graph structures to meet
|
alpar@40
|
41 |
the diverging requirements of the possible users. In order to save on
|
alpar@40
|
42 |
running time or on memory usage, some structures may fail to provide
|
kpeter@83
|
43 |
some graph features like arc/edge or node deletion.
|
alpar@40
|
44 |
|
alpar@209
|
45 |
Alteration of standard containers need a very limited number of
|
alpar@209
|
46 |
operations, these together satisfy the everyday requirements.
|
alpar@209
|
47 |
In the case of graph structures, different operations are needed which do
|
alpar@209
|
48 |
not alter the physical graph, but gives another view. If some nodes or
|
kpeter@83
|
49 |
arcs have to be hidden or the reverse oriented graph have to be used, then
|
alpar@209
|
50 |
this is the case. It also may happen that in a flow implementation
|
alpar@209
|
51 |
the residual graph can be accessed by another algorithm, or a node-set
|
alpar@209
|
52 |
is to be shrunk for another algorithm.
|
alpar@209
|
53 |
LEMON also provides a variety of graphs for these requirements called
|
alpar@209
|
54 |
\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
|
alpar@209
|
55 |
in conjunction with other graph representations.
|
alpar@40
|
56 |
|
alpar@40
|
57 |
You are free to use the graph structure that fit your requirements
|
alpar@40
|
58 |
the best, most graph algorithms and auxiliary data structures can be used
|
kpeter@314
|
59 |
with any graph structure.
|
kpeter@314
|
60 |
|
kpeter@314
|
61 |
<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
|
alpar@40
|
62 |
*/
|
alpar@40
|
63 |
|
alpar@40
|
64 |
/**
|
kpeter@474
|
65 |
@defgroup graph_adaptors Adaptor Classes for Graphs
|
deba@432
|
66 |
@ingroup graphs
|
kpeter@474
|
67 |
\brief Adaptor classes for digraphs and graphs
|
kpeter@474
|
68 |
|
kpeter@474
|
69 |
This group contains several useful adaptor classes for digraphs and graphs.
|
deba@432
|
70 |
|
deba@432
|
71 |
The main parts of LEMON are the different graph structures, generic
|
kpeter@474
|
72 |
graph algorithms, graph concepts, which couple them, and graph
|
deba@432
|
73 |
adaptors. While the previous notions are more or less clear, the
|
deba@432
|
74 |
latter one needs further explanation. Graph adaptors are graph classes
|
deba@432
|
75 |
which serve for considering graph structures in different ways.
|
deba@432
|
76 |
|
deba@432
|
77 |
A short example makes this much clearer. Suppose that we have an
|
kpeter@474
|
78 |
instance \c g of a directed graph type, say ListDigraph and an algorithm
|
deba@432
|
79 |
\code
|
deba@432
|
80 |
template <typename Digraph>
|
deba@432
|
81 |
int algorithm(const Digraph&);
|
deba@432
|
82 |
\endcode
|
deba@432
|
83 |
is needed to run on the reverse oriented graph. It may be expensive
|
deba@432
|
84 |
(in time or in memory usage) to copy \c g with the reversed
|
deba@432
|
85 |
arcs. In this case, an adaptor class is used, which (according
|
kpeter@474
|
86 |
to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
|
kpeter@474
|
87 |
The adaptor uses the original digraph structure and digraph operations when
|
kpeter@474
|
88 |
methods of the reversed oriented graph are called. This means that the adaptor
|
kpeter@474
|
89 |
have minor memory usage, and do not perform sophisticated algorithmic
|
deba@432
|
90 |
actions. The purpose of it is to give a tool for the cases when a
|
deba@432
|
91 |
graph have to be used in a specific alteration. If this alteration is
|
kpeter@474
|
92 |
obtained by a usual construction like filtering the node or the arc set or
|
deba@432
|
93 |
considering a new orientation, then an adaptor is worthwhile to use.
|
deba@432
|
94 |
To come back to the reverse oriented graph, in this situation
|
deba@432
|
95 |
\code
|
deba@432
|
96 |
template<typename Digraph> class ReverseDigraph;
|
deba@432
|
97 |
\endcode
|
deba@432
|
98 |
template class can be used. The code looks as follows
|
deba@432
|
99 |
\code
|
deba@432
|
100 |
ListDigraph g;
|
kpeter@474
|
101 |
ReverseDigraph<ListDigraph> rg(g);
|
deba@432
|
102 |
int result = algorithm(rg);
|
deba@432
|
103 |
\endcode
|
kpeter@474
|
104 |
During running the algorithm, the original digraph \c g is untouched.
|
kpeter@474
|
105 |
This techniques give rise to an elegant code, and based on stable
|
deba@432
|
106 |
graph adaptors, complex algorithms can be implemented easily.
|
deba@432
|
107 |
|
kpeter@474
|
108 |
In flow, circulation and matching problems, the residual
|
deba@432
|
109 |
graph is of particular importance. Combining an adaptor implementing
|
kpeter@474
|
110 |
this with shortest path algorithms or minimum mean cycle algorithms,
|
deba@432
|
111 |
a range of weighted and cardinality optimization algorithms can be
|
deba@432
|
112 |
obtained. For other examples, the interested user is referred to the
|
deba@432
|
113 |
detailed documentation of particular adaptors.
|
deba@432
|
114 |
|
deba@432
|
115 |
The behavior of graph adaptors can be very different. Some of them keep
|
deba@432
|
116 |
capabilities of the original graph while in other cases this would be
|
kpeter@474
|
117 |
meaningless. This means that the concepts that they meet depend
|
kpeter@474
|
118 |
on the graph adaptor, and the wrapped graph.
|
kpeter@474
|
119 |
For example, if an arc of a reversed digraph is deleted, this is carried
|
kpeter@474
|
120 |
out by deleting the corresponding arc of the original digraph, thus the
|
kpeter@474
|
121 |
adaptor modifies the original digraph.
|
kpeter@474
|
122 |
However in case of a residual digraph, this operation has no sense.
|
deba@432
|
123 |
|
deba@432
|
124 |
Let us stand one more example here to simplify your work.
|
kpeter@474
|
125 |
ReverseDigraph has constructor
|
deba@432
|
126 |
\code
|
deba@432
|
127 |
ReverseDigraph(Digraph& digraph);
|
deba@432
|
128 |
\endcode
|
kpeter@474
|
129 |
This means that in a situation, when a <tt>const %ListDigraph&</tt>
|
deba@432
|
130 |
reference to a graph is given, then it have to be instantiated with
|
kpeter@474
|
131 |
<tt>Digraph=const %ListDigraph</tt>.
|
deba@432
|
132 |
\code
|
deba@432
|
133 |
int algorithm1(const ListDigraph& g) {
|
kpeter@474
|
134 |
ReverseDigraph<const ListDigraph> rg(g);
|
deba@432
|
135 |
return algorithm2(rg);
|
deba@432
|
136 |
}
|
deba@432
|
137 |
\endcode
|
deba@432
|
138 |
*/
|
deba@432
|
139 |
|
deba@432
|
140 |
/**
|
alpar@209
|
141 |
@defgroup maps Maps
|
alpar@40
|
142 |
@ingroup datas
|
kpeter@50
|
143 |
\brief Map structures implemented in LEMON.
|
alpar@40
|
144 |
|
kpeter@606
|
145 |
This group contains the map structures implemented in LEMON.
|
kpeter@50
|
146 |
|
kpeter@314
|
147 |
LEMON provides several special purpose maps and map adaptors that e.g. combine
|
alpar@40
|
148 |
new maps from existing ones.
|
kpeter@314
|
149 |
|
kpeter@314
|
150 |
<b>See also:</b> \ref map_concepts "Map Concepts".
|
alpar@40
|
151 |
*/
|
alpar@40
|
152 |
|
alpar@40
|
153 |
/**
|
alpar@209
|
154 |
@defgroup graph_maps Graph Maps
|
alpar@40
|
155 |
@ingroup maps
|
kpeter@83
|
156 |
\brief Special graph-related maps.
|
alpar@40
|
157 |
|
kpeter@606
|
158 |
This group contains maps that are specifically designed to assign
|
kpeter@422
|
159 |
values to the nodes and arcs/edges of graphs.
|
kpeter@422
|
160 |
|
kpeter@422
|
161 |
If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
|
kpeter@422
|
162 |
\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
|
alpar@40
|
163 |
*/
|
alpar@40
|
164 |
|
alpar@40
|
165 |
/**
|
alpar@40
|
166 |
\defgroup map_adaptors Map Adaptors
|
alpar@40
|
167 |
\ingroup maps
|
alpar@40
|
168 |
\brief Tools to create new maps from existing ones
|
alpar@40
|
169 |
|
kpeter@606
|
170 |
This group contains map adaptors that are used to create "implicit"
|
kpeter@50
|
171 |
maps from other maps.
|
alpar@40
|
172 |
|
kpeter@422
|
173 |
Most of them are \ref concepts::ReadMap "read-only maps".
|
kpeter@83
|
174 |
They can make arithmetic and logical operations between one or two maps
|
kpeter@83
|
175 |
(negation, shifting, addition, multiplication, logical 'and', 'or',
|
kpeter@83
|
176 |
'not' etc.) or e.g. convert a map to another one of different Value type.
|
alpar@40
|
177 |
|
kpeter@50
|
178 |
The typical usage of this classes is passing implicit maps to
|
alpar@40
|
179 |
algorithms. If a function type algorithm is called then the function
|
alpar@40
|
180 |
type map adaptors can be used comfortable. For example let's see the
|
kpeter@314
|
181 |
usage of map adaptors with the \c graphToEps() function.
|
alpar@40
|
182 |
\code
|
alpar@40
|
183 |
Color nodeColor(int deg) {
|
alpar@40
|
184 |
if (deg >= 2) {
|
alpar@40
|
185 |
return Color(0.5, 0.0, 0.5);
|
alpar@40
|
186 |
} else if (deg == 1) {
|
alpar@40
|
187 |
return Color(1.0, 0.5, 1.0);
|
alpar@40
|
188 |
} else {
|
alpar@40
|
189 |
return Color(0.0, 0.0, 0.0);
|
alpar@40
|
190 |
}
|
alpar@40
|
191 |
}
|
alpar@209
|
192 |
|
kpeter@83
|
193 |
Digraph::NodeMap<int> degree_map(graph);
|
alpar@209
|
194 |
|
kpeter@314
|
195 |
graphToEps(graph, "graph.eps")
|
alpar@40
|
196 |
.coords(coords).scaleToA4().undirected()
|
kpeter@83
|
197 |
.nodeColors(composeMap(functorToMap(nodeColor), degree_map))
|
alpar@40
|
198 |
.run();
|
alpar@209
|
199 |
\endcode
|
kpeter@83
|
200 |
The \c functorToMap() function makes an \c int to \c Color map from the
|
kpeter@314
|
201 |
\c nodeColor() function. The \c composeMap() compose the \c degree_map
|
kpeter@83
|
202 |
and the previously created map. The composed map is a proper function to
|
kpeter@83
|
203 |
get the color of each node.
|
alpar@40
|
204 |
|
alpar@40
|
205 |
The usage with class type algorithms is little bit harder. In this
|
alpar@40
|
206 |
case the function type map adaptors can not be used, because the
|
kpeter@50
|
207 |
function map adaptors give back temporary objects.
|
alpar@40
|
208 |
\code
|
kpeter@83
|
209 |
Digraph graph;
|
kpeter@83
|
210 |
|
kpeter@83
|
211 |
typedef Digraph::ArcMap<double> DoubleArcMap;
|
kpeter@83
|
212 |
DoubleArcMap length(graph);
|
kpeter@83
|
213 |
DoubleArcMap speed(graph);
|
kpeter@83
|
214 |
|
kpeter@83
|
215 |
typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
|
alpar@40
|
216 |
TimeMap time(length, speed);
|
alpar@209
|
217 |
|
kpeter@83
|
218 |
Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
|
alpar@40
|
219 |
dijkstra.run(source, target);
|
alpar@40
|
220 |
\endcode
|
kpeter@83
|
221 |
We have a length map and a maximum speed map on the arcs of a digraph.
|
kpeter@83
|
222 |
The minimum time to pass the arc can be calculated as the division of
|
kpeter@83
|
223 |
the two maps which can be done implicitly with the \c DivMap template
|
alpar@40
|
224 |
class. We use the implicit minimum time map as the length map of the
|
alpar@40
|
225 |
\c Dijkstra algorithm.
|
alpar@40
|
226 |
*/
|
alpar@40
|
227 |
|
alpar@40
|
228 |
/**
|
alpar@40
|
229 |
@defgroup paths Path Structures
|
alpar@40
|
230 |
@ingroup datas
|
kpeter@318
|
231 |
\brief %Path structures implemented in LEMON.
|
alpar@40
|
232 |
|
kpeter@606
|
233 |
This group contains the path structures implemented in LEMON.
|
alpar@40
|
234 |
|
kpeter@50
|
235 |
LEMON provides flexible data structures to work with paths.
|
kpeter@50
|
236 |
All of them have similar interfaces and they can be copied easily with
|
kpeter@50
|
237 |
assignment operators and copy constructors. This makes it easy and
|
alpar@40
|
238 |
efficient to have e.g. the Dijkstra algorithm to store its result in
|
alpar@40
|
239 |
any kind of path structure.
|
alpar@40
|
240 |
|
kpeter@757
|
241 |
\sa \ref concepts::Path "Path concept"
|
kpeter@757
|
242 |
*/
|
kpeter@757
|
243 |
|
kpeter@757
|
244 |
/**
|
kpeter@757
|
245 |
@defgroup heaps Heap Structures
|
kpeter@757
|
246 |
@ingroup datas
|
kpeter@757
|
247 |
\brief %Heap structures implemented in LEMON.
|
kpeter@757
|
248 |
|
kpeter@757
|
249 |
This group contains the heap structures implemented in LEMON.
|
kpeter@757
|
250 |
|
kpeter@757
|
251 |
LEMON provides several heap classes. They are efficient implementations
|
kpeter@757
|
252 |
of the abstract data type \e priority \e queue. They store items with
|
kpeter@757
|
253 |
specified values called \e priorities in such a way that finding and
|
kpeter@757
|
254 |
removing the item with minimum priority are efficient.
|
kpeter@757
|
255 |
The basic operations are adding and erasing items, changing the priority
|
kpeter@757
|
256 |
of an item, etc.
|
kpeter@757
|
257 |
|
kpeter@757
|
258 |
Heaps are crucial in several algorithms, such as Dijkstra and Prim.
|
kpeter@757
|
259 |
The heap implementations have the same interface, thus any of them can be
|
kpeter@757
|
260 |
used easily in such algorithms.
|
kpeter@757
|
261 |
|
kpeter@757
|
262 |
\sa \ref concepts::Heap "Heap concept"
|
kpeter@757
|
263 |
*/
|
kpeter@757
|
264 |
|
kpeter@757
|
265 |
/**
|
alpar@40
|
266 |
@defgroup auxdat Auxiliary Data Structures
|
alpar@40
|
267 |
@ingroup datas
|
kpeter@50
|
268 |
\brief Auxiliary data structures implemented in LEMON.
|
alpar@40
|
269 |
|
kpeter@606
|
270 |
This group contains some data structures implemented in LEMON in
|
alpar@40
|
271 |
order to make it easier to implement combinatorial algorithms.
|
alpar@40
|
272 |
*/
|
alpar@40
|
273 |
|
alpar@40
|
274 |
/**
|
kpeter@761
|
275 |
@defgroup geomdat Geometric Data Structures
|
kpeter@761
|
276 |
@ingroup auxdat
|
kpeter@761
|
277 |
\brief Geometric data structures implemented in LEMON.
|
kpeter@761
|
278 |
|
kpeter@761
|
279 |
This group contains geometric data structures implemented in LEMON.
|
kpeter@761
|
280 |
|
kpeter@761
|
281 |
- \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
|
kpeter@761
|
282 |
vector with the usual operations.
|
kpeter@761
|
283 |
- \ref lemon::dim2::Box "dim2::Box" can be used to determine the
|
kpeter@761
|
284 |
rectangular bounding box of a set of \ref lemon::dim2::Point
|
kpeter@761
|
285 |
"dim2::Point"'s.
|
kpeter@761
|
286 |
*/
|
kpeter@761
|
287 |
|
kpeter@761
|
288 |
/**
|
kpeter@761
|
289 |
@defgroup matrices Matrices
|
kpeter@761
|
290 |
@ingroup auxdat
|
kpeter@761
|
291 |
\brief Two dimensional data storages implemented in LEMON.
|
kpeter@761
|
292 |
|
kpeter@761
|
293 |
This group contains two dimensional data storages implemented in LEMON.
|
kpeter@761
|
294 |
*/
|
kpeter@761
|
295 |
|
kpeter@761
|
296 |
/**
|
alpar@40
|
297 |
@defgroup algs Algorithms
|
kpeter@606
|
298 |
\brief This group contains the several algorithms
|
alpar@40
|
299 |
implemented in LEMON.
|
alpar@40
|
300 |
|
kpeter@606
|
301 |
This group contains the several algorithms
|
alpar@40
|
302 |
implemented in LEMON.
|
alpar@40
|
303 |
*/
|
alpar@40
|
304 |
|
alpar@40
|
305 |
/**
|
alpar@40
|
306 |
@defgroup search Graph Search
|
alpar@40
|
307 |
@ingroup algs
|
kpeter@50
|
308 |
\brief Common graph search algorithms.
|
alpar@40
|
309 |
|
kpeter@606
|
310 |
This group contains the common graph search algorithms, namely
|
kpeter@802
|
311 |
\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
|
kpeter@802
|
312 |
\ref clrs01algorithms.
|
alpar@40
|
313 |
*/
|
alpar@40
|
314 |
|
alpar@40
|
315 |
/**
|
kpeter@314
|
316 |
@defgroup shortest_path Shortest Path Algorithms
|
alpar@40
|
317 |
@ingroup algs
|
kpeter@50
|
318 |
\brief Algorithms for finding shortest paths.
|
alpar@40
|
319 |
|
kpeter@802
|
320 |
This group contains the algorithms for finding shortest paths in digraphs
|
kpeter@802
|
321 |
\ref clrs01algorithms.
|
kpeter@422
|
322 |
|
kpeter@422
|
323 |
- \ref Dijkstra algorithm for finding shortest paths from a source node
|
kpeter@422
|
324 |
when all arc lengths are non-negative.
|
kpeter@422
|
325 |
- \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
|
kpeter@422
|
326 |
from a source node when arc lenghts can be either positive or negative,
|
kpeter@422
|
327 |
but the digraph should not contain directed cycles with negative total
|
kpeter@422
|
328 |
length.
|
kpeter@422
|
329 |
- \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
|
kpeter@422
|
330 |
for solving the \e all-pairs \e shortest \e paths \e problem when arc
|
kpeter@422
|
331 |
lenghts can be either positive or negative, but the digraph should
|
kpeter@422
|
332 |
not contain directed cycles with negative total length.
|
kpeter@422
|
333 |
- \ref Suurballe A successive shortest path algorithm for finding
|
kpeter@422
|
334 |
arc-disjoint paths between two nodes having minimum total length.
|
alpar@40
|
335 |
*/
|
alpar@40
|
336 |
|
alpar@209
|
337 |
/**
|
kpeter@761
|
338 |
@defgroup spantree Minimum Spanning Tree Algorithms
|
kpeter@761
|
339 |
@ingroup algs
|
kpeter@761
|
340 |
\brief Algorithms for finding minimum cost spanning trees and arborescences.
|
kpeter@761
|
341 |
|
kpeter@761
|
342 |
This group contains the algorithms for finding minimum cost spanning
|
kpeter@802
|
343 |
trees and arborescences \ref clrs01algorithms.
|
kpeter@761
|
344 |
*/
|
kpeter@761
|
345 |
|
kpeter@761
|
346 |
/**
|
kpeter@314
|
347 |
@defgroup max_flow Maximum Flow Algorithms
|
alpar@209
|
348 |
@ingroup algs
|
kpeter@50
|
349 |
\brief Algorithms for finding maximum flows.
|
alpar@40
|
350 |
|
kpeter@606
|
351 |
This group contains the algorithms for finding maximum flows and
|
kpeter@802
|
352 |
feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
|
alpar@40
|
353 |
|
kpeter@422
|
354 |
The \e maximum \e flow \e problem is to find a flow of maximum value between
|
kpeter@422
|
355 |
a single source and a single target. Formally, there is a \f$G=(V,A)\f$
|
kpeter@656
|
356 |
digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
|
kpeter@422
|
357 |
\f$s, t \in V\f$ source and target nodes.
|
kpeter@656
|
358 |
A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
|
kpeter@422
|
359 |
following optimization problem.
|
alpar@40
|
360 |
|
kpeter@656
|
361 |
\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
|
kpeter@656
|
362 |
\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
|
kpeter@656
|
363 |
\quad \forall u\in V\setminus\{s,t\} \f]
|
kpeter@656
|
364 |
\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
|
alpar@40
|
365 |
|
kpeter@50
|
366 |
LEMON contains several algorithms for solving maximum flow problems:
|
kpeter@802
|
367 |
- \ref EdmondsKarp Edmonds-Karp algorithm
|
kpeter@802
|
368 |
\ref edmondskarp72theoretical.
|
kpeter@802
|
369 |
- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
|
kpeter@802
|
370 |
\ref goldberg88newapproach.
|
kpeter@802
|
371 |
- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
|
kpeter@802
|
372 |
\ref dinic70algorithm, \ref sleator83dynamic.
|
kpeter@802
|
373 |
- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
|
kpeter@802
|
374 |
\ref goldberg88newapproach, \ref sleator83dynamic.
|
alpar@40
|
375 |
|
kpeter@802
|
376 |
In most cases the \ref Preflow algorithm provides the
|
kpeter@422
|
377 |
fastest method for computing a maximum flow. All implementations
|
kpeter@698
|
378 |
also provide functions to query the minimum cut, which is the dual
|
kpeter@698
|
379 |
problem of maximum flow.
|
kpeter@698
|
380 |
|
deba@948
|
381 |
\ref Circulation is a preflow push-relabel algorithm implemented directly
|
kpeter@698
|
382 |
for finding feasible circulations, which is a somewhat different problem,
|
kpeter@698
|
383 |
but it is strongly related to maximum flow.
|
kpeter@698
|
384 |
For more information, see \ref Circulation.
|
alpar@40
|
385 |
*/
|
alpar@40
|
386 |
|
alpar@40
|
387 |
/**
|
kpeter@710
|
388 |
@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
|
alpar@40
|
389 |
@ingroup algs
|
alpar@40
|
390 |
|
kpeter@50
|
391 |
\brief Algorithms for finding minimum cost flows and circulations.
|
alpar@40
|
392 |
|
kpeter@656
|
393 |
This group contains the algorithms for finding minimum cost flows and
|
kpeter@802
|
394 |
circulations \ref amo93networkflows. For more information about this
|
kpeter@1217
|
395 |
problem and its dual solution, see: \ref min_cost_flow
|
kpeter@802
|
396 |
"Minimum Cost Flow Problem".
|
kpeter@422
|
397 |
|
kpeter@710
|
398 |
LEMON contains several algorithms for this problem.
|
kpeter@656
|
399 |
- \ref NetworkSimplex Primal Network Simplex algorithm with various
|
kpeter@802
|
400 |
pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
|
kpeter@879
|
401 |
- \ref CostScaling Cost Scaling algorithm based on push/augment and
|
kpeter@879
|
402 |
relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
|
kpeter@802
|
403 |
\ref bunnagel98efficient.
|
kpeter@879
|
404 |
- \ref CapacityScaling Capacity Scaling algorithm based on the successive
|
kpeter@879
|
405 |
shortest path method \ref edmondskarp72theoretical.
|
kpeter@879
|
406 |
- \ref CycleCanceling Cycle-Canceling algorithms, two of which are
|
kpeter@879
|
407 |
strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
|
kpeter@656
|
408 |
|
kpeter@1023
|
409 |
In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
|
kpeter@1165
|
410 |
implementations.
|
kpeter@1165
|
411 |
\ref NetworkSimplex is usually the fastest on relatively small graphs (up to
|
kpeter@1165
|
412 |
several thousands of nodes) and on dense graphs, while \ref CostScaling is
|
kpeter@1165
|
413 |
typically more efficient on large graphs (e.g. hundreds of thousands of
|
kpeter@1165
|
414 |
nodes or above), especially if they are sparse.
|
kpeter@1165
|
415 |
However, other algorithms could be faster in special cases.
|
kpeter@656
|
416 |
For example, if the total supply and/or capacities are rather small,
|
kpeter@1023
|
417 |
\ref CapacityScaling is usually the fastest algorithm (without effective scaling).
|
kpeter@1164
|
418 |
|
kpeter@1164
|
419 |
These classes are intended to be used with integer-valued input data
|
kpeter@1164
|
420 |
(capacities, supply values, and costs), except for \ref CapacityScaling,
|
kpeter@1164
|
421 |
which is capable of handling real-valued arc costs (other numerical
|
kpeter@1164
|
422 |
data are required to be integer).
|
alpar@40
|
423 |
*/
|
alpar@40
|
424 |
|
alpar@40
|
425 |
/**
|
kpeter@314
|
426 |
@defgroup min_cut Minimum Cut Algorithms
|
alpar@209
|
427 |
@ingroup algs
|
alpar@40
|
428 |
|
kpeter@50
|
429 |
\brief Algorithms for finding minimum cut in graphs.
|
alpar@40
|
430 |
|
kpeter@606
|
431 |
This group contains the algorithms for finding minimum cut in graphs.
|
alpar@40
|
432 |
|
kpeter@422
|
433 |
The \e minimum \e cut \e problem is to find a non-empty and non-complete
|
kpeter@422
|
434 |
\f$X\f$ subset of the nodes with minimum overall capacity on
|
kpeter@422
|
435 |
outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
|
kpeter@422
|
436 |
\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
|
kpeter@50
|
437 |
cut is the \f$X\f$ solution of the next optimization problem:
|
alpar@40
|
438 |
|
alpar@210
|
439 |
\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
|
kpeter@760
|
440 |
\sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
|
alpar@40
|
441 |
|
kpeter@50
|
442 |
LEMON contains several algorithms related to minimum cut problems:
|
alpar@40
|
443 |
|
kpeter@422
|
444 |
- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
|
kpeter@422
|
445 |
in directed graphs.
|
kpeter@422
|
446 |
- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
|
kpeter@422
|
447 |
calculating minimum cut in undirected graphs.
|
kpeter@606
|
448 |
- \ref GomoryHu "Gomory-Hu tree computation" for calculating
|
kpeter@422
|
449 |
all-pairs minimum cut in undirected graphs.
|
alpar@40
|
450 |
|
alpar@40
|
451 |
If you want to find minimum cut just between two distinict nodes,
|
kpeter@422
|
452 |
see the \ref max_flow "maximum flow problem".
|
alpar@40
|
453 |
*/
|
alpar@40
|
454 |
|
alpar@40
|
455 |
/**
|
kpeter@815
|
456 |
@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
|
alpar@40
|
457 |
@ingroup algs
|
kpeter@815
|
458 |
\brief Algorithms for finding minimum mean cycles.
|
alpar@40
|
459 |
|
kpeter@818
|
460 |
This group contains the algorithms for finding minimum mean cycles
|
kpeter@1164
|
461 |
\ref amo93networkflows, \ref karp78characterization.
|
alpar@40
|
462 |
|
kpeter@815
|
463 |
The \e minimum \e mean \e cycle \e problem is to find a directed cycle
|
kpeter@815
|
464 |
of minimum mean length (cost) in a digraph.
|
kpeter@815
|
465 |
The mean length of a cycle is the average length of its arcs, i.e. the
|
kpeter@815
|
466 |
ratio between the total length of the cycle and the number of arcs on it.
|
alpar@40
|
467 |
|
kpeter@815
|
468 |
This problem has an important connection to \e conservative \e length
|
kpeter@815
|
469 |
\e functions, too. A length function on the arcs of a digraph is called
|
kpeter@815
|
470 |
conservative if and only if there is no directed cycle of negative total
|
kpeter@815
|
471 |
length. For an arbitrary length function, the negative of the minimum
|
kpeter@815
|
472 |
cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
|
kpeter@815
|
473 |
arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
|
kpeter@815
|
474 |
function.
|
alpar@40
|
475 |
|
kpeter@815
|
476 |
LEMON contains three algorithms for solving the minimum mean cycle problem:
|
kpeter@1164
|
477 |
- \ref KarpMmc Karp's original algorithm \ref karp78characterization.
|
kpeter@959
|
478 |
- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
|
kpeter@1164
|
479 |
version of Karp's algorithm \ref hartmann93finding.
|
kpeter@959
|
480 |
- \ref HowardMmc Howard's policy iteration algorithm
|
kpeter@1164
|
481 |
\ref dasdan98minmeancycle, \ref dasdan04experimental.
|
alpar@40
|
482 |
|
kpeter@1023
|
483 |
In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
|
kpeter@959
|
484 |
most efficient one, though the best known theoretical bound on its running
|
kpeter@959
|
485 |
time is exponential.
|
kpeter@959
|
486 |
Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
|
kpeter@1217
|
487 |
run in time O(ne) and use space O(n<sup>2</sup>+e).
|
alpar@40
|
488 |
*/
|
alpar@40
|
489 |
|
alpar@40
|
490 |
/**
|
kpeter@314
|
491 |
@defgroup matching Matching Algorithms
|
alpar@40
|
492 |
@ingroup algs
|
kpeter@50
|
493 |
\brief Algorithms for finding matchings in graphs and bipartite graphs.
|
alpar@40
|
494 |
|
kpeter@637
|
495 |
This group contains the algorithms for calculating
|
alpar@40
|
496 |
matchings in graphs and bipartite graphs. The general matching problem is
|
kpeter@637
|
497 |
finding a subset of the edges for which each node has at most one incident
|
kpeter@637
|
498 |
edge.
|
alpar@209
|
499 |
|
alpar@40
|
500 |
There are several different algorithms for calculate matchings in
|
alpar@40
|
501 |
graphs. The matching problems in bipartite graphs are generally
|
alpar@40
|
502 |
easier than in general graphs. The goal of the matching optimization
|
kpeter@422
|
503 |
can be finding maximum cardinality, maximum weight or minimum cost
|
alpar@40
|
504 |
matching. The search can be constrained to find perfect or
|
alpar@40
|
505 |
maximum cardinality matching.
|
alpar@40
|
506 |
|
kpeter@422
|
507 |
The matching algorithms implemented in LEMON:
|
kpeter@422
|
508 |
- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
|
kpeter@422
|
509 |
for calculating maximum cardinality matching in bipartite graphs.
|
kpeter@422
|
510 |
- \ref PrBipartiteMatching Push-relabel algorithm
|
kpeter@422
|
511 |
for calculating maximum cardinality matching in bipartite graphs.
|
kpeter@422
|
512 |
- \ref MaxWeightedBipartiteMatching
|
kpeter@422
|
513 |
Successive shortest path algorithm for calculating maximum weighted
|
kpeter@422
|
514 |
matching and maximum weighted bipartite matching in bipartite graphs.
|
kpeter@422
|
515 |
- \ref MinCostMaxBipartiteMatching
|
kpeter@422
|
516 |
Successive shortest path algorithm for calculating minimum cost maximum
|
kpeter@422
|
517 |
matching in bipartite graphs.
|
kpeter@422
|
518 |
- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
|
kpeter@422
|
519 |
maximum cardinality matching in general graphs.
|
kpeter@422
|
520 |
- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
|
kpeter@422
|
521 |
maximum weighted matching in general graphs.
|
kpeter@422
|
522 |
- \ref MaxWeightedPerfectMatching
|
kpeter@422
|
523 |
Edmond's blossom shrinking algorithm for calculating maximum weighted
|
kpeter@422
|
524 |
perfect matching in general graphs.
|
deba@948
|
525 |
- \ref MaxFractionalMatching Push-relabel algorithm for calculating
|
deba@948
|
526 |
maximum cardinality fractional matching in general graphs.
|
deba@948
|
527 |
- \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating
|
deba@948
|
528 |
maximum weighted fractional matching in general graphs.
|
deba@948
|
529 |
- \ref MaxWeightedPerfectFractionalMatching
|
deba@948
|
530 |
Augmenting path algorithm for calculating maximum weighted
|
deba@948
|
531 |
perfect fractional matching in general graphs.
|
alpar@40
|
532 |
|
alpar@943
|
533 |
\image html matching.png
|
alpar@952
|
534 |
\image latex matching.eps "Min Cost Perfect Matching" width=\textwidth
|
alpar@40
|
535 |
*/
|
alpar@40
|
536 |
|
alpar@40
|
537 |
/**
|
kpeter@761
|
538 |
@defgroup graph_properties Connectivity and Other Graph Properties
|
alpar@40
|
539 |
@ingroup algs
|
kpeter@761
|
540 |
\brief Algorithms for discovering the graph properties
|
alpar@40
|
541 |
|
kpeter@761
|
542 |
This group contains the algorithms for discovering the graph properties
|
kpeter@761
|
543 |
like connectivity, bipartiteness, euler property, simplicity etc.
|
kpeter@761
|
544 |
|
kpeter@761
|
545 |
\image html connected_components.png
|
kpeter@761
|
546 |
\image latex connected_components.eps "Connected components" width=\textwidth
|
kpeter@761
|
547 |
*/
|
kpeter@761
|
548 |
|
kpeter@761
|
549 |
/**
|
kpeter@1023
|
550 |
@defgroup planar Planar Embedding and Drawing
|
kpeter@761
|
551 |
@ingroup algs
|
kpeter@761
|
552 |
\brief Algorithms for planarity checking, embedding and drawing
|
kpeter@761
|
553 |
|
kpeter@761
|
554 |
This group contains the algorithms for planarity checking,
|
kpeter@761
|
555 |
embedding and drawing.
|
kpeter@761
|
556 |
|
kpeter@761
|
557 |
\image html planar.png
|
kpeter@761
|
558 |
\image latex planar.eps "Plane graph" width=\textwidth
|
kpeter@761
|
559 |
*/
|
kpeter@1200
|
560 |
|
kpeter@1200
|
561 |
/**
|
kpeter@1200
|
562 |
@defgroup tsp Traveling Salesman Problem
|
kpeter@1200
|
563 |
@ingroup algs
|
kpeter@1200
|
564 |
\brief Algorithms for the symmetric traveling salesman problem
|
kpeter@1200
|
565 |
|
kpeter@1200
|
566 |
This group contains basic heuristic algorithms for the the symmetric
|
kpeter@1200
|
567 |
\e traveling \e salesman \e problem (TSP).
|
kpeter@1200
|
568 |
Given an \ref FullGraph "undirected full graph" with a cost map on its edges,
|
kpeter@1200
|
569 |
the problem is to find a shortest possible tour that visits each node exactly
|
kpeter@1200
|
570 |
once (i.e. the minimum cost Hamiltonian cycle).
|
kpeter@1200
|
571 |
|
kpeter@1202
|
572 |
These TSP algorithms are intended to be used with a \e metric \e cost
|
kpeter@1202
|
573 |
\e function, i.e. the edge costs should satisfy the triangle inequality.
|
kpeter@1202
|
574 |
Otherwise the algorithms could yield worse results.
|
kpeter@1200
|
575 |
|
kpeter@1200
|
576 |
LEMON provides five well-known heuristics for solving symmetric TSP:
|
kpeter@1200
|
577 |
- \ref NearestNeighborTsp Neareast neighbor algorithm
|
kpeter@1200
|
578 |
- \ref GreedyTsp Greedy algorithm
|
kpeter@1200
|
579 |
- \ref InsertionTsp Insertion heuristic (with four selection methods)
|
kpeter@1200
|
580 |
- \ref ChristofidesTsp Christofides algorithm
|
kpeter@1200
|
581 |
- \ref Opt2Tsp 2-opt algorithm
|
kpeter@1200
|
582 |
|
kpeter@1204
|
583 |
\ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest
|
kpeter@1204
|
584 |
solution methods. Furthermore, \ref InsertionTsp is usually quite effective.
|
kpeter@1204
|
585 |
|
kpeter@1204
|
586 |
\ref ChristofidesTsp is somewhat slower, but it has the best guaranteed
|
kpeter@1204
|
587 |
approximation factor: 3/2.
|
kpeter@1204
|
588 |
|
kpeter@1204
|
589 |
\ref Opt2Tsp usually provides the best results in practice, but
|
kpeter@1204
|
590 |
it is the slowest method. It can also be used to improve given tours,
|
kpeter@1204
|
591 |
for example, the results of other algorithms.
|
kpeter@1204
|
592 |
|
kpeter@1200
|
593 |
\image html tsp.png
|
kpeter@1200
|
594 |
\image latex tsp.eps "Traveling salesman problem" width=\textwidth
|
kpeter@1200
|
595 |
*/
|
kpeter@761
|
596 |
|
kpeter@761
|
597 |
/**
|
kpeter@999
|
598 |
@defgroup approx_algs Approximation Algorithms
|
kpeter@761
|
599 |
@ingroup algs
|
kpeter@761
|
600 |
\brief Approximation algorithms.
|
kpeter@761
|
601 |
|
kpeter@761
|
602 |
This group contains the approximation and heuristic algorithms
|
kpeter@761
|
603 |
implemented in LEMON.
|
kpeter@999
|
604 |
|
kpeter@999
|
605 |
<b>Maximum Clique Problem</b>
|
kpeter@999
|
606 |
- \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
|
kpeter@999
|
607 |
Grosso, Locatelli, and Pullan.
|
alpar@40
|
608 |
*/
|
alpar@40
|
609 |
|
alpar@40
|
610 |
/**
|
kpeter@314
|
611 |
@defgroup auxalg Auxiliary Algorithms
|
alpar@40
|
612 |
@ingroup algs
|
kpeter@50
|
613 |
\brief Auxiliary algorithms implemented in LEMON.
|
alpar@40
|
614 |
|
kpeter@606
|
615 |
This group contains some algorithms implemented in LEMON
|
kpeter@50
|
616 |
in order to make it easier to implement complex algorithms.
|
alpar@40
|
617 |
*/
|
alpar@40
|
618 |
|
alpar@40
|
619 |
/**
|
alpar@40
|
620 |
@defgroup gen_opt_group General Optimization Tools
|
kpeter@606
|
621 |
\brief This group contains some general optimization frameworks
|
alpar@40
|
622 |
implemented in LEMON.
|
alpar@40
|
623 |
|
kpeter@606
|
624 |
This group contains some general optimization frameworks
|
alpar@40
|
625 |
implemented in LEMON.
|
alpar@40
|
626 |
*/
|
alpar@40
|
627 |
|
alpar@40
|
628 |
/**
|
kpeter@802
|
629 |
@defgroup lp_group LP and MIP Solvers
|
alpar@40
|
630 |
@ingroup gen_opt_group
|
kpeter@802
|
631 |
\brief LP and MIP solver interfaces for LEMON.
|
alpar@40
|
632 |
|
kpeter@802
|
633 |
This group contains LP and MIP solver interfaces for LEMON.
|
kpeter@802
|
634 |
Various LP solvers could be used in the same manner with this
|
kpeter@802
|
635 |
high-level interface.
|
kpeter@802
|
636 |
|
kpeter@802
|
637 |
The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
|
kpeter@802
|
638 |
\ref cplex, \ref soplex.
|
alpar@40
|
639 |
*/
|
alpar@40
|
640 |
|
alpar@209
|
641 |
/**
|
kpeter@314
|
642 |
@defgroup lp_utils Tools for Lp and Mip Solvers
|
alpar@40
|
643 |
@ingroup lp_group
|
kpeter@50
|
644 |
\brief Helper tools to the Lp and Mip solvers.
|
alpar@40
|
645 |
|
alpar@40
|
646 |
This group adds some helper tools to general optimization framework
|
alpar@40
|
647 |
implemented in LEMON.
|
alpar@40
|
648 |
*/
|
alpar@40
|
649 |
|
alpar@40
|
650 |
/**
|
alpar@40
|
651 |
@defgroup metah Metaheuristics
|
alpar@40
|
652 |
@ingroup gen_opt_group
|
alpar@40
|
653 |
\brief Metaheuristics for LEMON library.
|
alpar@40
|
654 |
|
kpeter@606
|
655 |
This group contains some metaheuristic optimization tools.
|
alpar@40
|
656 |
*/
|
alpar@40
|
657 |
|
alpar@40
|
658 |
/**
|
alpar@209
|
659 |
@defgroup utils Tools and Utilities
|
kpeter@50
|
660 |
\brief Tools and utilities for programming in LEMON
|
alpar@40
|
661 |
|
kpeter@50
|
662 |
Tools and utilities for programming in LEMON.
|
alpar@40
|
663 |
*/
|
alpar@40
|
664 |
|
alpar@40
|
665 |
/**
|
alpar@40
|
666 |
@defgroup gutils Basic Graph Utilities
|
alpar@40
|
667 |
@ingroup utils
|
kpeter@50
|
668 |
\brief Simple basic graph utilities.
|
alpar@40
|
669 |
|
kpeter@606
|
670 |
This group contains some simple basic graph utilities.
|
alpar@40
|
671 |
*/
|
alpar@40
|
672 |
|
alpar@40
|
673 |
/**
|
alpar@40
|
674 |
@defgroup misc Miscellaneous Tools
|
alpar@40
|
675 |
@ingroup utils
|
kpeter@50
|
676 |
\brief Tools for development, debugging and testing.
|
kpeter@50
|
677 |
|
kpeter@606
|
678 |
This group contains several useful tools for development,
|
alpar@40
|
679 |
debugging and testing.
|
alpar@40
|
680 |
*/
|
alpar@40
|
681 |
|
alpar@40
|
682 |
/**
|
kpeter@314
|
683 |
@defgroup timecount Time Measuring and Counting
|
alpar@40
|
684 |
@ingroup misc
|
kpeter@50
|
685 |
\brief Simple tools for measuring the performance of algorithms.
|
kpeter@50
|
686 |
|
kpeter@606
|
687 |
This group contains simple tools for measuring the performance
|
alpar@40
|
688 |
of algorithms.
|
alpar@40
|
689 |
*/
|
alpar@40
|
690 |
|
alpar@40
|
691 |
/**
|
alpar@40
|
692 |
@defgroup exceptions Exceptions
|
alpar@40
|
693 |
@ingroup utils
|
kpeter@50
|
694 |
\brief Exceptions defined in LEMON.
|
kpeter@50
|
695 |
|
kpeter@606
|
696 |
This group contains the exceptions defined in LEMON.
|
alpar@40
|
697 |
*/
|
alpar@40
|
698 |
|
alpar@40
|
699 |
/**
|
alpar@40
|
700 |
@defgroup io_group Input-Output
|
kpeter@50
|
701 |
\brief Graph Input-Output methods
|
alpar@40
|
702 |
|
kpeter@606
|
703 |
This group contains the tools for importing and exporting graphs
|
kpeter@314
|
704 |
and graph related data. Now it supports the \ref lgf-format
|
kpeter@314
|
705 |
"LEMON Graph Format", the \c DIMACS format and the encapsulated
|
kpeter@314
|
706 |
postscript (EPS) format.
|
alpar@40
|
707 |
*/
|
alpar@40
|
708 |
|
alpar@40
|
709 |
/**
|
kpeter@363
|
710 |
@defgroup lemon_io LEMON Graph Format
|
alpar@40
|
711 |
@ingroup io_group
|
kpeter@314
|
712 |
\brief Reading and writing LEMON Graph Format.
|
alpar@40
|
713 |
|
kpeter@606
|
714 |
This group contains methods for reading and writing
|
ladanyi@236
|
715 |
\ref lgf-format "LEMON Graph Format".
|
alpar@40
|
716 |
*/
|
alpar@40
|
717 |
|
alpar@40
|
718 |
/**
|
kpeter@314
|
719 |
@defgroup eps_io Postscript Exporting
|
alpar@40
|
720 |
@ingroup io_group
|
alpar@40
|
721 |
\brief General \c EPS drawer and graph exporter
|
alpar@40
|
722 |
|
kpeter@606
|
723 |
This group contains general \c EPS drawing methods and special
|
alpar@209
|
724 |
graph exporting tools.
|
alpar@40
|
725 |
*/
|
alpar@40
|
726 |
|
alpar@40
|
727 |
/**
|
kpeter@761
|
728 |
@defgroup dimacs_group DIMACS Format
|
kpeter@403
|
729 |
@ingroup io_group
|
kpeter@403
|
730 |
\brief Read and write files in DIMACS format
|
kpeter@403
|
731 |
|
kpeter@403
|
732 |
Tools to read a digraph from or write it to a file in DIMACS format data.
|
kpeter@403
|
733 |
*/
|
kpeter@403
|
734 |
|
kpeter@403
|
735 |
/**
|
kpeter@363
|
736 |
@defgroup nauty_group NAUTY Format
|
kpeter@363
|
737 |
@ingroup io_group
|
kpeter@363
|
738 |
\brief Read \e Nauty format
|
kpeter@403
|
739 |
|
kpeter@363
|
740 |
Tool to read graphs from \e Nauty format data.
|
kpeter@363
|
741 |
*/
|
kpeter@363
|
742 |
|
kpeter@363
|
743 |
/**
|
alpar@40
|
744 |
@defgroup concept Concepts
|
alpar@40
|
745 |
\brief Skeleton classes and concept checking classes
|
alpar@40
|
746 |
|
kpeter@606
|
747 |
This group contains the data/algorithm skeletons and concept checking
|
alpar@40
|
748 |
classes implemented in LEMON.
|
alpar@40
|
749 |
|
alpar@40
|
750 |
The purpose of the classes in this group is fourfold.
|
alpar@209
|
751 |
|
kpeter@318
|
752 |
- These classes contain the documentations of the %concepts. In order
|
alpar@40
|
753 |
to avoid document multiplications, an implementation of a concept
|
alpar@40
|
754 |
simply refers to the corresponding concept class.
|
alpar@40
|
755 |
|
alpar@40
|
756 |
- These classes declare every functions, <tt>typedef</tt>s etc. an
|
kpeter@318
|
757 |
implementation of the %concepts should provide, however completely
|
alpar@40
|
758 |
without implementations and real data structures behind the
|
alpar@40
|
759 |
interface. On the other hand they should provide nothing else. All
|
alpar@40
|
760 |
the algorithms working on a data structure meeting a certain concept
|
alpar@40
|
761 |
should compile with these classes. (Though it will not run properly,
|
alpar@40
|
762 |
of course.) In this way it is easily to check if an algorithm
|
alpar@40
|
763 |
doesn't use any extra feature of a certain implementation.
|
alpar@40
|
764 |
|
alpar@40
|
765 |
- The concept descriptor classes also provide a <em>checker class</em>
|
kpeter@50
|
766 |
that makes it possible to check whether a certain implementation of a
|
alpar@40
|
767 |
concept indeed provides all the required features.
|
alpar@40
|
768 |
|
alpar@40
|
769 |
- Finally, They can serve as a skeleton of a new implementation of a concept.
|
alpar@40
|
770 |
*/
|
alpar@40
|
771 |
|
alpar@40
|
772 |
/**
|
alpar@40
|
773 |
@defgroup graph_concepts Graph Structure Concepts
|
alpar@40
|
774 |
@ingroup concept
|
alpar@40
|
775 |
\brief Skeleton and concept checking classes for graph structures
|
alpar@40
|
776 |
|
kpeter@782
|
777 |
This group contains the skeletons and concept checking classes of
|
kpeter@782
|
778 |
graph structures.
|
alpar@40
|
779 |
*/
|
alpar@40
|
780 |
|
kpeter@314
|
781 |
/**
|
kpeter@314
|
782 |
@defgroup map_concepts Map Concepts
|
kpeter@314
|
783 |
@ingroup concept
|
kpeter@314
|
784 |
\brief Skeleton and concept checking classes for maps
|
kpeter@314
|
785 |
|
kpeter@606
|
786 |
This group contains the skeletons and concept checking classes of maps.
|
alpar@40
|
787 |
*/
|
alpar@40
|
788 |
|
alpar@40
|
789 |
/**
|
kpeter@761
|
790 |
@defgroup tools Standalone Utility Applications
|
kpeter@761
|
791 |
|
kpeter@761
|
792 |
Some utility applications are listed here.
|
kpeter@761
|
793 |
|
kpeter@761
|
794 |
The standard compilation procedure (<tt>./configure;make</tt>) will compile
|
kpeter@761
|
795 |
them, as well.
|
kpeter@761
|
796 |
*/
|
kpeter@761
|
797 |
|
kpeter@761
|
798 |
/**
|
alpar@40
|
799 |
\anchor demoprograms
|
alpar@40
|
800 |
|
kpeter@422
|
801 |
@defgroup demos Demo Programs
|
alpar@40
|
802 |
|
alpar@40
|
803 |
Some demo programs are listed here. Their full source codes can be found in
|
alpar@40
|
804 |
the \c demo subdirectory of the source tree.
|
alpar@40
|
805 |
|
ladanyi@611
|
806 |
In order to compile them, use the <tt>make demo</tt> or the
|
ladanyi@611
|
807 |
<tt>make check</tt> commands.
|
alpar@40
|
808 |
*/
|
alpar@40
|
809 |
|
kpeter@422
|
810 |
}
|