doc/groups.dox
author deba
Fri, 31 Aug 2007 08:40:49 +0000
changeset 2469 d6f12a9b5cbf
parent 2391 14a343be7a5a
child 2489 48dddc283cfc
permissions -rw-r--r--
Invalid assignments ambiguity handling
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@2391
     5
 * Copyright (C) 2003-2007
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.
alpar@1402
   100
*/
alpar@1402
   101
alpar@1043
   102
/**
alpar@2072
   103
@defgroup matrices Matrices 
alpar@2072
   104
@ingroup datas
alpar@2072
   105
\brief Two dimensional data storages.
alpar@2072
   106
deba@2084
   107
Two dimensional data storages.
alpar@2072
   108
*/
alpar@2072
   109
deba@2084
   110
/**
deba@2084
   111
@defgroup paths Path Structures
deba@2084
   112
@ingroup datas
deba@2084
   113
\brief Path structures implemented in LEMON.
deba@2084
   114
deba@2084
   115
LEMON provides flexible data structures
deba@2084
   116
to work with paths.
deba@2084
   117
deba@2084
   118
All of them have the same interface, especially they can be built or extended
deba@2084
   119
using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
deba@2084
   120
algorithm to store its result in any kind of path structure.
deba@2084
   121
alpar@2260
   122
\sa lemon::concepts::Path
deba@2084
   123
deba@2084
   124
*/
alpar@2072
   125
alpar@2072
   126
/**
alpar@678
   127
@defgroup auxdat Auxiliary Data Structures
alpar@678
   128
@ingroup datas
alpar@921
   129
\brief Some data structures implemented in LEMON.
alpar@406
   130
alpar@921
   131
This group describes the data structures implemented in LEMON in
alpar@678
   132
order to make it easier to implement combinatorial algorithms.
alpar@678
   133
*/
alpar@406
   134
alpar@785
   135
alpar@785
   136
/**
deba@2084
   137
@defgroup algs Algorithms
deba@2084
   138
\brief This group describes the several algorithms
alpar@921
   139
implemented in LEMON.
alpar@947
   140
deba@2084
   141
This group describes the several algorithms
alpar@947
   142
implemented in LEMON.
alpar@947
   143
*/
alpar@947
   144
alpar@947
   145
/**
deba@2376
   146
@defgroup search Graph Search
deba@2084
   147
@ingroup algs
deba@2376
   148
\brief This group contains the common graph
deba@2376
   149
search algorithms.
alpar@947
   150
deba@2376
   151
This group contains the common graph
deba@2376
   152
search algorithms like Bfs and Dfs.
alpar@678
   153
*/
alpar@678
   154
alpar@678
   155
/**
deba@2376
   156
@defgroup shortest_path Shortest Path algorithms
deba@2084
   157
@ingroup algs
alpar@758
   158
\brief This group describes the algorithms
deba@2376
   159
for finding shortest paths.
deba@2060
   160
deba@2376
   161
This group describes the algorithms for finding shortest paths in
deba@2376
   162
graphs.
deba@2376
   163
deba@2376
   164
*/
deba@2376
   165
deba@2376
   166
/** 
deba@2376
   167
@defgroup max_flow Maximum Flow algorithms 
deba@2376
   168
@ingroup algs 
deba@2376
   169
\brief This group describes the algorithms for finding maximum flows.
deba@2376
   170
deba@2377
   171
This group describes the algorithms for finding maximum flows and
deba@2377
   172
feasible circulations.
deba@2060
   173
deba@2060
   174
\image html flow.png
deba@2060
   175
\image latex flow.eps "Graph flow" width=\textwidth
alpar@678
   176
*/
alpar@678
   177
alpar@678
   178
/**
deba@2376
   179
@defgroup min_cost_flow Minimum Cost Flow algorithms
deba@2376
   180
@ingroup algs
deba@2376
   181
deba@2376
   182
\brief This group describes the algorithms
deba@2376
   183
for finding minimum cost flows and circulations.
deba@2376
   184
deba@2376
   185
This group describes the algorithms for finding minimum cost flows and
deba@2376
   186
circulations.  
deba@2376
   187
*/
deba@2376
   188
deba@2376
   189
/**
deba@2376
   190
@defgroup min_cut Minimum Cut algorithms
deba@2376
   191
@ingroup algs
deba@2376
   192
\brief This group describes the algorithms
deba@2376
   193
for finding minimum cut in graphs.
deba@2376
   194
deba@2376
   195
This group describes the algorithms
deba@2376
   196
for finding minimum cut in graphs.
deba@2376
   197
*/
deba@2376
   198
deba@2376
   199
/**
deba@2429
   200
@defgroup graph_prop Connectivity and other graph properties
deba@2084
   201
@ingroup algs
deba@1750
   202
\brief This group describes the algorithms
deba@2429
   203
for discover the graph properties
deba@2060
   204
deba@2429
   205
This group describes the algorithms for discover the graph properties
deba@2429
   206
like connectivity, bipartiteness, euler property, simplicity, etc...
deba@2060
   207
deba@2060
   208
\image html edge_biconnected_components.png
deba@2060
   209
\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
deba@1750
   210
*/
deba@1750
   211
deba@1750
   212
/**
deba@2376
   213
@defgroup matching Matching algorithms 
deba@2084
   214
@ingroup algs
deba@2042
   215
\brief This group describes the algorithms
deba@2042
   216
for find matchings in graphs and bipartite graphs.
deba@2060
   217
deba@2060
   218
This group provides some algorithm objects and function
deba@2060
   219
to calculate matchings in graphs and bipartite graphs.
deba@2060
   220
deba@2060
   221
\image html bipartite_matching.png
deba@2060
   222
\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
deba@2060
   223
deba@2042
   224
*/
deba@2042
   225
deba@2042
   226
/**
deba@2376
   227
@defgroup spantree Minimum Spanning Tree algorithms
deba@2084
   228
@ingroup algs
alpar@2117
   229
\brief This group contains the algorithms for finding a minimum cost spanning
deba@2084
   230
tree in a graph
deba@2084
   231
alpar@2117
   232
This group contains the algorithms for finding a minimum cost spanning
deba@2084
   233
tree in a graph
deba@2084
   234
*/
deba@2084
   235
deba@2084
   236
deba@2084
   237
/**
deba@2376
   238
@defgroup auxalg Auxiliary algorithms
deba@2084
   239
@ingroup algs
deba@2084
   240
\brief Some algorithms implemented in LEMON.
deba@2084
   241
deba@2084
   242
This group describes the algorithms in LEMON in order to make 
deba@2084
   243
it easier to implement complex algorithms.
deba@2376
   244
*/
deba@2084
   245
deba@2376
   246
/**
deba@2376
   247
@defgroup approx Approximation algorithms
deba@2376
   248
\brief Approximation algorithms
deba@2376
   249
deba@2376
   250
Approximation and heuristic algorithms
deba@2084
   251
*/
deba@2084
   252
deba@2084
   253
/**
deba@2084
   254
@defgroup gen_opt_group General Optimization Tools
deba@2084
   255
\brief This group describes some general optimization frameworks
deba@2084
   256
implemented in LEMON.
deba@2084
   257
deba@2084
   258
This group describes some general optimization frameworks
deba@2084
   259
implemented in LEMON.
deba@2084
   260
alpar@1151
   261
*/
alpar@1151
   262
deba@2370
   263
/**
deba@2371
   264
@defgroup lp_group Lp and Mip solvers
deba@2370
   265
@ingroup gen_opt_group
deba@2370
   266
\brief Lp and Mip solver interfaces for LEMON.
deba@2370
   267
deba@2370
   268
This group describes Lp and Mip solver interfaces for LEMON. The
deba@2370
   269
various LP solvers could be used in the same manner with this
deba@2370
   270
interface.
deba@2370
   271
deba@2370
   272
*/
deba@2370
   273
deba@2368
   274
/** 
deba@2370
   275
@defgroup lp_utils Tools for Lp and Mip solvers 
deba@2370
   276
@ingroup lp_group
deba@2370
   277
\brief This group adds some helper tools to the Lp and Mip solvers
deba@2370
   278
implemented in LEMON.
deba@2368
   279
deba@2368
   280
This group adds some helper tools to general optimization framework
deba@2368
   281
implemented in LEMON.
deba@2368
   282
*/
deba@2368
   283
alpar@1151
   284
/**
deba@2370
   285
@defgroup metah Metaheuristics
deba@2370
   286
@ingroup gen_opt_group
deba@2370
   287
\brief Metaheuristics for LEMON library.
deba@2370
   288
deba@2370
   289
This group contains some metaheuristic optimization tools.
deba@2370
   290
*/
deba@2370
   291
deba@2370
   292
/**
deba@2376
   293
@defgroup utils Tools and Utilities 
deba@2376
   294
\brief Tools and Utilities for Programming in LEMON
deba@2376
   295
deba@2376
   296
Tools and Utilities for Programming in LEMON
deba@2376
   297
*/
deba@2376
   298
deba@2376
   299
/**
deba@2376
   300
@defgroup gutils Basic Graph Utilities
deba@2376
   301
@ingroup utils
deba@2376
   302
\brief This group describes some simple basic graph utilities.
deba@2376
   303
deba@2376
   304
This group describes some simple basic graph utilities.
deba@2376
   305
*/
deba@2376
   306
deba@2376
   307
/**
alpar@678
   308
@defgroup misc Miscellaneous Tools
deba@2376
   309
@ingroup utils
alpar@678
   310
Here you can find several useful tools for development,
alpar@678
   311
debugging and testing.
alpar@678
   312
*/
alpar@678
   313
deba@2376
   314
alpar@678
   315
/**
alpar@1847
   316
@defgroup timecount Time measuring and Counting
alpar@1847
   317
@ingroup misc
alpar@1847
   318
Here you can find simple tools for measuring the performance
alpar@1847
   319
of algorithms.
alpar@1847
   320
*/
alpar@1847
   321
alpar@1847
   322
/**
deba@2376
   323
@defgroup graphbits Tools for Graph Implementation
deba@2376
   324
@ingroup utils
deba@2376
   325
\brief Tools to Make It Easier to Make Graphs.
deba@2376
   326
deba@2376
   327
This group describes the tools that makes it easier to make graphs and
deba@2376
   328
the maps that dynamically update with the graph changes.
deba@2376
   329
*/
deba@2376
   330
deba@2376
   331
/**
deba@2376
   332
@defgroup exceptions Exceptions
deba@2376
   333
@ingroup utils
deba@2376
   334
This group contains the exceptions thrown by LEMON library
deba@2376
   335
*/
deba@2376
   336
deba@2376
   337
/**
deba@2016
   338
@defgroup io_group Input-Output
deba@2084
   339
\brief Several Graph Input-Output methods
deba@2084
   340
deba@2084
   341
Here you can find tools for importing and exporting graphs 
deba@2084
   342
and graph related data. Now it supports the LEMON format, the
alpar@2117
   343
\c DIMACS format and the encapsulated postscript format.
deba@2084
   344
*/
deba@2084
   345
deba@2084
   346
/**
deba@2084
   347
@defgroup lemon_io Lemon Input-Output
deba@2084
   348
@ingroup io_group
deba@2084
   349
\brief Reading and writing LEMON format
deba@2084
   350
deba@2084
   351
Methods for reading and writing LEMON format. More about this
deba@2084
   352
format you can find on the \ref graph-io-page "Graph Input-Output"
deba@2084
   353
tutorial pages.
alpar@1287
   354
*/
alpar@1287
   355
alpar@1287
   356
/**
deba@2016
   357
@defgroup section_io Section readers and writers
deba@2084
   358
@ingroup lemon_io
deba@2016
   359
\brief Section readers and writers for lemon Input-Output.
deba@2016
   360
deba@2016
   361
Here you can find which section readers and writers can attach to
deba@2016
   362
the LemonReader and LemonWriter.
deba@2016
   363
*/
deba@2016
   364
deba@2016
   365
/**
deba@2016
   366
@defgroup item_io Item Readers and Writers
deba@2084
   367
@ingroup lemon_io
deba@2016
   368
\brief Item readers and writers for lemon Input-Output.
deba@2016
   369
deba@2016
   370
The Input-Output classes can handle more data type by example
deba@2016
   371
as map or attribute value. Each of these should be written and
deba@2016
   372
read some way. The module make possible to do this.  
deba@2016
   373
*/
deba@2016
   374
deba@2016
   375
/**
deba@2084
   376
@defgroup eps_io Postscript exporting
deba@2084
   377
@ingroup io_group
alpar@2117
   378
\brief General \c EPS drawer and graph exporter
deba@2084
   379
alpar@2117
   380
This group contains general \c EPS drawing methods and special
deba@2084
   381
graph exporting tools. 
deba@2084
   382
*/
deba@2084
   383
deba@2084
   384
deba@2084
   385
/**
klao@1030
   386
@defgroup concept Concepts
klao@959
   387
\brief Skeleton classes and concept checking classes
alpar@794
   388
klao@959
   389
This group describes the data/algorithm skeletons and concept checking
klao@1030
   390
classes implemented in LEMON.
klao@1030
   391
alpar@2117
   392
The purpose of the classes in this group is fourfold.
alpar@2117
   393
 
alpar@2117
   394
- These classes contain the documentations of the concepts. In order
alpar@2117
   395
  to avoid document multiplications, an implementation of a concept
alpar@2117
   396
  simply refers to the corresponding concept class.
klao@1030
   397
alpar@2233
   398
- These classes declare every functions, <tt>typedef</tt>s etc. an
alpar@2117
   399
  implementation of the concepts should provide, however completely
alpar@2117
   400
  without implementations and real data structures behind the
alpar@2117
   401
  interface. On the other hand they should provide nothing else. All
alpar@2117
   402
  the algorithms working on a data structure meeting a certain concept
alpar@2117
   403
  should compile with these classes. (Though it will not run properly,
alpar@2117
   404
  of course.) In this way it is easily to check if an algorithm
alpar@2117
   405
  doesn't use any extra feature of a certain implementation.
alpar@2117
   406
alpar@2233
   407
- The concept descriptor classes also provide a <em>checker class</em>
alpar@2117
   408
  that makes it possible check whether a certain implementation of a
alpar@2117
   409
  concept indeed provides all the required features.
alpar@2117
   410
alpar@2117
   411
- Finally, They can serve as a skeleton of a new implementation of a concept.
klao@1030
   412
alpar@794
   413
*/
alpar@794
   414
deba@2084
   415
klao@1030
   416
/**
klao@1030
   417
@defgroup graph_concepts Graph Structure Concepts
klao@1030
   418
@ingroup concept
klao@1030
   419
\brief Skeleton and concept checking classes for graph structures
klao@1030
   420
klao@1030
   421
This group contains the skeletons and concept checking classes of LEMON's
klao@1030
   422
graph structures and helper classes used to implement these.
klao@1030
   423
*/
alpar@794
   424
alpar@1587
   425
/* --- Unused group
alpar@678
   426
@defgroup experimental Experimental Structures and Algorithms
alpar@678
   427
This group contains some Experimental structures and algorithms.
alpar@678
   428
The stuff here is subject to change.
alpar@678
   429
*/
alpar@1151
   430
alpar@1558
   431
/**
athos@1582
   432
\anchor demoprograms
athos@1582
   433
alpar@1558
   434
@defgroup demos Demo programs
alpar@1558
   435
alpar@1559
   436
Some demo programs are listed here. Their full source codes can be found in
alpar@1558
   437
the \c demo subdirectory of the source tree.
alpar@1558
   438
ladanyi@1639
   439
The standard compilation procedure (<tt>./configure;make</tt>) will compile
ladanyi@1639
   440
them, as well. 
alpar@1558
   441
alpar@1558
   442
*/
alpar@1558
   443