doc/groups.dox
author alpar
Wed, 09 Aug 2006 12:47:31 +0000
changeset 2169 9f71586a3f74
parent 2084 59769591eb60
child 2233 b3abb7ed76a8
permissions -rw-r--r--
This script lists all the header files included directly or indirectly by a certain header file.
alpar@814
     1
alpar@678
     2
/**
alpar@678
     3
@defgroup datas Data Structures
alpar@921
     4
This group describes the several graph structures implemented in LEMON.
alpar@678
     5
*/
alpar@430
     6
alpar@678
     7
/**
alpar@678
     8
@defgroup graphs Graph Structures
alpar@678
     9
@ingroup datas
alpar@921
    10
\brief Graph structures implemented in LEMON.
alpar@430
    11
marci@1172
    12
The implementation of combinatorial algorithms heavily relies on 
marci@1172
    13
efficient graph implementations. LEMON offers data structures which are 
marci@1172
    14
planned to be easily used in an experimental phase of implementation studies, 
marci@1172
    15
and thereafter the program code can be made efficient by small modifications. 
alpar@430
    16
deba@2084
    17
The most efficient implementation of diverse applications require the
deba@2084
    18
usage of different physical graph implementations. These differences
deba@2084
    19
appear in the size of graph we require to handle, memory or time usage
deba@2084
    20
limitations or in the set of operations through which the graph can be
deba@2084
    21
accessed.  LEMON provides several physical graph structures to meet
deba@2084
    22
the diverging requirements of the possible users.  In order to save on
deba@2084
    23
running time or on memory usage, some structures may fail to provide
deba@2084
    24
some graph features like edge or node deletion.
marci@1172
    25
marci@1172
    26
Alteration of standard containers need a very limited number of 
marci@1172
    27
operations, these together satisfy the everyday requirements. 
alpar@2117
    28
In the case of graph structures, different operations are needed which do 
alpar@2006
    29
not alter the physical graph, but gives another view. If some nodes or 
marci@1172
    30
edges have to be hidden or the reverse oriented graph have to be used, then 
alpar@2117
    31
this is the case. It also may happen that in a flow implementation 
alpar@2006
    32
the residual graph can be accessed by another algorithm, or a node-set 
alpar@2006
    33
is to be shrunk for another algorithm. 
marci@1172
    34
LEMON also provides a variety of graphs for these requirements called 
alpar@1401
    35
\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only 
marci@1172
    36
in conjunction with other graph representation. 
alpar@430
    37
alpar@678
    38
You are free to use the graph structure that fit your requirements
alpar@678
    39
the best, most graph algorithms and auxiliary data structures can be used
marci@1172
    40
with any graph structures. 
alpar@678
    41
*/
alpar@430
    42
alpar@678
    43
/**
deba@1866
    44
@defgroup semi_adaptors Semi-Adaptors Classes for Graphs
deba@1866
    45
@ingroup graphs
deba@1866
    46
\brief Graph types between real graphs and graph adaptors.
deba@1866
    47
alpar@2117
    48
Graph types between real graphs and graph adaptors. These classes wrap
alpar@2117
    49
graphs to give new functionality as the adaptors do it. On the other
alpar@2117
    50
hand they are not light-weight structures as the adaptors.
deba@1866
    51
*/
deba@1866
    52
deba@1866
    53
/**
alpar@1043
    54
@defgroup maps Maps 
alpar@1043
    55
@ingroup datas
alpar@1043
    56
\brief Some special purpose map to make life easier.
alpar@1043
    57
alpar@1043
    58
LEMON provides several special maps that e.g. combine
alpar@1043
    59
new maps from existing ones.
alpar@1043
    60
*/
alpar@1043
    61
alpar@1402
    62
/**
alpar@1402
    63
@defgroup graph_maps Graph Maps 
alpar@1402
    64
@ingroup maps
alpar@1402
    65
\brief Special Graph-Related Maps.
alpar@1402
    66
alpar@1402
    67
These maps are specifically designed to assign values to the nodes and edges of
alpar@1402
    68
graphs.
alpar@1402
    69
*/
alpar@1402
    70
alpar@1402
    71
alpar@1402
    72
/**
alpar@1402
    73
\defgroup map_adaptors Map Adaptors
alpar@1402
    74
\ingroup maps
alpar@1402
    75
\brief Tools to create new maps from existing ones
alpar@1402
    76
alpar@1402
    77
Map adaptors are used to create "implicit" maps from other maps.
alpar@1402
    78
alpar@1536
    79
Most of them are \ref lemon::concept::ReadMap "ReadMap"s. They can
alpar@2117
    80
make arithmetic operations between one or two maps (negation, scaling,
alpar@1402
    81
addition, multiplication etc.) or e.g. convert a map to another one
alpar@1402
    82
of different Value type.
alpar@1402
    83
*/
alpar@1402
    84
alpar@1043
    85
/**
alpar@2072
    86
@defgroup matrices Matrices 
alpar@2072
    87
@ingroup datas
alpar@2072
    88
\brief Two dimensional data storages.
alpar@2072
    89
deba@2084
    90
Two dimensional data storages.
alpar@2072
    91
*/
alpar@2072
    92
deba@2084
    93
/**
deba@2084
    94
@defgroup paths Path Structures
deba@2084
    95
@ingroup datas
deba@2084
    96
\brief Path structures implemented in LEMON.
deba@2084
    97
deba@2084
    98
LEMON provides flexible data structures
deba@2084
    99
to work with paths.
deba@2084
   100
deba@2084
   101
All of them have the same interface, especially they can be built or extended
deba@2084
   102
using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
deba@2084
   103
algorithm to store its result in any kind of path structure.
deba@2084
   104
deba@2084
   105
\sa lemon::concept::Path
deba@2084
   106
deba@2084
   107
*/
alpar@2072
   108
alpar@2072
   109
/**
alpar@678
   110
@defgroup auxdat Auxiliary Data Structures
alpar@678
   111
@ingroup datas
alpar@921
   112
\brief Some data structures implemented in LEMON.
alpar@406
   113
alpar@921
   114
This group describes the data structures implemented in LEMON in
alpar@678
   115
order to make it easier to implement combinatorial algorithms.
alpar@678
   116
*/
alpar@406
   117
alpar@678
   118
/**
deba@1996
   119
@defgroup graphbits Tools to Make It Easier to Make Graphs
alpar@785
   120
@ingroup auxdat
deba@1996
   121
\brief Tools to Make It Easier to Make Graphs.
alpar@785
   122
deba@1996
   123
This group describes the tools that makes it easier to make graphs and
deba@1996
   124
the maps that dynamically update with the graph changes.
alpar@785
   125
*/
alpar@785
   126
alpar@785
   127
/**
deba@2084
   128
@defgroup algs Algorithms
deba@2084
   129
\brief This group describes the several algorithms
alpar@921
   130
implemented in LEMON.
alpar@947
   131
deba@2084
   132
This group describes the several algorithms
alpar@947
   133
implemented in LEMON.
alpar@947
   134
*/
alpar@947
   135
alpar@947
   136
/**
alpar@947
   137
@defgroup gutils General Graph Utilities
deba@2084
   138
@ingroup algs
alpar@947
   139
\brief This group describes some simple general graph utilities.
alpar@947
   140
alpar@947
   141
This group describes some simple general graph utilities.
alpar@678
   142
*/
alpar@678
   143
alpar@678
   144
/**
alpar@758
   145
@defgroup flowalgs Path and Flow Algorithms
deba@2084
   146
@ingroup algs
alpar@758
   147
\brief This group describes the algorithms
alpar@758
   148
for finding paths and flows in graphs.
deba@2060
   149
deba@2060
   150
This group describes the algorithms
deba@2060
   151
for finding paths and flows in graphs.
deba@2060
   152
deba@2060
   153
\image html flow.png
deba@2060
   154
\image latex flow.eps "Graph flow" width=\textwidth
alpar@678
   155
*/
alpar@678
   156
alpar@678
   157
/**
deba@1750
   158
@defgroup topology Topology related algorithms
deba@2084
   159
@ingroup algs
deba@1750
   160
\brief This group describes the algorithms
deba@1750
   161
for discover the topology of the graphs.
deba@2060
   162
deba@2060
   163
This group describes the algorithms
deba@2060
   164
for discover the topology of the graphs.
deba@2060
   165
deba@2060
   166
\image html edge_biconnected_components.png
deba@2060
   167
\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
deba@2060
   168
deba@1750
   169
*/
deba@1750
   170
deba@1750
   171
/**
deba@2042
   172
@defgroup matching Matching algorithms in graphs and bipartite graphs
deba@2084
   173
@ingroup algs
deba@2042
   174
\brief This group describes the algorithms
deba@2042
   175
for find matchings in graphs and bipartite graphs.
deba@2060
   176
deba@2060
   177
This group provides some algorithm objects and function
deba@2060
   178
to calculate matchings in graphs and bipartite graphs.
deba@2060
   179
deba@2060
   180
\image html bipartite_matching.png
deba@2060
   181
\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
deba@2060
   182
deba@2042
   183
*/
deba@2042
   184
deba@2042
   185
/**
deba@2084
   186
@defgroup spantree Minimum Cost Spanning Tree Algorithms
deba@2084
   187
@ingroup algs
alpar@2117
   188
\brief This group contains the algorithms for finding a minimum cost spanning
deba@2084
   189
tree in a graph
deba@2084
   190
alpar@2117
   191
This group contains the algorithms for finding a minimum cost spanning
deba@2084
   192
tree in a graph
deba@2084
   193
*/
deba@2084
   194
deba@2084
   195
deba@2084
   196
/**
deba@2084
   197
@defgroup auxalg Auxiliary Algorithms
deba@2084
   198
@ingroup algs
deba@2084
   199
\brief Some algorithms implemented in LEMON.
deba@2084
   200
deba@2084
   201
This group describes the algorithms in LEMON in order to make 
deba@2084
   202
it easier to implement complex algorithms.
deba@2084
   203
deba@2084
   204
*/
deba@2084
   205
deba@2084
   206
/**
deba@2084
   207
@defgroup gen_opt_group General Optimization Tools
deba@2084
   208
\brief This group describes some general optimization frameworks
deba@2084
   209
implemented in LEMON.
deba@2084
   210
deba@2084
   211
This group describes some general optimization frameworks
deba@2084
   212
implemented in LEMON.
deba@2084
   213
alpar@1151
   214
*/
alpar@1151
   215
alpar@1151
   216
/**
alpar@678
   217
@defgroup misc Miscellaneous Tools
alpar@678
   218
Here you can find several useful tools for development,
alpar@678
   219
debugging and testing.
alpar@678
   220
*/
alpar@678
   221
alpar@678
   222
/**
alpar@1847
   223
@defgroup timecount Time measuring and Counting
alpar@1847
   224
@ingroup misc
alpar@1847
   225
Here you can find simple tools for measuring the performance
alpar@1847
   226
of algorithms.
alpar@1847
   227
*/
alpar@1847
   228
alpar@1847
   229
/**
deba@2016
   230
@defgroup io_group Input-Output
deba@2084
   231
\brief Several Graph Input-Output methods
deba@2084
   232
deba@2084
   233
Here you can find tools for importing and exporting graphs 
deba@2084
   234
and graph related data. Now it supports the LEMON format, the
alpar@2117
   235
\c DIMACS format and the encapsulated postscript format.
deba@2084
   236
*/
deba@2084
   237
deba@2084
   238
/**
deba@2084
   239
@defgroup lemon_io Lemon Input-Output
deba@2084
   240
@ingroup io_group
deba@2084
   241
\brief Reading and writing LEMON format
deba@2084
   242
deba@2084
   243
Methods for reading and writing LEMON format. More about this
deba@2084
   244
format you can find on the \ref graph-io-page "Graph Input-Output"
deba@2084
   245
tutorial pages.
deba@2084
   246
alpar@1287
   247
*/
alpar@1287
   248
alpar@1287
   249
/**
deba@2016
   250
@defgroup section_io Section readers and writers
deba@2084
   251
@ingroup lemon_io
deba@2016
   252
\brief Section readers and writers for lemon Input-Output.
deba@2016
   253
deba@2016
   254
Here you can find which section readers and writers can attach to
deba@2016
   255
the LemonReader and LemonWriter.
deba@2016
   256
*/
deba@2016
   257
deba@2016
   258
/**
deba@2016
   259
@defgroup item_io Item Readers and Writers
deba@2084
   260
@ingroup lemon_io
deba@2016
   261
\brief Item readers and writers for lemon Input-Output.
deba@2016
   262
deba@2016
   263
The Input-Output classes can handle more data type by example
deba@2016
   264
as map or attribute value. Each of these should be written and
deba@2016
   265
read some way. The module make possible to do this.  
deba@2016
   266
*/
deba@2016
   267
deba@2016
   268
/**
deba@2084
   269
@defgroup eps_io Postscript exporting
deba@2084
   270
@ingroup io_group
alpar@2117
   271
\brief General \c EPS drawer and graph exporter
deba@2084
   272
alpar@2117
   273
This group contains general \c EPS drawing methods and special
deba@2084
   274
graph exporting tools. 
deba@2084
   275
*/
deba@2084
   276
deba@2084
   277
/**
deba@2084
   278
@defgroup exceptions Exceptions
deba@2084
   279
This group contains the exceptions thrown by LEMON library
deba@2084
   280
*/
deba@2084
   281
deba@2084
   282
/**
klao@1030
   283
@defgroup concept Concepts
klao@959
   284
\brief Skeleton classes and concept checking classes
alpar@794
   285
klao@959
   286
This group describes the data/algorithm skeletons and concept checking
klao@1030
   287
classes implemented in LEMON.
klao@1030
   288
alpar@2117
   289
The purpose of the classes in this group is fourfold.
alpar@2117
   290
 
alpar@2117
   291
- These classes contain the documentations of the concepts. In order
alpar@2117
   292
  to avoid document multiplications, an implementation of a concept
alpar@2117
   293
  simply refers to the corresponding concept class.
klao@1030
   294
alpar@2117
   295
- These classes declare every functions, <tt>typedef<tt>s etc. an
alpar@2117
   296
  implementation of the concepts should provide, however completely
alpar@2117
   297
  without implementations and real data structures behind the
alpar@2117
   298
  interface. On the other hand they should provide nothing else. All
alpar@2117
   299
  the algorithms working on a data structure meeting a certain concept
alpar@2117
   300
  should compile with these classes. (Though it will not run properly,
alpar@2117
   301
  of course.) In this way it is easily to check if an algorithm
alpar@2117
   302
  doesn't use any extra feature of a certain implementation.
alpar@2117
   303
alpar@2117
   304
- The concept descriptor classes also provide a <em>checker class<em>
alpar@2117
   305
  that makes it possible check whether a certain implementation of a
alpar@2117
   306
  concept indeed provides all the required features.
alpar@2117
   307
alpar@2117
   308
- Finally, They can serve as a skeleton of a new implementation of a concept.
klao@1030
   309
alpar@794
   310
*/
alpar@794
   311
deba@2084
   312
klao@1030
   313
/**
klao@1030
   314
@defgroup graph_concepts Graph Structure Concepts
klao@1030
   315
@ingroup concept
klao@1030
   316
\brief Skeleton and concept checking classes for graph structures
klao@1030
   317
klao@1030
   318
This group contains the skeletons and concept checking classes of LEMON's
klao@1030
   319
graph structures and helper classes used to implement these.
klao@1030
   320
*/
alpar@794
   321
alpar@1587
   322
/* --- Unused group
alpar@678
   323
@defgroup experimental Experimental Structures and Algorithms
alpar@678
   324
This group contains some Experimental structures and algorithms.
alpar@678
   325
The stuff here is subject to change.
alpar@678
   326
*/
alpar@1151
   327
alpar@1558
   328
/**
athos@1582
   329
\anchor demoprograms
athos@1582
   330
alpar@1558
   331
@defgroup demos Demo programs
alpar@1558
   332
alpar@1559
   333
Some demo programs are listed here. Their full source codes can be found in
alpar@1558
   334
the \c demo subdirectory of the source tree.
alpar@1558
   335
ladanyi@1639
   336
The standard compilation procedure (<tt>./configure;make</tt>) will compile
ladanyi@1639
   337
them, as well. 
alpar@1558
   338
alpar@1558
   339
*/
alpar@1558
   340