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