doc/groups.dox
author Alpar Juttner <alpar@cs.elte.hu>
Mon, 08 Dec 2008 12:29:00 +0000
changeset 424 346991bf7ddd
parent 406 a578265aa8a6
parent 416 76287c8caa26
child 440 88ed40ad0d4f
child 451 fbd6e04acf44
permissions -rw-r--r--
Update test/CMakeLists.txt and test/Makefile.am
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
kpeter@406
    19
namespace lemon {
kpeter@406
    20
alpar@40
    21
/**
alpar@40
    22
@defgroup datas Data Structures
kpeter@50
    23
This group describes 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
/**
deba@416
    65
@defgroup graph_adaptors Adaptor Classes for graphs
deba@416
    66
@ingroup graphs
deba@416
    67
\brief This group contains several adaptor classes for digraphs and graphs
deba@416
    68
deba@416
    69
The main parts of LEMON are the different graph structures, generic
deba@416
    70
graph algorithms, graph concepts which couple these, and graph
deba@416
    71
adaptors. While the previous notions are more or less clear, the
deba@416
    72
latter one needs further explanation. Graph adaptors are graph classes
deba@416
    73
which serve for considering graph structures in different ways.
deba@416
    74
deba@416
    75
A short example makes this much clearer.  Suppose that we have an
deba@416
    76
instance \c g of a directed graph type say ListDigraph and an algorithm
deba@416
    77
\code
deba@416
    78
template <typename Digraph>
deba@416
    79
int algorithm(const Digraph&);
deba@416
    80
\endcode
deba@416
    81
is needed to run on the reverse oriented graph.  It may be expensive
deba@416
    82
(in time or in memory usage) to copy \c g with the reversed
deba@416
    83
arcs.  In this case, an adaptor class is used, which (according
deba@416
    84
to LEMON digraph concepts) works as a digraph.  The adaptor uses the
deba@416
    85
original digraph structure and digraph operations when methods of the
deba@416
    86
reversed oriented graph are called.  This means that the adaptor have
deba@416
    87
minor memory usage, and do not perform sophisticated algorithmic
deba@416
    88
actions.  The purpose of it is to give a tool for the cases when a
deba@416
    89
graph have to be used in a specific alteration.  If this alteration is
deba@416
    90
obtained by a usual construction like filtering the arc-set or
deba@416
    91
considering a new orientation, then an adaptor is worthwhile to use.
deba@416
    92
To come back to the reverse oriented graph, in this situation
deba@416
    93
\code
deba@416
    94
template<typename Digraph> class ReverseDigraph;
deba@416
    95
\endcode
deba@416
    96
template class can be used. The code looks as follows
deba@416
    97
\code
deba@416
    98
ListDigraph g;
deba@416
    99
ReverseDigraph<ListGraph> rg(g);
deba@416
   100
int result = algorithm(rg);
deba@416
   101
\endcode
deba@416
   102
After running the algorithm, the original graph \c g is untouched.
deba@416
   103
This techniques gives rise to an elegant code, and based on stable
deba@416
   104
graph adaptors, complex algorithms can be implemented easily.
deba@416
   105
deba@416
   106
In flow, circulation and bipartite matching problems, the residual
deba@416
   107
graph is of particular importance. Combining an adaptor implementing
deba@416
   108
this, shortest path algorithms and minimum mean cycle algorithms,
deba@416
   109
a range of weighted and cardinality optimization algorithms can be
deba@416
   110
obtained. For other examples, the interested user is referred to the
deba@416
   111
detailed documentation of particular adaptors.
deba@416
   112
deba@416
   113
The behavior of graph adaptors can be very different. Some of them keep
deba@416
   114
capabilities of the original graph while in other cases this would be
deba@416
   115
meaningless. This means that the concepts that they are models of depend
deba@416
   116
on the graph adaptor, and the wrapped graph(s).
deba@416
   117
If an arc of \c rg is deleted, this is carried out by deleting the
deba@416
   118
corresponding arc of \c g, thus the adaptor modifies the original graph.
deba@416
   119
deba@416
   120
But for a residual graph, this operation has no sense.
deba@416
   121
Let us stand one more example here to simplify your work.
deba@416
   122
RevGraphAdaptor has constructor
deba@416
   123
\code
deba@416
   124
ReverseDigraph(Digraph& digraph);
deba@416
   125
\endcode
deba@416
   126
This means that in a situation, when a <tt>const ListDigraph&</tt>
deba@416
   127
reference to a graph is given, then it have to be instantiated with
deba@416
   128
<tt>Digraph=const ListDigraph</tt>.
deba@416
   129
\code
deba@416
   130
int algorithm1(const ListDigraph& g) {
deba@416
   131
  RevGraphAdaptor<const ListDigraph> rg(g);
deba@416
   132
  return algorithm2(rg);
deba@416
   133
}
deba@416
   134
\endcode
deba@416
   135
*/
deba@416
   136
deba@416
   137
/**
kpeter@50
   138
@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
alpar@40
   139
@ingroup graphs
alpar@40
   140
\brief Graph types between real graphs and graph adaptors.
alpar@40
   141
kpeter@50
   142
This group describes some graph types between real graphs and graph adaptors.
alpar@209
   143
These classes wrap graphs to give new functionality as the adaptors do it.
kpeter@50
   144
On the other hand they are not light-weight structures as the adaptors.
alpar@40
   145
*/
alpar@40
   146
alpar@40
   147
/**
alpar@209
   148
@defgroup maps Maps
alpar@40
   149
@ingroup datas
kpeter@50
   150
\brief Map structures implemented in LEMON.
alpar@40
   151
kpeter@50
   152
This group describes the map structures implemented in LEMON.
kpeter@50
   153
kpeter@314
   154
LEMON provides several special purpose maps and map adaptors that e.g. combine
alpar@40
   155
new maps from existing ones.
kpeter@314
   156
kpeter@314
   157
<b>See also:</b> \ref map_concepts "Map Concepts".
alpar@40
   158
*/
alpar@40
   159
alpar@40
   160
/**
alpar@209
   161
@defgroup graph_maps Graph Maps
alpar@40
   162
@ingroup maps
kpeter@83
   163
\brief Special graph-related maps.
alpar@40
   164
kpeter@50
   165
This group describes maps that are specifically designed to assign
kpeter@406
   166
values to the nodes and arcs/edges of graphs.
kpeter@406
   167
kpeter@406
   168
If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
kpeter@406
   169
\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
alpar@40
   170
*/
alpar@40
   171
alpar@40
   172
/**
alpar@40
   173
\defgroup map_adaptors Map Adaptors
alpar@40
   174
\ingroup maps
alpar@40
   175
\brief Tools to create new maps from existing ones
alpar@40
   176
kpeter@50
   177
This group describes map adaptors that are used to create "implicit"
kpeter@50
   178
maps from other maps.
alpar@40
   179
kpeter@406
   180
Most of them are \ref concepts::ReadMap "read-only maps".
kpeter@83
   181
They can make arithmetic and logical operations between one or two maps
kpeter@83
   182
(negation, shifting, addition, multiplication, logical 'and', 'or',
kpeter@83
   183
'not' etc.) or e.g. convert a map to another one of different Value type.
alpar@40
   184
kpeter@50
   185
The typical usage of this classes is passing implicit maps to
alpar@40
   186
algorithms.  If a function type algorithm is called then the function
alpar@40
   187
type map adaptors can be used comfortable. For example let's see the
kpeter@314
   188
usage of map adaptors with the \c graphToEps() function.
alpar@40
   189
\code
alpar@40
   190
  Color nodeColor(int deg) {
alpar@40
   191
    if (deg >= 2) {
alpar@40
   192
      return Color(0.5, 0.0, 0.5);
alpar@40
   193
    } else if (deg == 1) {
alpar@40
   194
      return Color(1.0, 0.5, 1.0);
alpar@40
   195
    } else {
alpar@40
   196
      return Color(0.0, 0.0, 0.0);
alpar@40
   197
    }
alpar@40
   198
  }
alpar@209
   199
kpeter@83
   200
  Digraph::NodeMap<int> degree_map(graph);
alpar@209
   201
kpeter@314
   202
  graphToEps(graph, "graph.eps")
alpar@40
   203
    .coords(coords).scaleToA4().undirected()
kpeter@83
   204
    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
alpar@40
   205
    .run();
alpar@209
   206
\endcode
kpeter@83
   207
The \c functorToMap() function makes an \c int to \c Color map from the
kpeter@314
   208
\c nodeColor() function. The \c composeMap() compose the \c degree_map
kpeter@83
   209
and the previously created map. The composed map is a proper function to
kpeter@83
   210
get the color of each node.
alpar@40
   211
alpar@40
   212
The usage with class type algorithms is little bit harder. In this
alpar@40
   213
case the function type map adaptors can not be used, because the
kpeter@50
   214
function map adaptors give back temporary objects.
alpar@40
   215
\code
kpeter@83
   216
  Digraph graph;
kpeter@83
   217
kpeter@83
   218
  typedef Digraph::ArcMap<double> DoubleArcMap;
kpeter@83
   219
  DoubleArcMap length(graph);
kpeter@83
   220
  DoubleArcMap speed(graph);
kpeter@83
   221
kpeter@83
   222
  typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
alpar@40
   223
  TimeMap time(length, speed);
alpar@209
   224
kpeter@83
   225
  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
alpar@40
   226
  dijkstra.run(source, target);
alpar@40
   227
\endcode
kpeter@83
   228
We have a length map and a maximum speed map on the arcs of a digraph.
kpeter@83
   229
The minimum time to pass the arc can be calculated as the division of
kpeter@83
   230
the two maps which can be done implicitly with the \c DivMap template
alpar@40
   231
class. We use the implicit minimum time map as the length map of the
alpar@40
   232
\c Dijkstra algorithm.
alpar@40
   233
*/
alpar@40
   234
alpar@40
   235
/**
alpar@209
   236
@defgroup matrices Matrices
alpar@40
   237
@ingroup datas
kpeter@50
   238
\brief Two dimensional data storages implemented in LEMON.
alpar@40
   239
kpeter@50
   240
This group describes two dimensional data storages implemented in LEMON.
alpar@40
   241
*/
alpar@40
   242
alpar@40
   243
/**
alpar@40
   244
@defgroup paths Path Structures
alpar@40
   245
@ingroup datas
kpeter@318
   246
\brief %Path structures implemented in LEMON.
alpar@40
   247
kpeter@50
   248
This group describes the path structures implemented in LEMON.
alpar@40
   249
kpeter@50
   250
LEMON provides flexible data structures to work with paths.
kpeter@50
   251
All of them have similar interfaces and they can be copied easily with
kpeter@50
   252
assignment operators and copy constructors. This makes it easy and
alpar@40
   253
efficient to have e.g. the Dijkstra algorithm to store its result in
alpar@40
   254
any kind of path structure.
alpar@40
   255
alpar@40
   256
\sa lemon::concepts::Path
alpar@40
   257
*/
alpar@40
   258
alpar@40
   259
/**
alpar@40
   260
@defgroup auxdat Auxiliary Data Structures
alpar@40
   261
@ingroup datas
kpeter@50
   262
\brief Auxiliary data structures implemented in LEMON.
alpar@40
   263
kpeter@50
   264
This group describes some data structures implemented in LEMON in
alpar@40
   265
order to make it easier to implement combinatorial algorithms.
alpar@40
   266
*/
alpar@40
   267
alpar@40
   268
/**
alpar@40
   269
@defgroup algs Algorithms
alpar@40
   270
\brief This group describes the several algorithms
alpar@40
   271
implemented in LEMON.
alpar@40
   272
alpar@40
   273
This group describes the several algorithms
alpar@40
   274
implemented in LEMON.
alpar@40
   275
*/
alpar@40
   276
alpar@40
   277
/**
alpar@40
   278
@defgroup search Graph Search
alpar@40
   279
@ingroup algs
kpeter@50
   280
\brief Common graph search algorithms.
alpar@40
   281
kpeter@406
   282
This group describes the common graph search algorithms, namely
kpeter@406
   283
\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
alpar@40
   284
*/
alpar@40
   285
alpar@40
   286
/**
kpeter@314
   287
@defgroup shortest_path Shortest Path Algorithms
alpar@40
   288
@ingroup algs
kpeter@50
   289
\brief Algorithms for finding shortest paths.
alpar@40
   290
kpeter@406
   291
This group describes the algorithms for finding shortest paths in digraphs.
kpeter@406
   292
kpeter@406
   293
 - \ref Dijkstra algorithm for finding shortest paths from a source node
kpeter@406
   294
   when all arc lengths are non-negative.
kpeter@406
   295
 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
kpeter@406
   296
   from a source node when arc lenghts can be either positive or negative,
kpeter@406
   297
   but the digraph should not contain directed cycles with negative total
kpeter@406
   298
   length.
kpeter@406
   299
 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
kpeter@406
   300
   for solving the \e all-pairs \e shortest \e paths \e problem when arc
kpeter@406
   301
   lenghts can be either positive or negative, but the digraph should
kpeter@406
   302
   not contain directed cycles with negative total length.
kpeter@406
   303
 - \ref Suurballe A successive shortest path algorithm for finding
kpeter@406
   304
   arc-disjoint paths between two nodes having minimum total length.
alpar@40
   305
*/
alpar@40
   306
alpar@209
   307
/**
kpeter@314
   308
@defgroup max_flow Maximum Flow Algorithms
alpar@209
   309
@ingroup algs
kpeter@50
   310
\brief Algorithms for finding maximum flows.
alpar@40
   311
alpar@40
   312
This group describes the algorithms for finding maximum flows and
alpar@40
   313
feasible circulations.
alpar@40
   314
kpeter@406
   315
The \e maximum \e flow \e problem is to find a flow of maximum value between
kpeter@406
   316
a single source and a single target. Formally, there is a \f$G=(V,A)\f$
kpeter@406
   317
digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
kpeter@406
   318
\f$s, t \in V\f$ source and target nodes.
kpeter@406
   319
A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
kpeter@406
   320
following optimization problem.
alpar@40
   321
kpeter@406
   322
\f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]
kpeter@406
   323
\f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)
kpeter@406
   324
    \qquad \forall v\in V\setminus\{s,t\} \f]
kpeter@406
   325
\f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]
alpar@40
   326
kpeter@50
   327
LEMON contains several algorithms for solving maximum flow problems:
kpeter@406
   328
- \ref EdmondsKarp Edmonds-Karp algorithm.
kpeter@406
   329
- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
kpeter@406
   330
- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
kpeter@406
   331
- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
alpar@40
   332
kpeter@406
   333
In most cases the \ref Preflow "Preflow" algorithm provides the
kpeter@406
   334
fastest method for computing a maximum flow. All implementations
kpeter@406
   335
provides functions to also query the minimum cut, which is the dual
kpeter@406
   336
problem of the maximum flow.
alpar@40
   337
*/
alpar@40
   338
alpar@40
   339
/**
kpeter@314
   340
@defgroup min_cost_flow Minimum Cost Flow Algorithms
alpar@40
   341
@ingroup algs
alpar@40
   342
kpeter@50
   343
\brief Algorithms for finding minimum cost flows and circulations.
alpar@40
   344
alpar@40
   345
This group describes the algorithms for finding minimum cost flows and
alpar@209
   346
circulations.
kpeter@406
   347
kpeter@406
   348
The \e minimum \e cost \e flow \e problem is to find a feasible flow of
kpeter@406
   349
minimum total cost from a set of supply nodes to a set of demand nodes
kpeter@406
   350
in a network with capacity constraints and arc costs.
kpeter@406
   351
Formally, let \f$G=(V,A)\f$ be a digraph,
kpeter@406
   352
\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
kpeter@406
   353
upper bounds for the flow values on the arcs,
kpeter@406
   354
\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
kpeter@406
   355
on the arcs, and
kpeter@406
   356
\f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
kpeter@406
   357
of the nodes.
kpeter@406
   358
A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
kpeter@406
   359
the following optimization problem.
kpeter@406
   360
kpeter@406
   361
\f[ \min\sum_{a\in A} f(a) cost(a) \f]
kpeter@406
   362
\f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =
kpeter@406
   363
    supply(v) \qquad \forall v\in V \f]
kpeter@406
   364
\f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]
kpeter@406
   365
kpeter@406
   366
LEMON contains several algorithms for solving minimum cost flow problems:
kpeter@406
   367
 - \ref CycleCanceling Cycle-canceling algorithms.
kpeter@406
   368
 - \ref CapacityScaling Successive shortest path algorithm with optional
kpeter@406
   369
   capacity scaling.
kpeter@406
   370
 - \ref CostScaling Push-relabel and augment-relabel algorithms based on
kpeter@406
   371
   cost scaling.
kpeter@406
   372
 - \ref NetworkSimplex Primal network simplex algorithm with various
kpeter@406
   373
   pivot strategies.
alpar@40
   374
*/
alpar@40
   375
alpar@40
   376
/**
kpeter@314
   377
@defgroup min_cut Minimum Cut Algorithms
alpar@209
   378
@ingroup algs
alpar@40
   379
kpeter@50
   380
\brief Algorithms for finding minimum cut in graphs.
alpar@40
   381
alpar@40
   382
This group describes the algorithms for finding minimum cut in graphs.
alpar@40
   383
kpeter@406
   384
The \e minimum \e cut \e problem is to find a non-empty and non-complete
kpeter@406
   385
\f$X\f$ subset of the nodes with minimum overall capacity on
kpeter@406
   386
outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
kpeter@406
   387
\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
kpeter@50
   388
cut is the \f$X\f$ solution of the next optimization problem:
alpar@40
   389
alpar@210
   390
\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
kpeter@406
   391
    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
alpar@40
   392
kpeter@50
   393
LEMON contains several algorithms related to minimum cut problems:
alpar@40
   394
kpeter@406
   395
- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
kpeter@406
   396
  in directed graphs.
kpeter@406
   397
- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
kpeter@406
   398
  calculating minimum cut in undirected graphs.
kpeter@406
   399
- \ref GomoryHuTree "Gomory-Hu tree computation" for calculating
kpeter@406
   400
  all-pairs minimum cut in undirected graphs.
alpar@40
   401
alpar@40
   402
If you want to find minimum cut just between two distinict nodes,
kpeter@406
   403
see the \ref max_flow "maximum flow problem".
alpar@40
   404
*/
alpar@40
   405
alpar@40
   406
/**
kpeter@314
   407
@defgroup graph_prop Connectivity and Other Graph Properties
alpar@40
   408
@ingroup algs
kpeter@50
   409
\brief Algorithms for discovering the graph properties
alpar@40
   410
kpeter@50
   411
This group describes the algorithms for discovering the graph properties
kpeter@50
   412
like connectivity, bipartiteness, euler property, simplicity etc.
alpar@40
   413
alpar@40
   414
\image html edge_biconnected_components.png
alpar@40
   415
\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
alpar@40
   416
*/
alpar@40
   417
alpar@40
   418
/**
kpeter@314
   419
@defgroup planar Planarity Embedding and Drawing
alpar@40
   420
@ingroup algs
kpeter@50
   421
\brief Algorithms for planarity checking, embedding and drawing
alpar@40
   422
alpar@210
   423
This group describes the algorithms for planarity checking,
alpar@210
   424
embedding and drawing.
alpar@40
   425
alpar@40
   426
\image html planar.png
alpar@40
   427
\image latex planar.eps "Plane graph" width=\textwidth
alpar@40
   428
*/
alpar@40
   429
alpar@40
   430
/**
kpeter@314
   431
@defgroup matching Matching Algorithms
alpar@40
   432
@ingroup algs
kpeter@50
   433
\brief Algorithms for finding matchings in graphs and bipartite graphs.
alpar@40
   434
kpeter@50
   435
This group contains algorithm objects and functions to calculate
alpar@40
   436
matchings in graphs and bipartite graphs. The general matching problem is
kpeter@83
   437
finding a subset of the arcs which does not shares common endpoints.
alpar@209
   438
alpar@40
   439
There are several different algorithms for calculate matchings in
alpar@40
   440
graphs.  The matching problems in bipartite graphs are generally
alpar@40
   441
easier than in general graphs. The goal of the matching optimization
kpeter@406
   442
can be finding maximum cardinality, maximum weight or minimum cost
alpar@40
   443
matching. The search can be constrained to find perfect or
alpar@40
   444
maximum cardinality matching.
alpar@40
   445
kpeter@406
   446
The matching algorithms implemented in LEMON:
kpeter@406
   447
- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
kpeter@406
   448
  for calculating maximum cardinality matching in bipartite graphs.
kpeter@406
   449
- \ref PrBipartiteMatching Push-relabel algorithm
kpeter@406
   450
  for calculating maximum cardinality matching in bipartite graphs.
kpeter@406
   451
- \ref MaxWeightedBipartiteMatching
kpeter@406
   452
  Successive shortest path algorithm for calculating maximum weighted
kpeter@406
   453
  matching and maximum weighted bipartite matching in bipartite graphs.
kpeter@406
   454
- \ref MinCostMaxBipartiteMatching
kpeter@406
   455
  Successive shortest path algorithm for calculating minimum cost maximum
kpeter@406
   456
  matching in bipartite graphs.
kpeter@406
   457
- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
kpeter@406
   458
  maximum cardinality matching in general graphs.
kpeter@406
   459
- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
kpeter@406
   460
  maximum weighted matching in general graphs.
kpeter@406
   461
- \ref MaxWeightedPerfectMatching
kpeter@406
   462
  Edmond's blossom shrinking algorithm for calculating maximum weighted
kpeter@406
   463
  perfect matching in general graphs.
alpar@40
   464
alpar@40
   465
\image html bipartite_matching.png
alpar@40
   466
\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
alpar@40
   467
*/
alpar@40
   468
alpar@40
   469
/**
kpeter@314
   470
@defgroup spantree Minimum Spanning Tree Algorithms
alpar@40
   471
@ingroup algs
kpeter@50
   472
\brief Algorithms for finding a minimum cost spanning tree in a graph.
alpar@40
   473
kpeter@50
   474
This group describes the algorithms for finding a minimum cost spanning
kpeter@406
   475
tree in a graph.
alpar@40
   476
*/
alpar@40
   477
alpar@40
   478
/**
kpeter@314
   479
@defgroup auxalg Auxiliary Algorithms
alpar@40
   480
@ingroup algs
kpeter@50
   481
\brief Auxiliary algorithms implemented in LEMON.
alpar@40
   482
kpeter@50
   483
This group describes some algorithms implemented in LEMON
kpeter@50
   484
in order to make it easier to implement complex algorithms.
alpar@40
   485
*/
alpar@40
   486
alpar@40
   487
/**
kpeter@314
   488
@defgroup approx Approximation Algorithms
kpeter@314
   489
@ingroup algs
kpeter@50
   490
\brief Approximation algorithms.
alpar@40
   491
kpeter@50
   492
This group describes the approximation and heuristic algorithms
kpeter@50
   493
implemented in LEMON.
alpar@40
   494
*/
alpar@40
   495
alpar@40
   496
/**
alpar@40
   497
@defgroup gen_opt_group General Optimization Tools
alpar@40
   498
\brief This group describes some general optimization frameworks
alpar@40
   499
implemented in LEMON.
alpar@40
   500
alpar@40
   501
This group describes some general optimization frameworks
alpar@40
   502
implemented in LEMON.
alpar@40
   503
*/
alpar@40
   504
alpar@40
   505
/**
kpeter@314
   506
@defgroup lp_group Lp and Mip Solvers
alpar@40
   507
@ingroup gen_opt_group
alpar@40
   508
\brief Lp and Mip solver interfaces for LEMON.
alpar@40
   509
alpar@40
   510
This group describes Lp and Mip solver interfaces for LEMON. The
alpar@40
   511
various LP solvers could be used in the same manner with this
alpar@40
   512
interface.
alpar@40
   513
*/
alpar@40
   514
alpar@209
   515
/**
kpeter@314
   516
@defgroup lp_utils Tools for Lp and Mip Solvers
alpar@40
   517
@ingroup lp_group
kpeter@50
   518
\brief Helper tools to the Lp and Mip solvers.
alpar@40
   519
alpar@40
   520
This group adds some helper tools to general optimization framework
alpar@40
   521
implemented in LEMON.
alpar@40
   522
*/
alpar@40
   523
alpar@40
   524
/**
alpar@40
   525
@defgroup metah Metaheuristics
alpar@40
   526
@ingroup gen_opt_group
alpar@40
   527
\brief Metaheuristics for LEMON library.
alpar@40
   528
kpeter@50
   529
This group describes some metaheuristic optimization tools.
alpar@40
   530
*/
alpar@40
   531
alpar@40
   532
/**
alpar@209
   533
@defgroup utils Tools and Utilities
kpeter@50
   534
\brief Tools and utilities for programming in LEMON
alpar@40
   535
kpeter@50
   536
Tools and utilities for programming in LEMON.
alpar@40
   537
*/
alpar@40
   538
alpar@40
   539
/**
alpar@40
   540
@defgroup gutils Basic Graph Utilities
alpar@40
   541
@ingroup utils
kpeter@50
   542
\brief Simple basic graph utilities.
alpar@40
   543
alpar@40
   544
This group describes some simple basic graph utilities.
alpar@40
   545
*/
alpar@40
   546
alpar@40
   547
/**
alpar@40
   548
@defgroup misc Miscellaneous Tools
alpar@40
   549
@ingroup utils
kpeter@50
   550
\brief Tools for development, debugging and testing.
kpeter@50
   551
kpeter@50
   552
This group describes several useful tools for development,
alpar@40
   553
debugging and testing.
alpar@40
   554
*/
alpar@40
   555
alpar@40
   556
/**
kpeter@314
   557
@defgroup timecount Time Measuring and Counting
alpar@40
   558
@ingroup misc
kpeter@50
   559
\brief Simple tools for measuring the performance of algorithms.
kpeter@50
   560
kpeter@50
   561
This group describes simple tools for measuring the performance
alpar@40
   562
of algorithms.
alpar@40
   563
*/
alpar@40
   564
alpar@40
   565
/**
alpar@40
   566
@defgroup exceptions Exceptions
alpar@40
   567
@ingroup utils
kpeter@50
   568
\brief Exceptions defined in LEMON.
kpeter@50
   569
kpeter@50
   570
This group describes the exceptions defined in LEMON.
alpar@40
   571
*/
alpar@40
   572
alpar@40
   573
/**
alpar@40
   574
@defgroup io_group Input-Output
kpeter@50
   575
\brief Graph Input-Output methods
alpar@40
   576
alpar@209
   577
This group describes the tools for importing and exporting graphs
kpeter@314
   578
and graph related data. Now it supports the \ref lgf-format
kpeter@314
   579
"LEMON Graph Format", the \c DIMACS format and the encapsulated
kpeter@314
   580
postscript (EPS) format.
alpar@40
   581
*/
alpar@40
   582
alpar@40
   583
/**
kpeter@351
   584
@defgroup lemon_io LEMON Graph Format
alpar@40
   585
@ingroup io_group
kpeter@314
   586
\brief Reading and writing LEMON Graph Format.
alpar@40
   587
alpar@210
   588
This group describes methods for reading and writing
ladanyi@236
   589
\ref lgf-format "LEMON Graph Format".
alpar@40
   590
*/
alpar@40
   591
alpar@40
   592
/**
kpeter@314
   593
@defgroup eps_io Postscript Exporting
alpar@40
   594
@ingroup io_group
alpar@40
   595
\brief General \c EPS drawer and graph exporter
alpar@40
   596
kpeter@50
   597
This group describes general \c EPS drawing methods and special
alpar@209
   598
graph exporting tools.
alpar@40
   599
*/
alpar@40
   600
alpar@40
   601
/**
kpeter@388
   602
@defgroup dimacs_group DIMACS format
kpeter@388
   603
@ingroup io_group
kpeter@388
   604
\brief Read and write files in DIMACS format
kpeter@388
   605
kpeter@388
   606
Tools to read a digraph from or write it to a file in DIMACS format data.
kpeter@388
   607
*/
kpeter@388
   608
kpeter@388
   609
/**
kpeter@351
   610
@defgroup nauty_group NAUTY Format
kpeter@351
   611
@ingroup io_group
kpeter@351
   612
\brief Read \e Nauty format
kpeter@388
   613
kpeter@351
   614
Tool to read graphs from \e Nauty format data.
kpeter@351
   615
*/
kpeter@351
   616
kpeter@351
   617
/**
alpar@40
   618
@defgroup concept Concepts
alpar@40
   619
\brief Skeleton classes and concept checking classes
alpar@40
   620
alpar@40
   621
This group describes the data/algorithm skeletons and concept checking
alpar@40
   622
classes implemented in LEMON.
alpar@40
   623
alpar@40
   624
The purpose of the classes in this group is fourfold.
alpar@209
   625
kpeter@318
   626
- These classes contain the documentations of the %concepts. In order
alpar@40
   627
  to avoid document multiplications, an implementation of a concept
alpar@40
   628
  simply refers to the corresponding concept class.
alpar@40
   629
alpar@40
   630
- These classes declare every functions, <tt>typedef</tt>s etc. an
kpeter@318
   631
  implementation of the %concepts should provide, however completely
alpar@40
   632
  without implementations and real data structures behind the
alpar@40
   633
  interface. On the other hand they should provide nothing else. All
alpar@40
   634
  the algorithms working on a data structure meeting a certain concept
alpar@40
   635
  should compile with these classes. (Though it will not run properly,
alpar@40
   636
  of course.) In this way it is easily to check if an algorithm
alpar@40
   637
  doesn't use any extra feature of a certain implementation.
alpar@40
   638
alpar@40
   639
- The concept descriptor classes also provide a <em>checker class</em>
kpeter@50
   640
  that makes it possible to check whether a certain implementation of a
alpar@40
   641
  concept indeed provides all the required features.
alpar@40
   642
alpar@40
   643
- Finally, They can serve as a skeleton of a new implementation of a concept.
alpar@40
   644
*/
alpar@40
   645
alpar@40
   646
/**
alpar@40
   647
@defgroup graph_concepts Graph Structure Concepts
alpar@40
   648
@ingroup concept
alpar@40
   649
\brief Skeleton and concept checking classes for graph structures
alpar@40
   650
kpeter@50
   651
This group describes the skeletons and concept checking classes of LEMON's
alpar@40
   652
graph structures and helper classes used to implement these.
alpar@40
   653
*/
alpar@40
   654
kpeter@314
   655
/**
kpeter@314
   656
@defgroup map_concepts Map Concepts
kpeter@314
   657
@ingroup concept
kpeter@314
   658
\brief Skeleton and concept checking classes for maps
kpeter@314
   659
kpeter@314
   660
This group describes the skeletons and concept checking classes of maps.
alpar@40
   661
*/
alpar@40
   662
alpar@40
   663
/**
alpar@40
   664
\anchor demoprograms
alpar@40
   665
kpeter@406
   666
@defgroup demos Demo Programs
alpar@40
   667
alpar@40
   668
Some demo programs are listed here. Their full source codes can be found in
alpar@40
   669
the \c demo subdirectory of the source tree.
alpar@40
   670
alpar@41
   671
It order to compile them, use <tt>--enable-demo</tt> configure option when
alpar@41
   672
build the library.
alpar@40
   673
*/
alpar@40
   674
alpar@40
   675
/**
kpeter@406
   676
@defgroup tools Standalone Utility Applications
alpar@40
   677
alpar@209
   678
Some utility applications are listed here.
alpar@40
   679
alpar@40
   680
The standard compilation procedure (<tt>./configure;make</tt>) will compile
alpar@209
   681
them, as well.
alpar@40
   682
*/
alpar@40
   683
kpeter@406
   684
}