doc/groups.dox
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
parent 440 88ed40ad0d4f
parent 451 fbd6e04acf44
child 559 c5fd2d996909
child 609 e6927fe719e6
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

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