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