doc/groups.dox
author Alpar Juttner <alpar@cs.elte.hu>
Thu, 20 Mar 2008 22:59:58 +0000
changeset 105 e4948ef6a4ca
parent 50 a34c58ff6e40
child 83 3654324ec035
permissions -rw-r--r--
Get rid of StdMap in unionfind_test.cc
alpar@40
     1
/* -*- C++ -*-
alpar@40
     2
 *
alpar@40
     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@40
    29
The implementation of combinatorial algorithms heavily relies on 
alpar@40
    30
efficient graph implementations. LEMON offers data structures which are 
alpar@40
    31
planned to be easily used in an experimental phase of implementation studies, 
alpar@40
    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
alpar@40
    41
some graph features like edge or node deletion.
alpar@40
    42
alpar@40
    43
Alteration of standard containers need a very limited number of 
alpar@40
    44
operations, these together satisfy the everyday requirements. 
alpar@40
    45
In the case of graph structures, different operations are needed which do 
alpar@40
    46
not alter the physical graph, but gives another view. If some nodes or 
alpar@40
    47
edges have to be hidden or the reverse oriented graph have to be used, then 
alpar@40
    48
this is the case. It also may happen that in a flow implementation 
alpar@40
    49
the residual graph can be accessed by another algorithm, or a node-set 
alpar@40
    50
is to be shrunk for another algorithm. 
alpar@40
    51
LEMON also provides a variety of graphs for these requirements called 
alpar@40
    52
\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only 
kpeter@50
    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
alpar@40
    57
with any graph structures. 
alpar@40
    58
*/
alpar@40
    59
alpar@40
    60
/**
kpeter@50
    61
@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
alpar@40
    62
@ingroup graphs
alpar@40
    63
\brief Graph types between real graphs and graph adaptors.
alpar@40
    64
kpeter@50
    65
This group describes some graph types between real graphs and graph adaptors.
kpeter@50
    66
These classes wrap graphs to give new functionality as the adaptors do it. 
kpeter@50
    67
On the other hand they are not light-weight structures as the adaptors.
alpar@40
    68
*/
alpar@40
    69
alpar@40
    70
/**
alpar@40
    71
@defgroup maps Maps 
alpar@40
    72
@ingroup datas
kpeter@50
    73
\brief Map structures implemented in LEMON.
alpar@40
    74
kpeter@50
    75
This group describes the map structures implemented in LEMON.
kpeter@50
    76
kpeter@50
    77
LEMON provides several special purpose maps that e.g. combine
alpar@40
    78
new maps from existing ones.
alpar@40
    79
*/
alpar@40
    80
alpar@40
    81
/**
alpar@40
    82
@defgroup graph_maps Graph Maps 
alpar@40
    83
@ingroup maps
alpar@40
    84
\brief Special Graph-Related Maps.
alpar@40
    85
kpeter@50
    86
This group describes maps that are specifically designed to assign
kpeter@50
    87
values to the nodes and edges of graphs.
alpar@40
    88
*/
alpar@40
    89
alpar@40
    90
alpar@40
    91
/**
alpar@40
    92
\defgroup map_adaptors Map Adaptors
alpar@40
    93
\ingroup maps
alpar@40
    94
\brief Tools to create new maps from existing ones
alpar@40
    95
kpeter@50
    96
This group describes map adaptors that are used to create "implicit"
kpeter@50
    97
maps from other maps.
alpar@40
    98
alpar@40
    99
Most of them are \ref lemon::concepts::ReadMap "ReadMap"s. They can
alpar@40
   100
make arithmetic operations between one or two maps (negation, scaling,
alpar@40
   101
addition, multiplication etc.) or e.g. convert a map to another one
alpar@40
   102
of different Value type.
alpar@40
   103
kpeter@50
   104
The typical usage of this classes is passing implicit maps to
alpar@40
   105
algorithms.  If a function type algorithm is called then the function
alpar@40
   106
type map adaptors can be used comfortable. For example let's see the
alpar@40
   107
usage of map adaptors with the \c graphToEps() function:
alpar@40
   108
\code
alpar@40
   109
  Color nodeColor(int deg) {
alpar@40
   110
    if (deg >= 2) {
alpar@40
   111
      return Color(0.5, 0.0, 0.5);
alpar@40
   112
    } else if (deg == 1) {
alpar@40
   113
      return Color(1.0, 0.5, 1.0);
alpar@40
   114
    } else {
alpar@40
   115
      return Color(0.0, 0.0, 0.0);
alpar@40
   116
    }
alpar@40
   117
  }
alpar@40
   118
  
alpar@40
   119
  Graph::NodeMap<int> degree_map(graph);
alpar@40
   120
  
alpar@40
   121
  graphToEps(graph, "graph.eps")
alpar@40
   122
    .coords(coords).scaleToA4().undirected()
alpar@40
   123
    .nodeColors(composeMap(functorMap(nodeColor), degree_map)) 
alpar@40
   124
    .run();
alpar@40
   125
\endcode 
alpar@40
   126
The \c functorMap() function makes an \c int to \c Color map from the
alpar@40
   127
\e nodeColor() function. The \c composeMap() compose the \e degree_map
alpar@40
   128
and the previous created map. The composed map is proper function to
alpar@40
   129
get color of each node.
alpar@40
   130
alpar@40
   131
The usage with class type algorithms is little bit harder. In this
alpar@40
   132
case the function type map adaptors can not be used, because the
kpeter@50
   133
function map adaptors give back temporary objects.
alpar@40
   134
\code
alpar@40
   135
  Graph graph;
alpar@40
   136
  
alpar@40
   137
  typedef Graph::EdgeMap<double> DoubleEdgeMap;
alpar@40
   138
  DoubleEdgeMap length(graph);
alpar@40
   139
  DoubleEdgeMap speed(graph);
alpar@40
   140
  
alpar@40
   141
  typedef DivMap<DoubleEdgeMap, DoubleEdgeMap> TimeMap;
alpar@40
   142
  
alpar@40
   143
  TimeMap time(length, speed);
alpar@40
   144
  
alpar@40
   145
  Dijkstra<Graph, TimeMap> dijkstra(graph, time);
alpar@40
   146
  dijkstra.run(source, target);
alpar@40
   147
\endcode
alpar@40
   148
alpar@40
   149
We have a length map and a maximum speed map on a graph. The minimum
alpar@40
   150
time to pass the edge can be calculated as the division of the two
alpar@40
   151
maps which can be done implicitly with the \c DivMap template
alpar@40
   152
class. We use the implicit minimum time map as the length map of the
alpar@40
   153
\c Dijkstra algorithm.
alpar@40
   154
*/
alpar@40
   155
alpar@40
   156
/**
alpar@40
   157
@defgroup matrices Matrices 
alpar@40
   158
@ingroup datas
kpeter@50
   159
\brief Two dimensional data storages implemented in LEMON.
alpar@40
   160
kpeter@50
   161
This group describes two dimensional data storages implemented in LEMON.
alpar@40
   162
*/
alpar@40
   163
alpar@40
   164
/**
alpar@40
   165
@defgroup paths Path Structures
alpar@40
   166
@ingroup datas
alpar@40
   167
\brief Path structures implemented in LEMON.
alpar@40
   168
kpeter@50
   169
This group describes the path structures implemented in LEMON.
alpar@40
   170
kpeter@50
   171
LEMON provides flexible data structures to work with paths.
kpeter@50
   172
All of them have similar interfaces and they can be copied easily with
kpeter@50
   173
assignment operators and copy constructors. This makes it easy and
alpar@40
   174
efficient to have e.g. the Dijkstra algorithm to store its result in
alpar@40
   175
any kind of path structure.
alpar@40
   176
alpar@40
   177
\sa lemon::concepts::Path
alpar@40
   178
alpar@40
   179
*/
alpar@40
   180
alpar@40
   181
/**
alpar@40
   182
@defgroup auxdat Auxiliary Data Structures
alpar@40
   183
@ingroup datas
kpeter@50
   184
\brief Auxiliary data structures implemented in LEMON.
alpar@40
   185
kpeter@50
   186
This group describes some data structures implemented in LEMON in
alpar@40
   187
order to make it easier to implement combinatorial algorithms.
alpar@40
   188
*/
alpar@40
   189
alpar@40
   190
alpar@40
   191
/**
alpar@40
   192
@defgroup algs Algorithms
alpar@40
   193
\brief This group describes the several algorithms
alpar@40
   194
implemented in LEMON.
alpar@40
   195
alpar@40
   196
This group describes the several algorithms
alpar@40
   197
implemented in LEMON.
alpar@40
   198
*/
alpar@40
   199
alpar@40
   200
/**
alpar@40
   201
@defgroup search Graph Search
alpar@40
   202
@ingroup algs
kpeter@50
   203
\brief Common graph search algorithms.
alpar@40
   204
kpeter@50
   205
This group describes the common graph search algorithms like 
kpeter@50
   206
Breadth-first search (Bfs) and Depth-first search (Dfs).
alpar@40
   207
*/
alpar@40
   208
alpar@40
   209
/**
alpar@40
   210
@defgroup shortest_path Shortest Path algorithms
alpar@40
   211
@ingroup algs
kpeter@50
   212
\brief Algorithms for finding shortest paths.
alpar@40
   213
kpeter@50
   214
This group describes the algorithms for finding shortest paths in graphs.
alpar@40
   215
*/
alpar@40
   216
alpar@40
   217
/** 
alpar@40
   218
@defgroup max_flow Maximum Flow algorithms 
alpar@40
   219
@ingroup algs 
kpeter@50
   220
\brief Algorithms for finding maximum flows.
alpar@40
   221
alpar@40
   222
This group describes the algorithms for finding maximum flows and
alpar@40
   223
feasible circulations.
alpar@40
   224
kpeter@50
   225
The maximum flow problem is to find a flow between a single source and
kpeter@50
   226
a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
alpar@40
   227
directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
alpar@40
   228
function and given \f$s, t \in V\f$ source and target node. The
kpeter@50
   229
maximum flow is the \f$f_a\f$ solution of the next optimization problem:
alpar@40
   230
alpar@40
   231
\f[ 0 \le f_a \le c_a \f]
kpeter@50
   232
\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \qquad \forall u \in V \setminus \{s,t\}\f]
alpar@40
   233
\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
alpar@40
   234
kpeter@50
   235
LEMON contains several algorithms for solving maximum flow problems:
alpar@40
   236
- \ref lemon::EdmondsKarp "Edmonds-Karp" 
alpar@40
   237
- \ref lemon::Preflow "Goldberg's Preflow algorithm"
kpeter@50
   238
- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
alpar@40
   239
- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
alpar@40
   240
kpeter@50
   241
In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
alpar@40
   242
fastest method to compute the maximum flow. All impelementations
kpeter@50
   243
provides functions to query the minimum cut, which is the dual linear
kpeter@50
   244
programming problem of the maximum flow.
alpar@40
   245
alpar@40
   246
*/
alpar@40
   247
alpar@40
   248
/**
alpar@40
   249
@defgroup min_cost_flow Minimum Cost Flow algorithms
alpar@40
   250
@ingroup algs
alpar@40
   251
kpeter@50
   252
\brief Algorithms for finding minimum cost flows and circulations.
alpar@40
   253
alpar@40
   254
This group describes the algorithms for finding minimum cost flows and
alpar@40
   255
circulations.  
alpar@40
   256
*/
alpar@40
   257
alpar@40
   258
/**
alpar@40
   259
@defgroup min_cut Minimum Cut algorithms 
alpar@40
   260
@ingroup algs 
alpar@40
   261
kpeter@50
   262
\brief Algorithms for finding minimum cut in graphs.
alpar@40
   263
alpar@40
   264
This group describes the algorithms for finding minimum cut in graphs.
alpar@40
   265
alpar@40
   266
The minimum cut problem is to find a non-empty and non-complete
alpar@40
   267
\f$X\f$ subset of the vertices with minimum overall capacity on
alpar@40
   268
outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
alpar@40
   269
\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
kpeter@50
   270
cut is the \f$X\f$ solution of the next optimization problem:
alpar@40
   271
alpar@40
   272
\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
alpar@40
   273
kpeter@50
   274
LEMON contains several algorithms related to minimum cut problems:
alpar@40
   275
kpeter@50
   276
- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
alpar@40
   277
  in directed graphs  
kpeter@50
   278
- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
alpar@40
   279
  calculate minimum cut in undirected graphs
kpeter@50
   280
- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
alpar@40
   281
  pairs minimum cut in undirected graphs
alpar@40
   282
alpar@40
   283
If you want to find minimum cut just between two distinict nodes,
alpar@40
   284
please see the \ref max_flow "Maximum Flow page".
alpar@40
   285
alpar@40
   286
*/
alpar@40
   287
alpar@40
   288
/**
alpar@40
   289
@defgroup graph_prop Connectivity and other graph properties
alpar@40
   290
@ingroup algs
kpeter@50
   291
\brief Algorithms for discovering the graph properties
alpar@40
   292
kpeter@50
   293
This group describes the algorithms for discovering the graph properties
kpeter@50
   294
like connectivity, bipartiteness, euler property, simplicity etc.
alpar@40
   295
alpar@40
   296
\image html edge_biconnected_components.png
alpar@40
   297
\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
alpar@40
   298
*/
alpar@40
   299
alpar@40
   300
/**
alpar@40
   301
@defgroup planar Planarity embedding and drawing
alpar@40
   302
@ingroup algs
kpeter@50
   303
\brief Algorithms for planarity checking, embedding and drawing
alpar@40
   304
kpeter@50
   305
This group describes the algorithms for planarity checking, embedding and drawing.
alpar@40
   306
alpar@40
   307
\image html planar.png
alpar@40
   308
\image latex planar.eps "Plane graph" width=\textwidth
alpar@40
   309
*/
alpar@40
   310
alpar@40
   311
/**
alpar@40
   312
@defgroup matching Matching algorithms 
alpar@40
   313
@ingroup algs
kpeter@50
   314
\brief Algorithms for finding matchings in graphs and bipartite graphs.
alpar@40
   315
kpeter@50
   316
This group contains algorithm objects and functions to calculate
alpar@40
   317
matchings in graphs and bipartite graphs. The general matching problem is
alpar@40
   318
finding a subset of the edges which does not shares common endpoints.
alpar@40
   319
 
alpar@40
   320
There are several different algorithms for calculate matchings in
alpar@40
   321
graphs.  The matching problems in bipartite graphs are generally
alpar@40
   322
easier than in general graphs. The goal of the matching optimization
alpar@40
   323
can be the finding maximum cardinality, maximum weight or minimum cost
alpar@40
   324
matching. The search can be constrained to find perfect or
alpar@40
   325
maximum cardinality matching.
alpar@40
   326
alpar@40
   327
Lemon contains the next algorithms:
alpar@40
   328
- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp 
alpar@40
   329
  augmenting path algorithm for calculate maximum cardinality matching in 
alpar@40
   330
  bipartite graphs
alpar@40
   331
- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel 
alpar@40
   332
  algorithm for calculate maximum cardinality matching in bipartite graphs 
alpar@40
   333
- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching" 
alpar@40
   334
  Successive shortest path algorithm for calculate maximum weighted matching 
alpar@40
   335
  and maximum weighted bipartite matching in bipartite graph
alpar@40
   336
- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching" 
alpar@40
   337
  Successive shortest path algorithm for calculate minimum cost maximum 
alpar@40
   338
  matching in bipartite graph
alpar@40
   339
- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
alpar@40
   340
  for calculate maximum cardinality matching in general graph
alpar@40
   341
- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
alpar@40
   342
  shrinking algorithm for calculate maximum weighted matching in general
alpar@40
   343
  graph
alpar@40
   344
- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
alpar@40
   345
  Edmond's blossom shrinking algorithm for calculate maximum weighted
alpar@40
   346
  perfect matching in general graph
alpar@40
   347
alpar@40
   348
\image html bipartite_matching.png
alpar@40
   349
\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
alpar@40
   350
alpar@40
   351
*/
alpar@40
   352
alpar@40
   353
/**
alpar@40
   354
@defgroup spantree Minimum Spanning Tree algorithms
alpar@40
   355
@ingroup algs
kpeter@50
   356
\brief Algorithms for finding a minimum cost spanning tree in a graph.
alpar@40
   357
kpeter@50
   358
This group describes the algorithms for finding a minimum cost spanning
alpar@40
   359
tree in a graph
alpar@40
   360
*/
alpar@40
   361
alpar@40
   362
alpar@40
   363
/**
alpar@40
   364
@defgroup auxalg Auxiliary algorithms
alpar@40
   365
@ingroup algs
kpeter@50
   366
\brief Auxiliary algorithms implemented in LEMON.
alpar@40
   367
kpeter@50
   368
This group describes some algorithms implemented in LEMON
kpeter@50
   369
in order to make it easier to implement complex algorithms.
alpar@40
   370
*/
alpar@40
   371
alpar@40
   372
/**
alpar@40
   373
@defgroup approx Approximation algorithms
kpeter@50
   374
\brief Approximation algorithms.
alpar@40
   375
kpeter@50
   376
This group describes the approximation and heuristic algorithms
kpeter@50
   377
implemented in LEMON.
alpar@40
   378
*/
alpar@40
   379
alpar@40
   380
/**
alpar@40
   381
@defgroup gen_opt_group General Optimization Tools
alpar@40
   382
\brief This group describes some general optimization frameworks
alpar@40
   383
implemented in LEMON.
alpar@40
   384
alpar@40
   385
This group describes some general optimization frameworks
alpar@40
   386
implemented in LEMON.
alpar@40
   387
alpar@40
   388
*/
alpar@40
   389
alpar@40
   390
/**
alpar@40
   391
@defgroup lp_group Lp and Mip solvers
alpar@40
   392
@ingroup gen_opt_group
alpar@40
   393
\brief Lp and Mip solver interfaces for LEMON.
alpar@40
   394
alpar@40
   395
This group describes Lp and Mip solver interfaces for LEMON. The
alpar@40
   396
various LP solvers could be used in the same manner with this
alpar@40
   397
interface.
alpar@40
   398
alpar@40
   399
*/
alpar@40
   400
alpar@40
   401
/** 
alpar@40
   402
@defgroup lp_utils Tools for Lp and Mip solvers 
alpar@40
   403
@ingroup lp_group
kpeter@50
   404
\brief Helper tools to the Lp and Mip solvers.
alpar@40
   405
alpar@40
   406
This group adds some helper tools to general optimization framework
alpar@40
   407
implemented in LEMON.
alpar@40
   408
*/
alpar@40
   409
alpar@40
   410
/**
alpar@40
   411
@defgroup metah Metaheuristics
alpar@40
   412
@ingroup gen_opt_group
alpar@40
   413
\brief Metaheuristics for LEMON library.
alpar@40
   414
kpeter@50
   415
This group describes some metaheuristic optimization tools.
alpar@40
   416
*/
alpar@40
   417
alpar@40
   418
/**
alpar@40
   419
@defgroup utils Tools and Utilities 
kpeter@50
   420
\brief Tools and utilities for programming in LEMON
alpar@40
   421
kpeter@50
   422
Tools and utilities for programming in LEMON.
alpar@40
   423
*/
alpar@40
   424
alpar@40
   425
/**
alpar@40
   426
@defgroup gutils Basic Graph Utilities
alpar@40
   427
@ingroup utils
kpeter@50
   428
\brief Simple basic graph utilities.
alpar@40
   429
alpar@40
   430
This group describes some simple basic graph utilities.
alpar@40
   431
*/
alpar@40
   432
alpar@40
   433
/**
alpar@40
   434
@defgroup misc Miscellaneous Tools
alpar@40
   435
@ingroup utils
kpeter@50
   436
\brief Tools for development, debugging and testing.
kpeter@50
   437
kpeter@50
   438
This group describes several useful tools for development,
alpar@40
   439
debugging and testing.
alpar@40
   440
*/
alpar@40
   441
alpar@40
   442
/**
alpar@40
   443
@defgroup timecount Time measuring and Counting
alpar@40
   444
@ingroup misc
kpeter@50
   445
\brief Simple tools for measuring the performance of algorithms.
kpeter@50
   446
kpeter@50
   447
This group describes simple tools for measuring the performance
alpar@40
   448
of algorithms.
alpar@40
   449
*/
alpar@40
   450
alpar@40
   451
/**
alpar@40
   452
@defgroup graphbits Tools for Graph Implementation
alpar@40
   453
@ingroup utils
kpeter@50
   454
\brief Tools to make it easier to create graphs.
alpar@40
   455
kpeter@50
   456
This group describes the tools that makes it easier to create graphs and
alpar@40
   457
the maps that dynamically update with the graph changes.
alpar@40
   458
*/
alpar@40
   459
alpar@40
   460
/**
alpar@40
   461
@defgroup exceptions Exceptions
alpar@40
   462
@ingroup utils
kpeter@50
   463
\brief Exceptions defined in LEMON.
kpeter@50
   464
kpeter@50
   465
This group describes the exceptions defined in LEMON.
alpar@40
   466
*/
alpar@40
   467
alpar@40
   468
/**
alpar@40
   469
@defgroup io_group Input-Output
kpeter@50
   470
\brief Graph Input-Output methods
alpar@40
   471
kpeter@50
   472
This group describes the tools for importing and exporting graphs 
alpar@40
   473
and graph related data. Now it supports the LEMON format, the
kpeter@50
   474
\c DIMACS format and the encapsulated postscript (EPS) format.
alpar@40
   475
*/
alpar@40
   476
alpar@40
   477
/**
alpar@40
   478
@defgroup lemon_io Lemon Input-Output
alpar@40
   479
@ingroup io_group
alpar@40
   480
\brief Reading and writing LEMON format
alpar@40
   481
kpeter@50
   482
This group describes methods for reading and writing LEMON format. 
kpeter@50
   483
You can find more about this format on the \ref graph-io-page "Graph Input-Output"
alpar@40
   484
tutorial pages.
alpar@40
   485
*/
alpar@40
   486
alpar@40
   487
/**
alpar@40
   488
@defgroup section_io Section readers and writers
alpar@40
   489
@ingroup lemon_io
kpeter@71
   490
\brief Section readers and writers for LEMON Input-Output.
alpar@40
   491
kpeter@71
   492
This group describes section reader and writer classes that can be 
kpeter@71
   493
attached to \ref LemonReader and \ref LemonWriter.
alpar@40
   494
*/
alpar@40
   495
alpar@40
   496
/**
kpeter@71
   497
@defgroup item_io Item readers and writers
alpar@40
   498
@ingroup lemon_io
kpeter@71
   499
\brief Item readers and writers for LEMON Input-Output.
alpar@40
   500
kpeter@71
   501
This group describes reader and writer classes for various data types
kpeter@71
   502
(e.g. map or attribute values). These classes can be attached to
kpeter@71
   503
\ref LemonReader and \ref LemonWriter.
alpar@40
   504
*/
alpar@40
   505
alpar@40
   506
/**
alpar@40
   507
@defgroup eps_io Postscript exporting
alpar@40
   508
@ingroup io_group
alpar@40
   509
\brief General \c EPS drawer and graph exporter
alpar@40
   510
kpeter@50
   511
This group describes general \c EPS drawing methods and special
alpar@40
   512
graph exporting tools. 
alpar@40
   513
*/
alpar@40
   514
alpar@40
   515
alpar@40
   516
/**
alpar@40
   517
@defgroup concept Concepts
alpar@40
   518
\brief Skeleton classes and concept checking classes
alpar@40
   519
alpar@40
   520
This group describes the data/algorithm skeletons and concept checking
alpar@40
   521
classes implemented in LEMON.
alpar@40
   522
alpar@40
   523
The purpose of the classes in this group is fourfold.
alpar@40
   524
 
alpar@40
   525
- These classes contain the documentations of the concepts. In order
alpar@40
   526
  to avoid document multiplications, an implementation of a concept
alpar@40
   527
  simply refers to the corresponding concept class.
alpar@40
   528
alpar@40
   529
- These classes declare every functions, <tt>typedef</tt>s etc. an
alpar@40
   530
  implementation of the concepts should provide, however completely
alpar@40
   531
  without implementations and real data structures behind the
alpar@40
   532
  interface. On the other hand they should provide nothing else. All
alpar@40
   533
  the algorithms working on a data structure meeting a certain concept
alpar@40
   534
  should compile with these classes. (Though it will not run properly,
alpar@40
   535
  of course.) In this way it is easily to check if an algorithm
alpar@40
   536
  doesn't use any extra feature of a certain implementation.
alpar@40
   537
alpar@40
   538
- The concept descriptor classes also provide a <em>checker class</em>
kpeter@50
   539
  that makes it possible to check whether a certain implementation of a
alpar@40
   540
  concept indeed provides all the required features.
alpar@40
   541
alpar@40
   542
- Finally, They can serve as a skeleton of a new implementation of a concept.
alpar@40
   543
alpar@40
   544
*/
alpar@40
   545
alpar@40
   546
alpar@40
   547
/**
alpar@40
   548
@defgroup graph_concepts Graph Structure Concepts
alpar@40
   549
@ingroup concept
alpar@40
   550
\brief Skeleton and concept checking classes for graph structures
alpar@40
   551
kpeter@50
   552
This group describes the skeletons and concept checking classes of LEMON's
alpar@40
   553
graph structures and helper classes used to implement these.
alpar@40
   554
*/
alpar@40
   555
alpar@40
   556
/* --- Unused group
alpar@40
   557
@defgroup experimental Experimental Structures and Algorithms
kpeter@50
   558
This group describes some Experimental structures and algorithms.
alpar@40
   559
The stuff here is subject to change.
alpar@40
   560
*/
alpar@40
   561
alpar@40
   562
/**
alpar@40
   563
\anchor demoprograms
alpar@40
   564
alpar@40
   565
@defgroup demos Demo programs
alpar@40
   566
alpar@40
   567
Some demo programs are listed here. Their full source codes can be found in
alpar@40
   568
the \c demo subdirectory of the source tree.
alpar@40
   569
alpar@41
   570
It order to compile them, use <tt>--enable-demo</tt> configure option when
alpar@41
   571
build the library.
alpar@40
   572
*/
alpar@40
   573
alpar@40
   574
/**
alpar@40
   575
@defgroup tools Standalone utility applications
alpar@40
   576
alpar@40
   577
Some utility applications are listed here. 
alpar@40
   578
alpar@40
   579
The standard compilation procedure (<tt>./configure;make</tt>) will compile
alpar@40
   580
them, as well. 
alpar@40
   581
*/
alpar@40
   582