doc/groups.dox
author Balazs Dezso <deba@inf.elte.hu>
Mon, 15 Nov 2010 09:46:08 +0100
changeset 1021 a12cca3ad15a
parent 1002 f63ba40a60f4
child 1038 a2d142bb5d3c
permissions -rw-r--r--
ListBpGraph implementation (#69)
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@877
     5
 * Copyright (C) 2003-2010
alpar@40
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@40
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@40
     8
 *
alpar@40
     9
 * Permission to use, modify and distribute this software is granted
alpar@40
    10
 * provided that this copyright notice appears in all copies. For
alpar@40
    11
 * precise terms see the accompanying LICENSE file.
alpar@40
    12
 *
alpar@40
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@40
    14
 * express or implied, and with no claim as to its suitability for any
alpar@40
    15
 * purpose.
alpar@40
    16
 *
alpar@40
    17
 */
alpar@40
    18
kpeter@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
/**
alpar@209
   141
@defgroup maps Maps
alpar@40
   142
@ingroup datas
kpeter@50
   143
\brief Map structures implemented in LEMON.
alpar@40
   144
kpeter@559
   145
This group contains the map structures implemented in LEMON.
kpeter@50
   146
kpeter@314
   147
LEMON provides several special purpose maps and map adaptors that e.g. combine
alpar@40
   148
new maps from existing ones.
kpeter@314
   149
kpeter@314
   150
<b>See also:</b> \ref map_concepts "Map Concepts".
alpar@40
   151
*/
alpar@40
   152
alpar@40
   153
/**
alpar@209
   154
@defgroup graph_maps Graph Maps
alpar@40
   155
@ingroup maps
kpeter@83
   156
\brief Special graph-related maps.
alpar@40
   157
kpeter@559
   158
This group contains maps that are specifically designed to assign
kpeter@406
   159
values to the nodes and arcs/edges of graphs.
kpeter@406
   160
kpeter@406
   161
If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
kpeter@406
   162
\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
alpar@40
   163
*/
alpar@40
   164
alpar@40
   165
/**
alpar@40
   166
\defgroup map_adaptors Map Adaptors
alpar@40
   167
\ingroup maps
alpar@40
   168
\brief Tools to create new maps from existing ones
alpar@40
   169
kpeter@559
   170
This group contains map adaptors that are used to create "implicit"
kpeter@50
   171
maps from other maps.
alpar@40
   172
kpeter@406
   173
Most of them are \ref concepts::ReadMap "read-only maps".
kpeter@83
   174
They can make arithmetic and logical operations between one or two maps
kpeter@83
   175
(negation, shifting, addition, multiplication, logical 'and', 'or',
kpeter@83
   176
'not' etc.) or e.g. convert a map to another one of different Value type.
alpar@40
   177
kpeter@50
   178
The typical usage of this classes is passing implicit maps to
alpar@40
   179
algorithms.  If a function type algorithm is called then the function
alpar@40
   180
type map adaptors can be used comfortable. For example let's see the
kpeter@314
   181
usage of map adaptors with the \c graphToEps() function.
alpar@40
   182
\code
alpar@40
   183
  Color nodeColor(int deg) {
alpar@40
   184
    if (deg >= 2) {
alpar@40
   185
      return Color(0.5, 0.0, 0.5);
alpar@40
   186
    } else if (deg == 1) {
alpar@40
   187
      return Color(1.0, 0.5, 1.0);
alpar@40
   188
    } else {
alpar@40
   189
      return Color(0.0, 0.0, 0.0);
alpar@40
   190
    }
alpar@40
   191
  }
alpar@209
   192
kpeter@83
   193
  Digraph::NodeMap<int> degree_map(graph);
alpar@209
   194
kpeter@314
   195
  graphToEps(graph, "graph.eps")
alpar@40
   196
    .coords(coords).scaleToA4().undirected()
kpeter@83
   197
    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
alpar@40
   198
    .run();
alpar@209
   199
\endcode
kpeter@83
   200
The \c functorToMap() function makes an \c int to \c Color map from the
kpeter@314
   201
\c nodeColor() function. The \c composeMap() compose the \c degree_map
kpeter@83
   202
and the previously created map. The composed map is a proper function to
kpeter@83
   203
get the color of each node.
alpar@40
   204
alpar@40
   205
The usage with class type algorithms is little bit harder. In this
alpar@40
   206
case the function type map adaptors can not be used, because the
kpeter@50
   207
function map adaptors give back temporary objects.
alpar@40
   208
\code
kpeter@83
   209
  Digraph graph;
kpeter@83
   210
kpeter@83
   211
  typedef Digraph::ArcMap<double> DoubleArcMap;
kpeter@83
   212
  DoubleArcMap length(graph);
kpeter@83
   213
  DoubleArcMap speed(graph);
kpeter@83
   214
kpeter@83
   215
  typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
alpar@40
   216
  TimeMap time(length, speed);
alpar@209
   217
kpeter@83
   218
  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
alpar@40
   219
  dijkstra.run(source, target);
alpar@40
   220
\endcode
kpeter@83
   221
We have a length map and a maximum speed map on the arcs of a digraph.
kpeter@83
   222
The minimum time to pass the arc can be calculated as the division of
kpeter@83
   223
the two maps which can be done implicitly with the \c DivMap template
alpar@40
   224
class. We use the implicit minimum time map as the length map of the
alpar@40
   225
\c Dijkstra algorithm.
alpar@40
   226
*/
alpar@40
   227
alpar@40
   228
/**
alpar@40
   229
@defgroup paths Path Structures
alpar@40
   230
@ingroup datas
kpeter@318
   231
\brief %Path structures implemented in LEMON.
alpar@40
   232
kpeter@559
   233
This group contains the path structures implemented in LEMON.
alpar@40
   234
kpeter@50
   235
LEMON provides flexible data structures to work with paths.
kpeter@50
   236
All of them have similar interfaces and they can be copied easily with
kpeter@50
   237
assignment operators and copy constructors. This makes it easy and
alpar@40
   238
efficient to have e.g. the Dijkstra algorithm to store its result in
alpar@40
   239
any kind of path structure.
alpar@40
   240
kpeter@710
   241
\sa \ref concepts::Path "Path concept"
kpeter@710
   242
*/
kpeter@710
   243
kpeter@710
   244
/**
kpeter@710
   245
@defgroup heaps Heap Structures
kpeter@710
   246
@ingroup datas
kpeter@710
   247
\brief %Heap structures implemented in LEMON.
kpeter@710
   248
kpeter@710
   249
This group contains the heap structures implemented in LEMON.
kpeter@710
   250
kpeter@710
   251
LEMON provides several heap classes. They are efficient implementations
kpeter@710
   252
of the abstract data type \e priority \e queue. They store items with
kpeter@710
   253
specified values called \e priorities in such a way that finding and
kpeter@710
   254
removing the item with minimum priority are efficient.
kpeter@710
   255
The basic operations are adding and erasing items, changing the priority
kpeter@710
   256
of an item, etc.
kpeter@710
   257
kpeter@710
   258
Heaps are crucial in several algorithms, such as Dijkstra and Prim.
kpeter@710
   259
The heap implementations have the same interface, thus any of them can be
kpeter@710
   260
used easily in such algorithms.
kpeter@710
   261
kpeter@710
   262
\sa \ref concepts::Heap "Heap concept"
kpeter@710
   263
*/
kpeter@710
   264
kpeter@710
   265
/**
alpar@40
   266
@defgroup auxdat Auxiliary Data Structures
alpar@40
   267
@ingroup datas
kpeter@50
   268
\brief Auxiliary data structures implemented in LEMON.
alpar@40
   269
kpeter@559
   270
This group contains some data structures implemented in LEMON in
alpar@40
   271
order to make it easier to implement combinatorial algorithms.
alpar@40
   272
*/
alpar@40
   273
alpar@40
   274
/**
kpeter@714
   275
@defgroup geomdat Geometric Data Structures
kpeter@714
   276
@ingroup auxdat
kpeter@714
   277
\brief Geometric data structures implemented in LEMON.
kpeter@714
   278
kpeter@714
   279
This group contains geometric data structures implemented in LEMON.
kpeter@714
   280
kpeter@714
   281
 - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
kpeter@714
   282
   vector with the usual operations.
kpeter@714
   283
 - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
kpeter@714
   284
   rectangular bounding box of a set of \ref lemon::dim2::Point
kpeter@714
   285
   "dim2::Point"'s.
kpeter@714
   286
*/
kpeter@714
   287
kpeter@714
   288
/**
kpeter@714
   289
@defgroup matrices Matrices
kpeter@714
   290
@ingroup auxdat
kpeter@714
   291
\brief Two dimensional data storages implemented in LEMON.
kpeter@714
   292
kpeter@714
   293
This group contains two dimensional data storages implemented in LEMON.
kpeter@714
   294
*/
kpeter@714
   295
kpeter@714
   296
/**
alpar@40
   297
@defgroup algs Algorithms
kpeter@559
   298
\brief This group contains the several algorithms
alpar@40
   299
implemented in LEMON.
alpar@40
   300
kpeter@559
   301
This group contains the several algorithms
alpar@40
   302
implemented in LEMON.
alpar@40
   303
*/
alpar@40
   304
alpar@40
   305
/**
alpar@40
   306
@defgroup search Graph Search
alpar@40
   307
@ingroup algs
kpeter@50
   308
\brief Common graph search algorithms.
alpar@40
   309
kpeter@559
   310
This group contains the common graph search algorithms, namely
kpeter@755
   311
\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
kpeter@755
   312
\ref clrs01algorithms.
alpar@40
   313
*/
alpar@40
   314
alpar@40
   315
/**
kpeter@314
   316
@defgroup shortest_path Shortest Path Algorithms
alpar@40
   317
@ingroup algs
kpeter@50
   318
\brief Algorithms for finding shortest paths.
alpar@40
   319
kpeter@755
   320
This group contains the algorithms for finding shortest paths in digraphs
kpeter@755
   321
\ref clrs01algorithms.
kpeter@406
   322
kpeter@406
   323
 - \ref Dijkstra algorithm for finding shortest paths from a source node
kpeter@406
   324
   when all arc lengths are non-negative.
kpeter@406
   325
 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
kpeter@406
   326
   from a source node when arc lenghts can be either positive or negative,
kpeter@406
   327
   but the digraph should not contain directed cycles with negative total
kpeter@406
   328
   length.
kpeter@406
   329
 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
kpeter@406
   330
   for solving the \e all-pairs \e shortest \e paths \e problem when arc
kpeter@406
   331
   lenghts can be either positive or negative, but the digraph should
kpeter@406
   332
   not contain directed cycles with negative total length.
kpeter@406
   333
 - \ref Suurballe A successive shortest path algorithm for finding
kpeter@406
   334
   arc-disjoint paths between two nodes having minimum total length.
alpar@40
   335
*/
alpar@40
   336
alpar@209
   337
/**
kpeter@714
   338
@defgroup spantree Minimum Spanning Tree Algorithms
kpeter@714
   339
@ingroup algs
kpeter@714
   340
\brief Algorithms for finding minimum cost spanning trees and arborescences.
kpeter@714
   341
kpeter@714
   342
This group contains the algorithms for finding minimum cost spanning
kpeter@755
   343
trees and arborescences \ref clrs01algorithms.
kpeter@714
   344
*/
kpeter@714
   345
kpeter@714
   346
/**
kpeter@314
   347
@defgroup max_flow Maximum Flow Algorithms
alpar@209
   348
@ingroup algs
kpeter@50
   349
\brief Algorithms for finding maximum flows.
alpar@40
   350
kpeter@559
   351
This group contains the algorithms for finding maximum flows and
kpeter@755
   352
feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
alpar@40
   353
kpeter@406
   354
The \e maximum \e flow \e problem is to find a flow of maximum value between
kpeter@406
   355
a single source and a single target. Formally, there is a \f$G=(V,A)\f$
kpeter@609
   356
digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
kpeter@406
   357
\f$s, t \in V\f$ source and target nodes.
kpeter@609
   358
A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
kpeter@406
   359
following optimization problem.
alpar@40
   360
kpeter@609
   361
\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
kpeter@609
   362
\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
kpeter@609
   363
    \quad \forall u\in V\setminus\{s,t\} \f]
kpeter@609
   364
\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
alpar@40
   365
kpeter@50
   366
LEMON contains several algorithms for solving maximum flow problems:
kpeter@755
   367
- \ref EdmondsKarp Edmonds-Karp algorithm
kpeter@755
   368
  \ref edmondskarp72theoretical.
kpeter@755
   369
- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
kpeter@755
   370
  \ref goldberg88newapproach.
kpeter@755
   371
- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
kpeter@755
   372
  \ref dinic70algorithm, \ref sleator83dynamic.
kpeter@755
   373
- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
kpeter@755
   374
  \ref goldberg88newapproach, \ref sleator83dynamic.
alpar@40
   375
kpeter@755
   376
In most cases the \ref Preflow algorithm provides the
kpeter@406
   377
fastest method for computing a maximum flow. All implementations
kpeter@651
   378
also provide functions to query the minimum cut, which is the dual
kpeter@651
   379
problem of maximum flow.
kpeter@651
   380
deba@869
   381
\ref Circulation is a preflow push-relabel algorithm implemented directly
kpeter@651
   382
for finding feasible circulations, which is a somewhat different problem,
kpeter@651
   383
but it is strongly related to maximum flow.
kpeter@651
   384
For more information, see \ref Circulation.
alpar@40
   385
*/
alpar@40
   386
alpar@40
   387
/**
kpeter@663
   388
@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
alpar@40
   389
@ingroup algs
alpar@40
   390
kpeter@50
   391
\brief Algorithms for finding minimum cost flows and circulations.
alpar@40
   392
kpeter@609
   393
This group contains the algorithms for finding minimum cost flows and
kpeter@755
   394
circulations \ref amo93networkflows. For more information about this
kpeter@755
   395
problem and its dual solution, see \ref min_cost_flow
kpeter@755
   396
"Minimum Cost Flow Problem".
kpeter@406
   397
kpeter@663
   398
LEMON contains several algorithms for this problem.
kpeter@609
   399
 - \ref NetworkSimplex Primal Network Simplex algorithm with various
kpeter@755
   400
   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
kpeter@813
   401
 - \ref CostScaling Cost Scaling algorithm based on push/augment and
kpeter@813
   402
   relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
kpeter@755
   403
   \ref bunnagel98efficient.
kpeter@813
   404
 - \ref CapacityScaling Capacity Scaling algorithm based on the successive
kpeter@813
   405
   shortest path method \ref edmondskarp72theoretical.
kpeter@813
   406
 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
kpeter@813
   407
   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
kpeter@609
   408
kpeter@919
   409
In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
kpeter@1003
   410
implementations.
kpeter@1003
   411
\ref NetworkSimplex is usually the fastest on relatively small graphs (up to
kpeter@1003
   412
several thousands of nodes) and on dense graphs, while \ref CostScaling is
kpeter@1003
   413
typically more efficient on large graphs (e.g. hundreds of thousands of
kpeter@1003
   414
nodes or above), especially if they are sparse.
kpeter@1003
   415
However, other algorithms could be faster in special cases.
kpeter@609
   416
For example, if the total supply and/or capacities are rather small,
kpeter@919
   417
\ref CapacityScaling is usually the fastest algorithm (without effective scaling).
kpeter@1002
   418
kpeter@1002
   419
These classes are intended to be used with integer-valued input data
kpeter@1002
   420
(capacities, supply values, and costs), except for \ref CapacityScaling,
kpeter@1002
   421
which is capable of handling real-valued arc costs (other numerical
kpeter@1002
   422
data are required to be integer).
alpar@40
   423
*/
alpar@40
   424
alpar@40
   425
/**
kpeter@314
   426
@defgroup min_cut Minimum Cut Algorithms
alpar@209
   427
@ingroup algs
alpar@40
   428
kpeter@50
   429
\brief Algorithms for finding minimum cut in graphs.
alpar@40
   430
kpeter@559
   431
This group contains the algorithms for finding minimum cut in graphs.
alpar@40
   432
kpeter@406
   433
The \e minimum \e cut \e problem is to find a non-empty and non-complete
kpeter@406
   434
\f$X\f$ subset of the nodes with minimum overall capacity on
kpeter@406
   435
outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
kpeter@406
   436
\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
kpeter@50
   437
cut is the \f$X\f$ solution of the next optimization problem:
alpar@40
   438
alpar@210
   439
\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
kpeter@713
   440
    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
alpar@40
   441
kpeter@50
   442
LEMON contains several algorithms related to minimum cut problems:
alpar@40
   443
kpeter@406
   444
- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
kpeter@406
   445
  in directed graphs.
kpeter@406
   446
- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
kpeter@406
   447
  calculating minimum cut in undirected graphs.
kpeter@559
   448
- \ref GomoryHu "Gomory-Hu tree computation" for calculating
kpeter@406
   449
  all-pairs minimum cut in undirected graphs.
alpar@40
   450
alpar@40
   451
If you want to find minimum cut just between two distinict nodes,
kpeter@406
   452
see the \ref max_flow "maximum flow problem".
alpar@40
   453
*/
alpar@40
   454
alpar@40
   455
/**
kpeter@768
   456
@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
alpar@40
   457
@ingroup algs
kpeter@768
   458
\brief Algorithms for finding minimum mean cycles.
alpar@40
   459
kpeter@771
   460
This group contains the algorithms for finding minimum mean cycles
kpeter@1002
   461
\ref amo93networkflows, \ref karp78characterization.
alpar@40
   462
kpeter@768
   463
The \e minimum \e mean \e cycle \e problem is to find a directed cycle
kpeter@768
   464
of minimum mean length (cost) in a digraph.
kpeter@768
   465
The mean length of a cycle is the average length of its arcs, i.e. the
kpeter@768
   466
ratio between the total length of the cycle and the number of arcs on it.
alpar@40
   467
kpeter@768
   468
This problem has an important connection to \e conservative \e length
kpeter@768
   469
\e functions, too. A length function on the arcs of a digraph is called
kpeter@768
   470
conservative if and only if there is no directed cycle of negative total
kpeter@768
   471
length. For an arbitrary length function, the negative of the minimum
kpeter@768
   472
cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
kpeter@768
   473
arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
kpeter@768
   474
function.
alpar@40
   475
kpeter@768
   476
LEMON contains three algorithms for solving the minimum mean cycle problem:
kpeter@1002
   477
- \ref KarpMmc Karp's original algorithm \ref karp78characterization.
kpeter@879
   478
- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
kpeter@1002
   479
  version of Karp's algorithm \ref hartmann93finding.
kpeter@879
   480
- \ref HowardMmc Howard's policy iteration algorithm
kpeter@1002
   481
  \ref dasdan98minmeancycle, \ref dasdan04experimental.
alpar@40
   482
kpeter@919
   483
In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
kpeter@879
   484
most efficient one, though the best known theoretical bound on its running
kpeter@879
   485
time is exponential.
kpeter@879
   486
Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
kpeter@879
   487
run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
kpeter@879
   488
typically faster due to the applied early termination scheme.
alpar@40
   489
*/
alpar@40
   490
alpar@40
   491
/**
kpeter@314
   492
@defgroup matching Matching Algorithms
alpar@40
   493
@ingroup algs
kpeter@50
   494
\brief Algorithms for finding matchings in graphs and bipartite graphs.
alpar@40
   495
kpeter@590
   496
This group contains the algorithms for calculating
alpar@40
   497
matchings in graphs and bipartite graphs. The general matching problem is
kpeter@590
   498
finding a subset of the edges for which each node has at most one incident
kpeter@590
   499
edge.
alpar@209
   500
alpar@40
   501
There are several different algorithms for calculate matchings in
alpar@40
   502
graphs.  The matching problems in bipartite graphs are generally
alpar@40
   503
easier than in general graphs. The goal of the matching optimization
kpeter@406
   504
can be finding maximum cardinality, maximum weight or minimum cost
alpar@40
   505
matching. The search can be constrained to find perfect or
alpar@40
   506
maximum cardinality matching.
alpar@40
   507
kpeter@406
   508
The matching algorithms implemented in LEMON:
kpeter@406
   509
- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
kpeter@406
   510
  for calculating maximum cardinality matching in bipartite graphs.
kpeter@406
   511
- \ref PrBipartiteMatching Push-relabel algorithm
kpeter@406
   512
  for calculating maximum cardinality matching in bipartite graphs.
kpeter@406
   513
- \ref MaxWeightedBipartiteMatching
kpeter@406
   514
  Successive shortest path algorithm for calculating maximum weighted
kpeter@406
   515
  matching and maximum weighted bipartite matching in bipartite graphs.
kpeter@406
   516
- \ref MinCostMaxBipartiteMatching
kpeter@406
   517
  Successive shortest path algorithm for calculating minimum cost maximum
kpeter@406
   518
  matching in bipartite graphs.
kpeter@406
   519
- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
kpeter@406
   520
  maximum cardinality matching in general graphs.
kpeter@406
   521
- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
kpeter@406
   522
  maximum weighted matching in general graphs.
kpeter@406
   523
- \ref MaxWeightedPerfectMatching
kpeter@406
   524
  Edmond's blossom shrinking algorithm for calculating maximum weighted
kpeter@406
   525
  perfect matching in general graphs.
deba@869
   526
- \ref MaxFractionalMatching Push-relabel algorithm for calculating
deba@869
   527
  maximum cardinality fractional matching in general graphs.
deba@869
   528
- \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating
deba@869
   529
  maximum weighted fractional matching in general graphs.
deba@869
   530
- \ref MaxWeightedPerfectFractionalMatching
deba@869
   531
  Augmenting path algorithm for calculating maximum weighted
deba@869
   532
  perfect fractional matching in general graphs.
alpar@40
   533
alpar@865
   534
\image html matching.png
alpar@873
   535
\image latex matching.eps "Min Cost Perfect Matching" width=\textwidth
alpar@40
   536
*/
alpar@40
   537
alpar@40
   538
/**
kpeter@714
   539
@defgroup graph_properties Connectivity and Other Graph Properties
alpar@40
   540
@ingroup algs
kpeter@714
   541
\brief Algorithms for discovering the graph properties
alpar@40
   542
kpeter@714
   543
This group contains the algorithms for discovering the graph properties
kpeter@714
   544
like connectivity, bipartiteness, euler property, simplicity etc.
kpeter@714
   545
kpeter@714
   546
\image html connected_components.png
kpeter@714
   547
\image latex connected_components.eps "Connected components" width=\textwidth
kpeter@714
   548
*/
kpeter@714
   549
kpeter@714
   550
/**
kpeter@919
   551
@defgroup planar Planar Embedding and Drawing
kpeter@714
   552
@ingroup algs
kpeter@714
   553
\brief Algorithms for planarity checking, embedding and drawing
kpeter@714
   554
kpeter@714
   555
This group contains the algorithms for planarity checking,
kpeter@714
   556
embedding and drawing.
kpeter@714
   557
kpeter@714
   558
\image html planar.png
kpeter@714
   559
\image latex planar.eps "Plane graph" width=\textwidth
kpeter@714
   560
*/
kpeter@714
   561
kpeter@714
   562
/**
kpeter@904
   563
@defgroup approx_algs Approximation Algorithms
kpeter@714
   564
@ingroup algs
kpeter@714
   565
\brief Approximation algorithms.
kpeter@714
   566
kpeter@714
   567
This group contains the approximation and heuristic algorithms
kpeter@714
   568
implemented in LEMON.
kpeter@904
   569
kpeter@904
   570
<b>Maximum Clique Problem</b>
kpeter@904
   571
  - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
kpeter@904
   572
    Grosso, Locatelli, and Pullan.
alpar@40
   573
*/
alpar@40
   574
alpar@40
   575
/**
kpeter@314
   576
@defgroup auxalg Auxiliary Algorithms
alpar@40
   577
@ingroup algs
kpeter@50
   578
\brief Auxiliary algorithms implemented in LEMON.
alpar@40
   579
kpeter@559
   580
This group contains some algorithms implemented in LEMON
kpeter@50
   581
in order to make it easier to implement complex algorithms.
alpar@40
   582
*/
alpar@40
   583
alpar@40
   584
/**
alpar@40
   585
@defgroup gen_opt_group General Optimization Tools
kpeter@559
   586
\brief This group contains some general optimization frameworks
alpar@40
   587
implemented in LEMON.
alpar@40
   588
kpeter@559
   589
This group contains some general optimization frameworks
alpar@40
   590
implemented in LEMON.
alpar@40
   591
*/
alpar@40
   592
alpar@40
   593
/**
kpeter@755
   594
@defgroup lp_group LP and MIP Solvers
alpar@40
   595
@ingroup gen_opt_group
kpeter@755
   596
\brief LP and MIP solver interfaces for LEMON.
alpar@40
   597
kpeter@755
   598
This group contains LP and MIP solver interfaces for LEMON.
kpeter@755
   599
Various LP solvers could be used in the same manner with this
kpeter@755
   600
high-level interface.
kpeter@755
   601
kpeter@755
   602
The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
kpeter@755
   603
\ref cplex, \ref soplex.
alpar@40
   604
*/
alpar@40
   605
alpar@209
   606
/**
kpeter@314
   607
@defgroup lp_utils Tools for Lp and Mip Solvers
alpar@40
   608
@ingroup lp_group
kpeter@50
   609
\brief Helper tools to the Lp and Mip solvers.
alpar@40
   610
alpar@40
   611
This group adds some helper tools to general optimization framework
alpar@40
   612
implemented in LEMON.
alpar@40
   613
*/
alpar@40
   614
alpar@40
   615
/**
alpar@40
   616
@defgroup metah Metaheuristics
alpar@40
   617
@ingroup gen_opt_group
alpar@40
   618
\brief Metaheuristics for LEMON library.
alpar@40
   619
kpeter@559
   620
This group contains some metaheuristic optimization tools.
alpar@40
   621
*/
alpar@40
   622
alpar@40
   623
/**
alpar@209
   624
@defgroup utils Tools and Utilities
kpeter@50
   625
\brief Tools and utilities for programming in LEMON
alpar@40
   626
kpeter@50
   627
Tools and utilities for programming in LEMON.
alpar@40
   628
*/
alpar@40
   629
alpar@40
   630
/**
alpar@40
   631
@defgroup gutils Basic Graph Utilities
alpar@40
   632
@ingroup utils
kpeter@50
   633
\brief Simple basic graph utilities.
alpar@40
   634
kpeter@559
   635
This group contains some simple basic graph utilities.
alpar@40
   636
*/
alpar@40
   637
alpar@40
   638
/**
alpar@40
   639
@defgroup misc Miscellaneous Tools
alpar@40
   640
@ingroup utils
kpeter@50
   641
\brief Tools for development, debugging and testing.
kpeter@50
   642
kpeter@559
   643
This group contains several useful tools for development,
alpar@40
   644
debugging and testing.
alpar@40
   645
*/
alpar@40
   646
alpar@40
   647
/**
kpeter@314
   648
@defgroup timecount Time Measuring and Counting
alpar@40
   649
@ingroup misc
kpeter@50
   650
\brief Simple tools for measuring the performance of algorithms.
kpeter@50
   651
kpeter@559
   652
This group contains simple tools for measuring the performance
alpar@40
   653
of algorithms.
alpar@40
   654
*/
alpar@40
   655
alpar@40
   656
/**
alpar@40
   657
@defgroup exceptions Exceptions
alpar@40
   658
@ingroup utils
kpeter@50
   659
\brief Exceptions defined in LEMON.
kpeter@50
   660
kpeter@559
   661
This group contains the exceptions defined in LEMON.
alpar@40
   662
*/
alpar@40
   663
alpar@40
   664
/**
alpar@40
   665
@defgroup io_group Input-Output
kpeter@50
   666
\brief Graph Input-Output methods
alpar@40
   667
kpeter@559
   668
This group contains the tools for importing and exporting graphs
kpeter@314
   669
and graph related data. Now it supports the \ref lgf-format
kpeter@314
   670
"LEMON Graph Format", the \c DIMACS format and the encapsulated
kpeter@314
   671
postscript (EPS) format.
alpar@40
   672
*/
alpar@40
   673
alpar@40
   674
/**
kpeter@351
   675
@defgroup lemon_io LEMON Graph Format
alpar@40
   676
@ingroup io_group
kpeter@314
   677
\brief Reading and writing LEMON Graph Format.
alpar@40
   678
kpeter@559
   679
This group contains methods for reading and writing
ladanyi@236
   680
\ref lgf-format "LEMON Graph Format".
alpar@40
   681
*/
alpar@40
   682
alpar@40
   683
/**
kpeter@314
   684
@defgroup eps_io Postscript Exporting
alpar@40
   685
@ingroup io_group
alpar@40
   686
\brief General \c EPS drawer and graph exporter
alpar@40
   687
kpeter@559
   688
This group contains general \c EPS drawing methods and special
alpar@209
   689
graph exporting tools.
alpar@40
   690
*/
alpar@40
   691
alpar@40
   692
/**
kpeter@714
   693
@defgroup dimacs_group DIMACS Format
kpeter@388
   694
@ingroup io_group
kpeter@388
   695
\brief Read and write files in DIMACS format
kpeter@388
   696
kpeter@388
   697
Tools to read a digraph from or write it to a file in DIMACS format data.
kpeter@388
   698
*/
kpeter@388
   699
kpeter@388
   700
/**
kpeter@351
   701
@defgroup nauty_group NAUTY Format
kpeter@351
   702
@ingroup io_group
kpeter@351
   703
\brief Read \e Nauty format
kpeter@388
   704
kpeter@351
   705
Tool to read graphs from \e Nauty format data.
kpeter@351
   706
*/
kpeter@351
   707
kpeter@351
   708
/**
alpar@40
   709
@defgroup concept Concepts
alpar@40
   710
\brief Skeleton classes and concept checking classes
alpar@40
   711
kpeter@559
   712
This group contains the data/algorithm skeletons and concept checking
alpar@40
   713
classes implemented in LEMON.
alpar@40
   714
alpar@40
   715
The purpose of the classes in this group is fourfold.
alpar@209
   716
kpeter@318
   717
- These classes contain the documentations of the %concepts. In order
alpar@40
   718
  to avoid document multiplications, an implementation of a concept
alpar@40
   719
  simply refers to the corresponding concept class.
alpar@40
   720
alpar@40
   721
- These classes declare every functions, <tt>typedef</tt>s etc. an
kpeter@318
   722
  implementation of the %concepts should provide, however completely
alpar@40
   723
  without implementations and real data structures behind the
alpar@40
   724
  interface. On the other hand they should provide nothing else. All
alpar@40
   725
  the algorithms working on a data structure meeting a certain concept
alpar@40
   726
  should compile with these classes. (Though it will not run properly,
alpar@40
   727
  of course.) In this way it is easily to check if an algorithm
alpar@40
   728
  doesn't use any extra feature of a certain implementation.
alpar@40
   729
alpar@40
   730
- The concept descriptor classes also provide a <em>checker class</em>
kpeter@50
   731
  that makes it possible to check whether a certain implementation of a
alpar@40
   732
  concept indeed provides all the required features.
alpar@40
   733
alpar@40
   734
- Finally, They can serve as a skeleton of a new implementation of a concept.
alpar@40
   735
*/
alpar@40
   736
alpar@40
   737
/**
alpar@40
   738
@defgroup graph_concepts Graph Structure Concepts
alpar@40
   739
@ingroup concept
alpar@40
   740
\brief Skeleton and concept checking classes for graph structures
alpar@40
   741
kpeter@735
   742
This group contains the skeletons and concept checking classes of
kpeter@735
   743
graph structures.
alpar@40
   744
*/
alpar@40
   745
kpeter@314
   746
/**
kpeter@314
   747
@defgroup map_concepts Map Concepts
kpeter@314
   748
@ingroup concept
kpeter@314
   749
\brief Skeleton and concept checking classes for maps
kpeter@314
   750
kpeter@559
   751
This group contains the skeletons and concept checking classes of maps.
alpar@40
   752
*/
alpar@40
   753
alpar@40
   754
/**
kpeter@714
   755
@defgroup tools Standalone Utility Applications
kpeter@714
   756
kpeter@714
   757
Some utility applications are listed here.
kpeter@714
   758
kpeter@714
   759
The standard compilation procedure (<tt>./configure;make</tt>) will compile
kpeter@714
   760
them, as well.
kpeter@714
   761
*/
kpeter@714
   762
kpeter@714
   763
/**
alpar@40
   764
\anchor demoprograms
alpar@40
   765
kpeter@406
   766
@defgroup demos Demo Programs
alpar@40
   767
alpar@40
   768
Some demo programs are listed here. Their full source codes can be found in
alpar@40
   769
the \c demo subdirectory of the source tree.
alpar@40
   770
ladanyi@564
   771
In order to compile them, use the <tt>make demo</tt> or the
ladanyi@564
   772
<tt>make check</tt> commands.
alpar@40
   773
*/
alpar@40
   774
kpeter@406
   775
}