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