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