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