doc/groups.dox
author Peter Kovacs <kpeter@inf.elte.hu>
Sun, 15 Jun 2008 22:03:33 +0200
changeset 170 91fb4372688f
parent 83 3654324ec035
child 192 7bf5f97d574f
permissions -rw-r--r--
Port dijkstra_test.cc from SVN -r3499
     1 /* -*- C++ -*-
     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} \qquad \forall u \in V \setminus \{s,t\}\f]
   231 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
   232 
   233 LEMON contains several algorithms for solving maximum flow problems:
   234 - \ref lemon::EdmondsKarp "Edmonds-Karp" 
   235 - \ref lemon::Preflow "Goldberg's Preflow algorithm"
   236 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
   237 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
   238 
   239 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
   240 fastest method to compute the maximum flow. All impelementations
   241 provides functions to query the minimum cut, which is the dual linear
   242 programming problem of the maximum flow.
   243 
   244 */
   245 
   246 /**
   247 @defgroup min_cost_flow Minimum Cost Flow algorithms
   248 @ingroup algs
   249 
   250 \brief Algorithms for finding minimum cost flows and circulations.
   251 
   252 This group describes the algorithms for finding minimum cost flows and
   253 circulations.  
   254 */
   255 
   256 /**
   257 @defgroup min_cut Minimum Cut algorithms 
   258 @ingroup algs 
   259 
   260 \brief Algorithms for finding minimum cut in graphs.
   261 
   262 This group describes the algorithms for finding minimum cut in graphs.
   263 
   264 The minimum cut problem is to find a non-empty and non-complete
   265 \f$X\f$ subset of the vertices with minimum overall capacity on
   266 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
   267 \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
   268 cut is the \f$X\f$ solution of the next optimization problem:
   269 
   270 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
   271 
   272 LEMON contains several algorithms related to minimum cut problems:
   273 
   274 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
   275   in directed graphs  
   276 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
   277   calculate minimum cut in undirected graphs
   278 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
   279   pairs minimum cut in undirected graphs
   280 
   281 If you want to find minimum cut just between two distinict nodes,
   282 please see the \ref max_flow "Maximum Flow page".
   283 
   284 */
   285 
   286 /**
   287 @defgroup graph_prop Connectivity and other graph properties
   288 @ingroup algs
   289 \brief Algorithms for discovering the graph properties
   290 
   291 This group describes the algorithms for discovering the graph properties
   292 like connectivity, bipartiteness, euler property, simplicity etc.
   293 
   294 \image html edge_biconnected_components.png
   295 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
   296 */
   297 
   298 /**
   299 @defgroup planar Planarity embedding and drawing
   300 @ingroup algs
   301 \brief Algorithms for planarity checking, embedding and drawing
   302 
   303 This group describes the algorithms for planarity checking, embedding and drawing.
   304 
   305 \image html planar.png
   306 \image latex planar.eps "Plane graph" width=\textwidth
   307 */
   308 
   309 /**
   310 @defgroup matching Matching algorithms 
   311 @ingroup algs
   312 \brief Algorithms for finding matchings in graphs and bipartite graphs.
   313 
   314 This group contains algorithm objects and functions to calculate
   315 matchings in graphs and bipartite graphs. The general matching problem is
   316 finding a subset of the arcs which does not shares common endpoints.
   317  
   318 There are several different algorithms for calculate matchings in
   319 graphs.  The matching problems in bipartite graphs are generally
   320 easier than in general graphs. The goal of the matching optimization
   321 can be the finding maximum cardinality, maximum weight or minimum cost
   322 matching. The search can be constrained to find perfect or
   323 maximum cardinality matching.
   324 
   325 Lemon contains the next algorithms:
   326 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp 
   327   augmenting path algorithm for calculate maximum cardinality matching in 
   328   bipartite graphs
   329 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel 
   330   algorithm for calculate maximum cardinality matching in bipartite graphs 
   331 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching" 
   332   Successive shortest path algorithm for calculate maximum weighted matching 
   333   and maximum weighted bipartite matching in bipartite graph
   334 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching" 
   335   Successive shortest path algorithm for calculate minimum cost maximum 
   336   matching in bipartite graph
   337 - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
   338   for calculate maximum cardinality matching in general graph
   339 - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
   340   shrinking algorithm for calculate maximum weighted matching in general
   341   graph
   342 - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
   343   Edmond's blossom shrinking algorithm for calculate maximum weighted
   344   perfect matching in general graph
   345 
   346 \image html bipartite_matching.png
   347 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
   348 
   349 */
   350 
   351 /**
   352 @defgroup spantree Minimum Spanning Tree algorithms
   353 @ingroup algs
   354 \brief Algorithms for finding a minimum cost spanning tree in a graph.
   355 
   356 This group describes the algorithms for finding a minimum cost spanning
   357 tree in a graph
   358 */
   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 \brief Approximation algorithms.
   373 
   374 This group describes the approximation and heuristic algorithms
   375 implemented in LEMON.
   376 */
   377 
   378 /**
   379 @defgroup gen_opt_group General Optimization Tools
   380 \brief This group describes some general optimization frameworks
   381 implemented in LEMON.
   382 
   383 This group describes some general optimization frameworks
   384 implemented in LEMON.
   385 
   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 /** 
   400 @defgroup lp_utils Tools for Lp and Mip solvers 
   401 @ingroup lp_group
   402 \brief Helper tools to the Lp and Mip solvers.
   403 
   404 This group adds some helper tools to general optimization framework
   405 implemented in LEMON.
   406 */
   407 
   408 /**
   409 @defgroup metah Metaheuristics
   410 @ingroup gen_opt_group
   411 \brief Metaheuristics for LEMON library.
   412 
   413 This group describes some metaheuristic optimization tools.
   414 */
   415 
   416 /**
   417 @defgroup utils Tools and Utilities 
   418 \brief Tools and utilities for programming in LEMON
   419 
   420 Tools and utilities for programming in LEMON.
   421 */
   422 
   423 /**
   424 @defgroup gutils Basic Graph Utilities
   425 @ingroup utils
   426 \brief Simple basic graph utilities.
   427 
   428 This group describes some simple basic graph utilities.
   429 */
   430 
   431 /**
   432 @defgroup misc Miscellaneous Tools
   433 @ingroup utils
   434 \brief Tools for development, debugging and testing.
   435 
   436 This group describes several useful tools for development,
   437 debugging and testing.
   438 */
   439 
   440 /**
   441 @defgroup timecount Time measuring and Counting
   442 @ingroup misc
   443 \brief Simple tools for measuring the performance of algorithms.
   444 
   445 This group describes simple tools for measuring the performance
   446 of algorithms.
   447 */
   448 
   449 /**
   450 @defgroup graphbits Tools for Graph Implementation
   451 @ingroup utils
   452 \brief Tools to make it easier to create graphs.
   453 
   454 This group describes the tools that makes it easier to create graphs and
   455 the maps that dynamically update with the graph changes.
   456 */
   457 
   458 /**
   459 @defgroup exceptions Exceptions
   460 @ingroup utils
   461 \brief Exceptions defined in LEMON.
   462 
   463 This group describes the exceptions defined in LEMON.
   464 */
   465 
   466 /**
   467 @defgroup io_group Input-Output
   468 \brief Graph Input-Output methods
   469 
   470 This group describes the tools for importing and exporting graphs 
   471 and graph related data. Now it supports the LEMON format, the
   472 \c DIMACS format and the encapsulated postscript (EPS) format.
   473 */
   474 
   475 /**
   476 @defgroup lemon_io Lemon Input-Output
   477 @ingroup io_group
   478 \brief Reading and writing LEMON format
   479 
   480 This group describes methods for reading and writing LEMON format. 
   481 You can find more about this format on the \ref graph-io-page "Graph Input-Output"
   482 tutorial pages.
   483 */
   484 
   485 /**
   486 @defgroup eps_io Postscript exporting
   487 @ingroup io_group
   488 \brief General \c EPS drawer and graph exporter
   489 
   490 This group describes general \c EPS drawing methods and special
   491 graph exporting tools. 
   492 */
   493 
   494 
   495 /**
   496 @defgroup concept Concepts
   497 \brief Skeleton classes and concept checking classes
   498 
   499 This group describes the data/algorithm skeletons and concept checking
   500 classes implemented in LEMON.
   501 
   502 The purpose of the classes in this group is fourfold.
   503  
   504 - These classes contain the documentations of the concepts. In order
   505   to avoid document multiplications, an implementation of a concept
   506   simply refers to the corresponding concept class.
   507 
   508 - These classes declare every functions, <tt>typedef</tt>s etc. an
   509   implementation of the concepts should provide, however completely
   510   without implementations and real data structures behind the
   511   interface. On the other hand they should provide nothing else. All
   512   the algorithms working on a data structure meeting a certain concept
   513   should compile with these classes. (Though it will not run properly,
   514   of course.) In this way it is easily to check if an algorithm
   515   doesn't use any extra feature of a certain implementation.
   516 
   517 - The concept descriptor classes also provide a <em>checker class</em>
   518   that makes it possible to check whether a certain implementation of a
   519   concept indeed provides all the required features.
   520 
   521 - Finally, They can serve as a skeleton of a new implementation of a concept.
   522 
   523 */
   524 
   525 
   526 /**
   527 @defgroup graph_concepts Graph Structure Concepts
   528 @ingroup concept
   529 \brief Skeleton and concept checking classes for graph structures
   530 
   531 This group describes the skeletons and concept checking classes of LEMON's
   532 graph structures and helper classes used to implement these.
   533 */
   534 
   535 /* --- Unused group
   536 @defgroup experimental Experimental Structures and Algorithms
   537 This group describes some Experimental structures and algorithms.
   538 The stuff here is subject to change.
   539 */
   540 
   541 /**
   542 \anchor demoprograms
   543 
   544 @defgroup demos Demo programs
   545 
   546 Some demo programs are listed here. Their full source codes can be found in
   547 the \c demo subdirectory of the source tree.
   548 
   549 It order to compile them, use <tt>--enable-demo</tt> configure option when
   550 build the library.
   551 */
   552 
   553 /**
   554 @defgroup tools Standalone utility applications
   555 
   556 Some utility applications are listed here. 
   557 
   558 The standard compilation procedure (<tt>./configure;make</tt>) will compile
   559 them, as well. 
   560 */
   561