doc/groups.dox
author Akos Ladanyi <ladanyi@tmit.bme.hu>
Mon, 27 Apr 2009 18:03:18 +0100
changeset 635 89705c452130
parent 590 b61354458b59
parent 609 e6927fe719e6
child 640 6c408d864fa1
permissions -rw-r--r--
Add CPLEX_ROOT_DIR variable to FindCPLEX (#277)
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@559
    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@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@559
   145
This group contains 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@559
   155
This group contains 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@559
   168
This group contains 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@559
   180
This group contains 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@559
   243
This group contains 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@559
   251
This group contains 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@559
   267
This group contains 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
kpeter@559
   273
\brief This group contains the several algorithms
alpar@40
   274
implemented in LEMON.
alpar@40
   275
kpeter@559
   276
This group contains 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@559
   285
This group contains 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@559
   294
This group contains 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
kpeter@559
   315
This group contains 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@609
   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@609
   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@609
   325
\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
kpeter@609
   326
\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
kpeter@609
   327
    \quad \forall u\in V\setminus\{s,t\} \f]
kpeter@609
   328
\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\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
kpeter@609
   348
This group contains 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@609
   353
in a network with capacity constraints (lower and upper bounds)
kpeter@609
   354
and arc costs.
kpeter@406
   355
Formally, let \f$G=(V,A)\f$ be a digraph,
kpeter@406
   356
\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
kpeter@609
   357
upper bounds for the flow values on the arcs, for which
kpeter@609
   358
\f$0 \leq lower(uv) \leq upper(uv)\f$ holds for all \f$uv\in A\f$.
kpeter@406
   359
\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
kpeter@609
   360
on the arcs, and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
kpeter@609
   361
signed supply values of the nodes.
kpeter@609
   362
If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
kpeter@609
   363
supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
kpeter@609
   364
\f$-sup(u)\f$ demand.
kpeter@609
   365
A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}^+_0\f$ solution
kpeter@609
   366
of the following optimization problem.
kpeter@406
   367
kpeter@609
   368
\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
kpeter@609
   369
\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
kpeter@609
   370
    sup(u) \quad \forall u\in V \f]
kpeter@609
   371
\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
kpeter@406
   372
kpeter@609
   373
The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
kpeter@609
   374
zero or negative in order to have a feasible solution (since the sum
kpeter@609
   375
of the expressions on the left-hand side of the inequalities is zero).
kpeter@609
   376
It means that the total demand must be greater or equal to the total
kpeter@609
   377
supply and all the supplies have to be carried out from the supply nodes,
kpeter@609
   378
but there could be demands that are not satisfied.
kpeter@609
   379
If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
kpeter@609
   380
constraints have to be satisfied with equality, i.e. all demands
kpeter@609
   381
have to be satisfied and all supplies have to be used.
kpeter@609
   382
kpeter@609
   383
If you need the opposite inequalities in the supply/demand constraints
kpeter@609
   384
(i.e. the total demand is less than the total supply and all the demands
kpeter@609
   385
have to be satisfied while there could be supplies that are not used),
kpeter@609
   386
then you could easily transform the problem to the above form by reversing
kpeter@609
   387
the direction of the arcs and taking the negative of the supply values
kpeter@609
   388
(e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
kpeter@609
   389
However \ref NetworkSimplex algorithm also supports this form directly
kpeter@609
   390
for the sake of convenience.
kpeter@609
   391
kpeter@609
   392
A feasible solution for this problem can be found using \ref Circulation.
kpeter@609
   393
kpeter@609
   394
Note that the above formulation is actually more general than the usual
kpeter@609
   395
definition of the minimum cost flow problem, in which strict equalities
kpeter@609
   396
are required in the supply/demand contraints, i.e.
kpeter@609
   397
kpeter@609
   398
\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
kpeter@609
   399
    sup(u) \quad \forall u\in V. \f]
kpeter@609
   400
kpeter@609
   401
However if the sum of the supply values is zero, then these two problems
kpeter@609
   402
are equivalent. So if you need the equality form, you have to ensure this
kpeter@609
   403
additional contraint for the algorithms.
kpeter@609
   404
kpeter@609
   405
The dual solution of the minimum cost flow problem is represented by node 
kpeter@609
   406
potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
kpeter@609
   407
An \f$f: A\rightarrow\mathbf{Z}^+_0\f$ feasible solution of the problem
kpeter@609
   408
is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
kpeter@609
   409
node potentials the following \e complementary \e slackness optimality
kpeter@609
   410
conditions hold.
kpeter@609
   411
kpeter@609
   412
 - For all \f$uv\in A\f$ arcs:
kpeter@609
   413
   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
kpeter@609
   414
   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
kpeter@609
   415
   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
kpeter@609
   416
 - For all \f$u\in V\f$:
kpeter@609
   417
   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
kpeter@609
   418
     then \f$\pi(u)=0\f$.
kpeter@609
   419
 
kpeter@609
   420
Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
kpeter@609
   421
\f$uv\in A\f$ with respect to the node potentials \f$\pi\f$, i.e.
kpeter@609
   422
\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
kpeter@609
   423
kpeter@609
   424
All algorithms provide dual solution (node potentials) as well
kpeter@609
   425
if an optimal flow is found.
kpeter@609
   426
kpeter@609
   427
LEMON contains several algorithms for solving minimum cost flow problems.
kpeter@609
   428
 - \ref NetworkSimplex Primal Network Simplex algorithm with various
kpeter@609
   429
   pivot strategies.
kpeter@609
   430
 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
kpeter@609
   431
   cost scaling.
kpeter@609
   432
 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
kpeter@406
   433
   capacity scaling.
kpeter@609
   434
 - \ref CancelAndTighten The Cancel and Tighten algorithm.
kpeter@609
   435
 - \ref CycleCanceling Cycle-Canceling algorithms.
kpeter@609
   436
kpeter@609
   437
Most of these implementations support the general inequality form of the
kpeter@609
   438
minimum cost flow problem, but CancelAndTighten and CycleCanceling
kpeter@609
   439
only support the equality form due to the primal method they use.
kpeter@609
   440
kpeter@609
   441
In general NetworkSimplex is the most efficient implementation,
kpeter@609
   442
but in special cases other algorithms could be faster.
kpeter@609
   443
For example, if the total supply and/or capacities are rather small,
kpeter@609
   444
CapacityScaling is usually the fastest algorithm (without effective scaling).
alpar@40
   445
*/
alpar@40
   446
alpar@40
   447
/**
kpeter@314
   448
@defgroup min_cut Minimum Cut Algorithms
alpar@209
   449
@ingroup algs
alpar@40
   450
kpeter@50
   451
\brief Algorithms for finding minimum cut in graphs.
alpar@40
   452
kpeter@559
   453
This group contains the algorithms for finding minimum cut in graphs.
alpar@40
   454
kpeter@406
   455
The \e minimum \e cut \e problem is to find a non-empty and non-complete
kpeter@406
   456
\f$X\f$ subset of the nodes with minimum overall capacity on
kpeter@406
   457
outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
kpeter@406
   458
\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
kpeter@50
   459
cut is the \f$X\f$ solution of the next optimization problem:
alpar@40
   460
alpar@210
   461
\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
kpeter@406
   462
    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
alpar@40
   463
kpeter@50
   464
LEMON contains several algorithms related to minimum cut problems:
alpar@40
   465
kpeter@406
   466
- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
kpeter@406
   467
  in directed graphs.
kpeter@406
   468
- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
kpeter@406
   469
  calculating minimum cut in undirected graphs.
kpeter@559
   470
- \ref GomoryHu "Gomory-Hu tree computation" for calculating
kpeter@406
   471
  all-pairs minimum cut in undirected graphs.
alpar@40
   472
alpar@40
   473
If you want to find minimum cut just between two distinict nodes,
kpeter@406
   474
see the \ref max_flow "maximum flow problem".
alpar@40
   475
*/
alpar@40
   476
alpar@40
   477
/**
kpeter@586
   478
@defgroup graph_properties Connectivity and Other Graph Properties
alpar@40
   479
@ingroup algs
kpeter@50
   480
\brief Algorithms for discovering the graph properties
alpar@40
   481
kpeter@559
   482
This group contains the algorithms for discovering the graph properties
kpeter@50
   483
like connectivity, bipartiteness, euler property, simplicity etc.
alpar@40
   484
alpar@40
   485
\image html edge_biconnected_components.png
alpar@40
   486
\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
alpar@40
   487
*/
alpar@40
   488
alpar@40
   489
/**
kpeter@314
   490
@defgroup planar Planarity Embedding and Drawing
alpar@40
   491
@ingroup algs
kpeter@50
   492
\brief Algorithms for planarity checking, embedding and drawing
alpar@40
   493
kpeter@559
   494
This group contains the algorithms for planarity checking,
alpar@210
   495
embedding and drawing.
alpar@40
   496
alpar@40
   497
\image html planar.png
alpar@40
   498
\image latex planar.eps "Plane graph" width=\textwidth
alpar@40
   499
*/
alpar@40
   500
alpar@40
   501
/**
kpeter@314
   502
@defgroup matching Matching Algorithms
alpar@40
   503
@ingroup algs
kpeter@50
   504
\brief Algorithms for finding matchings in graphs and bipartite graphs.
alpar@40
   505
kpeter@590
   506
This group contains the algorithms for calculating
alpar@40
   507
matchings in graphs and bipartite graphs. The general matching problem is
kpeter@590
   508
finding a subset of the edges for which each node has at most one incident
kpeter@590
   509
edge.
alpar@209
   510
alpar@40
   511
There are several different algorithms for calculate matchings in
alpar@40
   512
graphs.  The matching problems in bipartite graphs are generally
alpar@40
   513
easier than in general graphs. The goal of the matching optimization
kpeter@406
   514
can be finding maximum cardinality, maximum weight or minimum cost
alpar@40
   515
matching. The search can be constrained to find perfect or
alpar@40
   516
maximum cardinality matching.
alpar@40
   517
kpeter@406
   518
The matching algorithms implemented in LEMON:
kpeter@406
   519
- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
kpeter@406
   520
  for calculating maximum cardinality matching in bipartite graphs.
kpeter@406
   521
- \ref PrBipartiteMatching Push-relabel algorithm
kpeter@406
   522
  for calculating maximum cardinality matching in bipartite graphs.
kpeter@406
   523
- \ref MaxWeightedBipartiteMatching
kpeter@406
   524
  Successive shortest path algorithm for calculating maximum weighted
kpeter@406
   525
  matching and maximum weighted bipartite matching in bipartite graphs.
kpeter@406
   526
- \ref MinCostMaxBipartiteMatching
kpeter@406
   527
  Successive shortest path algorithm for calculating minimum cost maximum
kpeter@406
   528
  matching in bipartite graphs.
kpeter@406
   529
- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
kpeter@406
   530
  maximum cardinality matching in general graphs.
kpeter@406
   531
- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
kpeter@406
   532
  maximum weighted matching in general graphs.
kpeter@406
   533
- \ref MaxWeightedPerfectMatching
kpeter@406
   534
  Edmond's blossom shrinking algorithm for calculating maximum weighted
kpeter@406
   535
  perfect matching in general graphs.
alpar@40
   536
alpar@40
   537
\image html bipartite_matching.png
alpar@40
   538
\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
alpar@40
   539
*/
alpar@40
   540
alpar@40
   541
/**
kpeter@314
   542
@defgroup spantree Minimum Spanning Tree Algorithms
alpar@40
   543
@ingroup algs
kpeter@50
   544
\brief Algorithms for finding a minimum cost spanning tree in a graph.
alpar@40
   545
kpeter@559
   546
This group contains the algorithms for finding a minimum cost spanning
kpeter@406
   547
tree in a graph.
alpar@40
   548
*/
alpar@40
   549
alpar@40
   550
/**
kpeter@314
   551
@defgroup auxalg Auxiliary Algorithms
alpar@40
   552
@ingroup algs
kpeter@50
   553
\brief Auxiliary algorithms implemented in LEMON.
alpar@40
   554
kpeter@559
   555
This group contains some algorithms implemented in LEMON
kpeter@50
   556
in order to make it easier to implement complex algorithms.
alpar@40
   557
*/
alpar@40
   558
alpar@40
   559
/**
kpeter@314
   560
@defgroup approx Approximation Algorithms
kpeter@314
   561
@ingroup algs
kpeter@50
   562
\brief Approximation algorithms.
alpar@40
   563
kpeter@559
   564
This group contains the approximation and heuristic algorithms
kpeter@50
   565
implemented in LEMON.
alpar@40
   566
*/
alpar@40
   567
alpar@40
   568
/**
alpar@40
   569
@defgroup gen_opt_group General Optimization Tools
kpeter@559
   570
\brief This group contains some general optimization frameworks
alpar@40
   571
implemented in LEMON.
alpar@40
   572
kpeter@559
   573
This group contains some general optimization frameworks
alpar@40
   574
implemented in LEMON.
alpar@40
   575
*/
alpar@40
   576
alpar@40
   577
/**
kpeter@314
   578
@defgroup lp_group Lp and Mip Solvers
alpar@40
   579
@ingroup gen_opt_group
alpar@40
   580
\brief Lp and Mip solver interfaces for LEMON.
alpar@40
   581
kpeter@559
   582
This group contains Lp and Mip solver interfaces for LEMON. The
alpar@40
   583
various LP solvers could be used in the same manner with this
alpar@40
   584
interface.
alpar@40
   585
*/
alpar@40
   586
alpar@209
   587
/**
kpeter@314
   588
@defgroup lp_utils Tools for Lp and Mip Solvers
alpar@40
   589
@ingroup lp_group
kpeter@50
   590
\brief Helper tools to the Lp and Mip solvers.
alpar@40
   591
alpar@40
   592
This group adds some helper tools to general optimization framework
alpar@40
   593
implemented in LEMON.
alpar@40
   594
*/
alpar@40
   595
alpar@40
   596
/**
alpar@40
   597
@defgroup metah Metaheuristics
alpar@40
   598
@ingroup gen_opt_group
alpar@40
   599
\brief Metaheuristics for LEMON library.
alpar@40
   600
kpeter@559
   601
This group contains some metaheuristic optimization tools.
alpar@40
   602
*/
alpar@40
   603
alpar@40
   604
/**
alpar@209
   605
@defgroup utils Tools and Utilities
kpeter@50
   606
\brief Tools and utilities for programming in LEMON
alpar@40
   607
kpeter@50
   608
Tools and utilities for programming in LEMON.
alpar@40
   609
*/
alpar@40
   610
alpar@40
   611
/**
alpar@40
   612
@defgroup gutils Basic Graph Utilities
alpar@40
   613
@ingroup utils
kpeter@50
   614
\brief Simple basic graph utilities.
alpar@40
   615
kpeter@559
   616
This group contains some simple basic graph utilities.
alpar@40
   617
*/
alpar@40
   618
alpar@40
   619
/**
alpar@40
   620
@defgroup misc Miscellaneous Tools
alpar@40
   621
@ingroup utils
kpeter@50
   622
\brief Tools for development, debugging and testing.
kpeter@50
   623
kpeter@559
   624
This group contains several useful tools for development,
alpar@40
   625
debugging and testing.
alpar@40
   626
*/
alpar@40
   627
alpar@40
   628
/**
kpeter@314
   629
@defgroup timecount Time Measuring and Counting
alpar@40
   630
@ingroup misc
kpeter@50
   631
\brief Simple tools for measuring the performance of algorithms.
kpeter@50
   632
kpeter@559
   633
This group contains simple tools for measuring the performance
alpar@40
   634
of algorithms.
alpar@40
   635
*/
alpar@40
   636
alpar@40
   637
/**
alpar@40
   638
@defgroup exceptions Exceptions
alpar@40
   639
@ingroup utils
kpeter@50
   640
\brief Exceptions defined in LEMON.
kpeter@50
   641
kpeter@559
   642
This group contains the exceptions defined in LEMON.
alpar@40
   643
*/
alpar@40
   644
alpar@40
   645
/**
alpar@40
   646
@defgroup io_group Input-Output
kpeter@50
   647
\brief Graph Input-Output methods
alpar@40
   648
kpeter@559
   649
This group contains the tools for importing and exporting graphs
kpeter@314
   650
and graph related data. Now it supports the \ref lgf-format
kpeter@314
   651
"LEMON Graph Format", the \c DIMACS format and the encapsulated
kpeter@314
   652
postscript (EPS) format.
alpar@40
   653
*/
alpar@40
   654
alpar@40
   655
/**
kpeter@351
   656
@defgroup lemon_io LEMON Graph Format
alpar@40
   657
@ingroup io_group
kpeter@314
   658
\brief Reading and writing LEMON Graph Format.
alpar@40
   659
kpeter@559
   660
This group contains methods for reading and writing
ladanyi@236
   661
\ref lgf-format "LEMON Graph Format".
alpar@40
   662
*/
alpar@40
   663
alpar@40
   664
/**
kpeter@314
   665
@defgroup eps_io Postscript Exporting
alpar@40
   666
@ingroup io_group
alpar@40
   667
\brief General \c EPS drawer and graph exporter
alpar@40
   668
kpeter@559
   669
This group contains general \c EPS drawing methods and special
alpar@209
   670
graph exporting tools.
alpar@40
   671
*/
alpar@40
   672
alpar@40
   673
/**
kpeter@388
   674
@defgroup dimacs_group DIMACS format
kpeter@388
   675
@ingroup io_group
kpeter@388
   676
\brief Read and write files in DIMACS format
kpeter@388
   677
kpeter@388
   678
Tools to read a digraph from or write it to a file in DIMACS format data.
kpeter@388
   679
*/
kpeter@388
   680
kpeter@388
   681
/**
kpeter@351
   682
@defgroup nauty_group NAUTY Format
kpeter@351
   683
@ingroup io_group
kpeter@351
   684
\brief Read \e Nauty format
kpeter@388
   685
kpeter@351
   686
Tool to read graphs from \e Nauty format data.
kpeter@351
   687
*/
kpeter@351
   688
kpeter@351
   689
/**
alpar@40
   690
@defgroup concept Concepts
alpar@40
   691
\brief Skeleton classes and concept checking classes
alpar@40
   692
kpeter@559
   693
This group contains the data/algorithm skeletons and concept checking
alpar@40
   694
classes implemented in LEMON.
alpar@40
   695
alpar@40
   696
The purpose of the classes in this group is fourfold.
alpar@209
   697
kpeter@318
   698
- These classes contain the documentations of the %concepts. In order
alpar@40
   699
  to avoid document multiplications, an implementation of a concept
alpar@40
   700
  simply refers to the corresponding concept class.
alpar@40
   701
alpar@40
   702
- These classes declare every functions, <tt>typedef</tt>s etc. an
kpeter@318
   703
  implementation of the %concepts should provide, however completely
alpar@40
   704
  without implementations and real data structures behind the
alpar@40
   705
  interface. On the other hand they should provide nothing else. All
alpar@40
   706
  the algorithms working on a data structure meeting a certain concept
alpar@40
   707
  should compile with these classes. (Though it will not run properly,
alpar@40
   708
  of course.) In this way it is easily to check if an algorithm
alpar@40
   709
  doesn't use any extra feature of a certain implementation.
alpar@40
   710
alpar@40
   711
- The concept descriptor classes also provide a <em>checker class</em>
kpeter@50
   712
  that makes it possible to check whether a certain implementation of a
alpar@40
   713
  concept indeed provides all the required features.
alpar@40
   714
alpar@40
   715
- Finally, They can serve as a skeleton of a new implementation of a concept.
alpar@40
   716
*/
alpar@40
   717
alpar@40
   718
/**
alpar@40
   719
@defgroup graph_concepts Graph Structure Concepts
alpar@40
   720
@ingroup concept
alpar@40
   721
\brief Skeleton and concept checking classes for graph structures
alpar@40
   722
kpeter@559
   723
This group contains the skeletons and concept checking classes of LEMON's
alpar@40
   724
graph structures and helper classes used to implement these.
alpar@40
   725
*/
alpar@40
   726
kpeter@314
   727
/**
kpeter@314
   728
@defgroup map_concepts Map Concepts
kpeter@314
   729
@ingroup concept
kpeter@314
   730
\brief Skeleton and concept checking classes for maps
kpeter@314
   731
kpeter@559
   732
This group contains the skeletons and concept checking classes of maps.
alpar@40
   733
*/
alpar@40
   734
alpar@40
   735
/**
alpar@40
   736
\anchor demoprograms
alpar@40
   737
kpeter@406
   738
@defgroup demos Demo Programs
alpar@40
   739
alpar@40
   740
Some demo programs are listed here. Their full source codes can be found in
alpar@40
   741
the \c demo subdirectory of the source tree.
alpar@40
   742
ladanyi@564
   743
In order to compile them, use the <tt>make demo</tt> or the
ladanyi@564
   744
<tt>make check</tt> commands.
alpar@40
   745
*/
alpar@40
   746
alpar@40
   747
/**
kpeter@406
   748
@defgroup tools Standalone Utility Applications
alpar@40
   749
alpar@209
   750
Some utility applications are listed here.
alpar@40
   751
alpar@40
   752
The standard compilation procedure (<tt>./configure;make</tt>) will compile
alpar@209
   753
them, as well.
alpar@40
   754
*/
alpar@40
   755
kpeter@406
   756
}