doc/groups.dox
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 05 Aug 2011 00:17:29 +0200
branch1.0
changeset 1078 c59bdcc8e33e
parent 330 d3a7603026a2
permissions -rw-r--r--
Unify sources
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@40
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@40
     4
 *
alpar@1078
     5
 * Copyright (C) 2003-2011
alpar@40
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@40
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@40
     8
 *
alpar@40
     9
 * Permission to use, modify and distribute this software is granted
alpar@40
    10
 * provided that this copyright notice appears in all copies. For
alpar@40
    11
 * precise terms see the accompanying LICENSE file.
alpar@40
    12
 *
alpar@40
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@40
    14
 * express or implied, and with no claim as to its suitability for any
alpar@40
    15
 * purpose.
alpar@40
    16
 *
alpar@40
    17
 */
alpar@40
    18
alpar@40
    19
/**
alpar@40
    20
@defgroup datas Data Structures
kpeter@50
    21
This group describes the several data structures implemented in LEMON.
alpar@40
    22
*/
alpar@40
    23
alpar@40
    24
/**
alpar@40
    25
@defgroup graphs Graph Structures
alpar@40
    26
@ingroup datas
alpar@40
    27
\brief Graph structures implemented in LEMON.
alpar@40
    28
alpar@209
    29
The implementation of combinatorial algorithms heavily relies on
alpar@209
    30
efficient graph implementations. LEMON offers data structures which are
alpar@209
    31
planned to be easily used in an experimental phase of implementation studies,
alpar@209
    32
and thereafter the program code can be made efficient by small modifications.
alpar@40
    33
alpar@40
    34
The most efficient implementation of diverse applications require the
alpar@40
    35
usage of different physical graph implementations. These differences
alpar@40
    36
appear in the size of graph we require to handle, memory or time usage
alpar@40
    37
limitations or in the set of operations through which the graph can be
alpar@40
    38
accessed.  LEMON provides several physical graph structures to meet
alpar@40
    39
the diverging requirements of the possible users.  In order to save on
alpar@40
    40
running time or on memory usage, some structures may fail to provide
kpeter@83
    41
some graph features like arc/edge or node deletion.
alpar@40
    42
alpar@40
    43
You are free to use the graph structure that fit your requirements
alpar@40
    44
the best, most graph algorithms and auxiliary data structures can be used
kpeter@314
    45
with any graph structure.
kpeter@314
    46
kpeter@314
    47
<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
alpar@40
    48
*/
alpar@40
    49
alpar@40
    50
/**
alpar@209
    51
@defgroup maps Maps
alpar@40
    52
@ingroup datas
kpeter@50
    53
\brief Map structures implemented in LEMON.
alpar@40
    54
kpeter@50
    55
This group describes the map structures implemented in LEMON.
kpeter@50
    56
kpeter@314
    57
LEMON provides several special purpose maps and map adaptors that e.g. combine
alpar@40
    58
new maps from existing ones.
kpeter@314
    59
kpeter@314
    60
<b>See also:</b> \ref map_concepts "Map Concepts".
alpar@40
    61
*/
alpar@40
    62
alpar@40
    63
/**
alpar@209
    64
@defgroup graph_maps Graph Maps
alpar@40
    65
@ingroup maps
kpeter@83
    66
\brief Special graph-related maps.
alpar@40
    67
kpeter@50
    68
This group describes maps that are specifically designed to assign
kpeter@83
    69
values to the nodes and arcs of graphs.
alpar@40
    70
*/
alpar@40
    71
alpar@40
    72
/**
alpar@40
    73
\defgroup map_adaptors Map Adaptors
alpar@40
    74
\ingroup maps
alpar@40
    75
\brief Tools to create new maps from existing ones
alpar@40
    76
kpeter@50
    77
This group describes map adaptors that are used to create "implicit"
kpeter@50
    78
maps from other maps.
alpar@40
    79
kpeter@83
    80
Most of them are \ref lemon::concepts::ReadMap "read-only maps".
kpeter@83
    81
They can make arithmetic and logical operations between one or two maps
kpeter@83
    82
(negation, shifting, addition, multiplication, logical 'and', 'or',
kpeter@83
    83
'not' etc.) or e.g. convert a map to another one of different Value type.
alpar@40
    84
kpeter@50
    85
The typical usage of this classes is passing implicit maps to
alpar@40
    86
algorithms.  If a function type algorithm is called then the function
alpar@40
    87
type map adaptors can be used comfortable. For example let's see the
kpeter@314
    88
usage of map adaptors with the \c graphToEps() function.
alpar@40
    89
\code
alpar@40
    90
  Color nodeColor(int deg) {
alpar@40
    91
    if (deg >= 2) {
alpar@40
    92
      return Color(0.5, 0.0, 0.5);
alpar@40
    93
    } else if (deg == 1) {
alpar@40
    94
      return Color(1.0, 0.5, 1.0);
alpar@40
    95
    } else {
alpar@40
    96
      return Color(0.0, 0.0, 0.0);
alpar@40
    97
    }
alpar@40
    98
  }
alpar@209
    99
kpeter@83
   100
  Digraph::NodeMap<int> degree_map(graph);
alpar@209
   101
kpeter@314
   102
  graphToEps(graph, "graph.eps")
alpar@40
   103
    .coords(coords).scaleToA4().undirected()
kpeter@83
   104
    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
alpar@40
   105
    .run();
alpar@209
   106
\endcode
kpeter@83
   107
The \c functorToMap() function makes an \c int to \c Color map from the
kpeter@314
   108
\c nodeColor() function. The \c composeMap() compose the \c degree_map
kpeter@83
   109
and the previously created map. The composed map is a proper function to
kpeter@83
   110
get the color of each node.
alpar@40
   111
alpar@40
   112
The usage with class type algorithms is little bit harder. In this
alpar@40
   113
case the function type map adaptors can not be used, because the
kpeter@50
   114
function map adaptors give back temporary objects.
alpar@40
   115
\code
kpeter@83
   116
  Digraph graph;
kpeter@83
   117
kpeter@83
   118
  typedef Digraph::ArcMap<double> DoubleArcMap;
kpeter@83
   119
  DoubleArcMap length(graph);
kpeter@83
   120
  DoubleArcMap speed(graph);
kpeter@83
   121
kpeter@83
   122
  typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
alpar@40
   123
  TimeMap time(length, speed);
alpar@209
   124
kpeter@83
   125
  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
alpar@40
   126
  dijkstra.run(source, target);
alpar@40
   127
\endcode
kpeter@83
   128
We have a length map and a maximum speed map on the arcs of a digraph.
kpeter@83
   129
The minimum time to pass the arc can be calculated as the division of
kpeter@83
   130
the two maps which can be done implicitly with the \c DivMap template
alpar@40
   131
class. We use the implicit minimum time map as the length map of the
alpar@40
   132
\c Dijkstra algorithm.
alpar@40
   133
*/
alpar@40
   134
alpar@40
   135
/**
alpar@40
   136
@defgroup paths Path Structures
alpar@40
   137
@ingroup datas
kpeter@318
   138
\brief %Path structures implemented in LEMON.
alpar@40
   139
kpeter@50
   140
This group describes the path structures implemented in LEMON.
alpar@40
   141
kpeter@50
   142
LEMON provides flexible data structures to work with paths.
kpeter@50
   143
All of them have similar interfaces and they can be copied easily with
kpeter@50
   144
assignment operators and copy constructors. This makes it easy and
alpar@40
   145
efficient to have e.g. the Dijkstra algorithm to store its result in
alpar@40
   146
any kind of path structure.
alpar@40
   147
alpar@40
   148
\sa lemon::concepts::Path
alpar@40
   149
*/
alpar@40
   150
alpar@40
   151
/**
alpar@40
   152
@defgroup auxdat Auxiliary Data Structures
alpar@40
   153
@ingroup datas
kpeter@50
   154
\brief Auxiliary data structures implemented in LEMON.
alpar@40
   155
kpeter@50
   156
This group describes some data structures implemented in LEMON in
alpar@40
   157
order to make it easier to implement combinatorial algorithms.
alpar@40
   158
*/
alpar@40
   159
alpar@40
   160
/**
alpar@40
   161
@defgroup algs Algorithms
alpar@40
   162
\brief This group describes the several algorithms
alpar@40
   163
implemented in LEMON.
alpar@40
   164
alpar@40
   165
This group describes the several algorithms
alpar@40
   166
implemented in LEMON.
alpar@40
   167
*/
alpar@40
   168
alpar@40
   169
/**
alpar@40
   170
@defgroup search Graph Search
alpar@40
   171
@ingroup algs
kpeter@50
   172
\brief Common graph search algorithms.
alpar@40
   173
alpar@209
   174
This group describes the common graph search algorithms like
kpeter@314
   175
Breadth-First Search (BFS) and Depth-First Search (DFS).
alpar@40
   176
*/
alpar@40
   177
alpar@40
   178
/**
kpeter@314
   179
@defgroup shortest_path Shortest Path Algorithms
alpar@40
   180
@ingroup algs
kpeter@50
   181
\brief Algorithms for finding shortest paths.
alpar@40
   182
kpeter@50
   183
This group describes the algorithms for finding shortest paths in graphs.
alpar@40
   184
*/
alpar@40
   185
alpar@209
   186
/**
kpeter@314
   187
@defgroup spantree Minimum Spanning Tree Algorithms
alpar@40
   188
@ingroup algs
kpeter@50
   189
\brief Algorithms for finding a minimum cost spanning tree in a graph.
alpar@40
   190
kpeter@50
   191
This group describes the algorithms for finding a minimum cost spanning
alpar@40
   192
tree in a graph
alpar@40
   193
*/
alpar@40
   194
alpar@40
   195
/**
alpar@209
   196
@defgroup utils Tools and Utilities
kpeter@50
   197
\brief Tools and utilities for programming in LEMON
alpar@40
   198
kpeter@50
   199
Tools and utilities for programming in LEMON.
alpar@40
   200
*/
alpar@40
   201
alpar@40
   202
/**
alpar@40
   203
@defgroup gutils Basic Graph Utilities
alpar@40
   204
@ingroup utils
kpeter@50
   205
\brief Simple basic graph utilities.
alpar@40
   206
alpar@40
   207
This group describes some simple basic graph utilities.
alpar@40
   208
*/
alpar@40
   209
alpar@40
   210
/**
alpar@40
   211
@defgroup misc Miscellaneous Tools
alpar@40
   212
@ingroup utils
kpeter@50
   213
\brief Tools for development, debugging and testing.
kpeter@50
   214
kpeter@50
   215
This group describes several useful tools for development,
alpar@40
   216
debugging and testing.
alpar@40
   217
*/
alpar@40
   218
alpar@40
   219
/**
kpeter@314
   220
@defgroup timecount Time Measuring and Counting
alpar@40
   221
@ingroup misc
kpeter@50
   222
\brief Simple tools for measuring the performance of algorithms.
kpeter@50
   223
kpeter@50
   224
This group describes simple tools for measuring the performance
alpar@40
   225
of algorithms.
alpar@40
   226
*/
alpar@40
   227
alpar@40
   228
/**
alpar@40
   229
@defgroup exceptions Exceptions
alpar@40
   230
@ingroup utils
kpeter@50
   231
\brief Exceptions defined in LEMON.
kpeter@50
   232
kpeter@50
   233
This group describes the exceptions defined in LEMON.
alpar@40
   234
*/
alpar@40
   235
alpar@40
   236
/**
alpar@40
   237
@defgroup io_group Input-Output
kpeter@50
   238
\brief Graph Input-Output methods
alpar@40
   239
alpar@209
   240
This group describes the tools for importing and exporting graphs
kpeter@325
   241
and graph related data. Now it supports the LEMON format
kpeter@325
   242
and the encapsulated postscript (EPS) format.
kpeter@314
   243
postscript (EPS) format.
alpar@40
   244
*/
alpar@40
   245
alpar@40
   246
/**
ladanyi@236
   247
@defgroup lemon_io LEMON Input-Output
alpar@40
   248
@ingroup io_group
kpeter@314
   249
\brief Reading and writing LEMON Graph Format.
alpar@40
   250
alpar@210
   251
This group describes methods for reading and writing
ladanyi@236
   252
\ref lgf-format "LEMON Graph Format".
alpar@40
   253
*/
alpar@40
   254
alpar@40
   255
/**
kpeter@314
   256
@defgroup eps_io Postscript Exporting
alpar@40
   257
@ingroup io_group
alpar@40
   258
\brief General \c EPS drawer and graph exporter
alpar@40
   259
kpeter@50
   260
This group describes general \c EPS drawing methods and special
alpar@209
   261
graph exporting tools.
alpar@40
   262
*/
alpar@40
   263
alpar@40
   264
/**
alpar@40
   265
@defgroup concept Concepts
alpar@40
   266
\brief Skeleton classes and concept checking classes
alpar@40
   267
alpar@40
   268
This group describes the data/algorithm skeletons and concept checking
alpar@40
   269
classes implemented in LEMON.
alpar@40
   270
alpar@40
   271
The purpose of the classes in this group is fourfold.
alpar@209
   272
kpeter@318
   273
- These classes contain the documentations of the %concepts. In order
alpar@40
   274
  to avoid document multiplications, an implementation of a concept
alpar@40
   275
  simply refers to the corresponding concept class.
alpar@40
   276
alpar@40
   277
- These classes declare every functions, <tt>typedef</tt>s etc. an
kpeter@318
   278
  implementation of the %concepts should provide, however completely
alpar@40
   279
  without implementations and real data structures behind the
alpar@40
   280
  interface. On the other hand they should provide nothing else. All
alpar@40
   281
  the algorithms working on a data structure meeting a certain concept
alpar@40
   282
  should compile with these classes. (Though it will not run properly,
alpar@40
   283
  of course.) In this way it is easily to check if an algorithm
alpar@40
   284
  doesn't use any extra feature of a certain implementation.
alpar@40
   285
alpar@40
   286
- The concept descriptor classes also provide a <em>checker class</em>
kpeter@50
   287
  that makes it possible to check whether a certain implementation of a
alpar@40
   288
  concept indeed provides all the required features.
alpar@40
   289
alpar@40
   290
- Finally, They can serve as a skeleton of a new implementation of a concept.
alpar@40
   291
*/
alpar@40
   292
alpar@40
   293
/**
alpar@40
   294
@defgroup graph_concepts Graph Structure Concepts
alpar@40
   295
@ingroup concept
alpar@40
   296
\brief Skeleton and concept checking classes for graph structures
alpar@40
   297
kpeter@50
   298
This group describes the skeletons and concept checking classes of LEMON's
alpar@40
   299
graph structures and helper classes used to implement these.
alpar@40
   300
*/
alpar@40
   301
kpeter@314
   302
/**
kpeter@314
   303
@defgroup map_concepts Map Concepts
kpeter@314
   304
@ingroup concept
kpeter@314
   305
\brief Skeleton and concept checking classes for maps
alpar@1078
   306
kpeter@314
   307
This group describes the skeletons and concept checking classes of maps.
alpar@40
   308
*/
alpar@40
   309
alpar@40
   310
/**
alpar@40
   311
\anchor demoprograms
alpar@40
   312
alpar@40
   313
@defgroup demos Demo programs
alpar@40
   314
alpar@40
   315
Some demo programs are listed here. Their full source codes can be found in
alpar@40
   316
the \c demo subdirectory of the source tree.
alpar@40
   317
alpar@41
   318
It order to compile them, use <tt>--enable-demo</tt> configure option when
alpar@41
   319
build the library.
alpar@40
   320
*/