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