doc/groups.dox
author Balazs Dezso <deba@inf.elte.hu>
Fri, 25 Jan 2008 13:39:52 +0100
changeset 61 d718974f1290
parent 41 b11737922197
child 71 9df0fe5e5109
permissions -rw-r--r--
Digraph and Graph concept should be conform to the IDable... concepts
     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 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 edges 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 edges 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 "ReadMap"s. They can
   100 make arithmetic operations between one or two maps (negation, scaling,
   101 addition, multiplication etc.) or e.g. convert a map to another one
   102 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 graphToEps() 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   Graph::NodeMap<int> degree_map(graph);
   120   
   121   graphToEps(graph, "graph.eps")
   122     .coords(coords).scaleToA4().undirected()
   123     .nodeColors(composeMap(functorMap(nodeColor), degree_map)) 
   124     .run();
   125 \endcode 
   126 The \c functorMap() 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 previous created map. The composed map is proper function to
   129 get 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   Graph graph;
   136   
   137   typedef Graph::EdgeMap<double> DoubleEdgeMap;
   138   DoubleEdgeMap length(graph);
   139   DoubleEdgeMap speed(graph);
   140   
   141   typedef DivMap<DoubleEdgeMap, DoubleEdgeMap> TimeMap;
   142   
   143   TimeMap time(length, speed);
   144   
   145   Dijkstra<Graph, TimeMap> dijkstra(graph, time);
   146   dijkstra.run(source, target);
   147 \endcode
   148 
   149 We have a length map and a maximum speed map on a graph. The minimum
   150 time to pass the edge can be calculated as the division of the two
   151 maps which can be done implicitly with the \c DivMap template
   152 class. We use the implicit minimum time map as the length map of the
   153 \c Dijkstra algorithm.
   154 */
   155 
   156 /**
   157 @defgroup matrices Matrices 
   158 @ingroup datas
   159 \brief Two dimensional data storages implemented in LEMON.
   160 
   161 This group describes two dimensional data storages implemented in LEMON.
   162 */
   163 
   164 /**
   165 @defgroup paths Path Structures
   166 @ingroup datas
   167 \brief Path structures implemented in LEMON.
   168 
   169 This group describes the path structures implemented in LEMON.
   170 
   171 LEMON provides flexible data structures to work with paths.
   172 All of them have similar interfaces and they can be copied easily with
   173 assignment operators and copy constructors. This makes it easy and
   174 efficient to have e.g. the Dijkstra algorithm to store its result in
   175 any kind of path structure.
   176 
   177 \sa lemon::concepts::Path
   178 
   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 /**
   192 @defgroup algs Algorithms
   193 \brief This group describes the several algorithms
   194 implemented in LEMON.
   195 
   196 This group describes the several algorithms
   197 implemented in LEMON.
   198 */
   199 
   200 /**
   201 @defgroup search Graph Search
   202 @ingroup algs
   203 \brief Common graph search algorithms.
   204 
   205 This group describes the common graph search algorithms like 
   206 Breadth-first search (Bfs) and Depth-first search (Dfs).
   207 */
   208 
   209 /**
   210 @defgroup shortest_path Shortest Path algorithms
   211 @ingroup algs
   212 \brief Algorithms for finding shortest paths.
   213 
   214 This group describes the algorithms for finding shortest paths in graphs.
   215 */
   216 
   217 /** 
   218 @defgroup max_flow Maximum Flow algorithms 
   219 @ingroup algs 
   220 \brief Algorithms for finding maximum flows.
   221 
   222 This group describes the algorithms for finding maximum flows and
   223 feasible circulations.
   224 
   225 The maximum flow problem is to find a flow between a single source and
   226 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
   227 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
   228 function and given \f$s, t \in V\f$ source and target node. The
   229 maximum flow is the \f$f_a\f$ solution of the next optimization problem:
   230 
   231 \f[ 0 \le f_a \le c_a \f]
   232 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \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 /**
   249 @defgroup min_cost_flow Minimum Cost Flow algorithms
   250 @ingroup algs
   251 
   252 \brief Algorithms for finding minimum cost flows and circulations.
   253 
   254 This group describes the algorithms for finding minimum cost flows and
   255 circulations.  
   256 */
   257 
   258 /**
   259 @defgroup min_cut Minimum Cut algorithms 
   260 @ingroup algs 
   261 
   262 \brief Algorithms for finding minimum cut in graphs.
   263 
   264 This group describes the algorithms for finding minimum cut in graphs.
   265 
   266 The minimum cut problem is to find a non-empty and non-complete
   267 \f$X\f$ subset of the vertices with minimum overall capacity on
   268 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
   269 \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
   270 cut is the \f$X\f$ solution of the next optimization problem:
   271 
   272 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}\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, 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 edges 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 /**
   354 @defgroup spantree Minimum Spanning Tree algorithms
   355 @ingroup algs
   356 \brief Algorithms for finding a minimum cost spanning tree in a graph.
   357 
   358 This group describes the algorithms for finding a minimum cost spanning
   359 tree in a graph
   360 */
   361 
   362 
   363 /**
   364 @defgroup auxalg Auxiliary algorithms
   365 @ingroup algs
   366 \brief Auxiliary algorithms implemented in LEMON.
   367 
   368 This group describes some algorithms implemented in LEMON
   369 in order to make it easier to implement complex algorithms.
   370 */
   371 
   372 /**
   373 @defgroup approx Approximation algorithms
   374 \brief Approximation algorithms.
   375 
   376 This group describes the approximation and heuristic algorithms
   377 implemented in LEMON.
   378 */
   379 
   380 /**
   381 @defgroup gen_opt_group General Optimization Tools
   382 \brief This group describes some general optimization frameworks
   383 implemented in LEMON.
   384 
   385 This group describes some general optimization frameworks
   386 implemented in LEMON.
   387 
   388 */
   389 
   390 /**
   391 @defgroup lp_group Lp and Mip solvers
   392 @ingroup gen_opt_group
   393 \brief Lp and Mip solver interfaces for LEMON.
   394 
   395 This group describes Lp and Mip solver interfaces for LEMON. The
   396 various LP solvers could be used in the same manner with this
   397 interface.
   398 
   399 */
   400 
   401 /** 
   402 @defgroup lp_utils Tools for Lp and Mip solvers 
   403 @ingroup lp_group
   404 \brief Helper tools to the Lp and Mip solvers.
   405 
   406 This group adds some helper tools to general optimization framework
   407 implemented in LEMON.
   408 */
   409 
   410 /**
   411 @defgroup metah Metaheuristics
   412 @ingroup gen_opt_group
   413 \brief Metaheuristics for LEMON library.
   414 
   415 This group describes some metaheuristic optimization tools.
   416 */
   417 
   418 /**
   419 @defgroup utils Tools and Utilities 
   420 \brief Tools and utilities for programming in LEMON
   421 
   422 Tools and utilities for programming in LEMON.
   423 */
   424 
   425 /**
   426 @defgroup gutils Basic Graph Utilities
   427 @ingroup utils
   428 \brief Simple basic graph utilities.
   429 
   430 This group describes some simple basic graph utilities.
   431 */
   432 
   433 /**
   434 @defgroup misc Miscellaneous Tools
   435 @ingroup utils
   436 \brief Tools for development, debugging and testing.
   437 
   438 This group describes several useful tools for development,
   439 debugging and testing.
   440 */
   441 
   442 /**
   443 @defgroup timecount Time measuring and Counting
   444 @ingroup misc
   445 \brief Simple tools for measuring the performance of algorithms.
   446 
   447 This group describes simple tools for measuring the performance
   448 of algorithms.
   449 */
   450 
   451 /**
   452 @defgroup graphbits Tools for Graph Implementation
   453 @ingroup utils
   454 \brief Tools to make it easier to create graphs.
   455 
   456 This group describes the tools that makes it easier to create graphs and
   457 the maps that dynamically update with the graph changes.
   458 */
   459 
   460 /**
   461 @defgroup exceptions Exceptions
   462 @ingroup utils
   463 \brief Exceptions defined in LEMON.
   464 
   465 This group describes the exceptions defined in LEMON.
   466 */
   467 
   468 /**
   469 @defgroup io_group Input-Output
   470 \brief Graph Input-Output methods
   471 
   472 This group describes the tools for importing and exporting graphs 
   473 and graph related data. Now it supports the LEMON format, the
   474 \c DIMACS format and the encapsulated postscript (EPS) format.
   475 */
   476 
   477 /**
   478 @defgroup lemon_io Lemon Input-Output
   479 @ingroup io_group
   480 \brief Reading and writing LEMON format
   481 
   482 This group describes methods for reading and writing LEMON format. 
   483 You can find more about this format on the \ref graph-io-page "Graph Input-Output"
   484 tutorial pages.
   485 */
   486 
   487 /**
   488 @defgroup section_io Section readers and writers
   489 @ingroup lemon_io
   490 \brief Section readers and writers for lemon Input-Output.
   491 
   492 This group describes section readers and writers that can be attached to
   493 \ref LemonReader and \ref LemonWriter.
   494 */
   495 
   496 /**
   497 @defgroup item_io Item Readers and Writers
   498 @ingroup lemon_io
   499 \brief Item readers and writers for lemon Input-Output.
   500 
   501 The Input-Output classes can handle more data type by example
   502 as map or attribute value. Each of these should be written and
   503 read some way. The module make possible to do this.  
   504 */
   505 
   506 /**
   507 @defgroup eps_io Postscript exporting
   508 @ingroup io_group
   509 \brief General \c EPS drawer and graph exporter
   510 
   511 This group describes general \c EPS drawing methods and special
   512 graph exporting tools. 
   513 */
   514 
   515 
   516 /**
   517 @defgroup concept Concepts
   518 \brief Skeleton classes and concept checking classes
   519 
   520 This group describes the data/algorithm skeletons and concept checking
   521 classes implemented in LEMON.
   522 
   523 The purpose of the classes in this group is fourfold.
   524  
   525 - These classes contain the documentations of the concepts. In order
   526   to avoid document multiplications, an implementation of a concept
   527   simply refers to the corresponding concept class.
   528 
   529 - These classes declare every functions, <tt>typedef</tt>s etc. an
   530   implementation of the concepts should provide, however completely
   531   without implementations and real data structures behind the
   532   interface. On the other hand they should provide nothing else. All
   533   the algorithms working on a data structure meeting a certain concept
   534   should compile with these classes. (Though it will not run properly,
   535   of course.) In this way it is easily to check if an algorithm
   536   doesn't use any extra feature of a certain implementation.
   537 
   538 - The concept descriptor classes also provide a <em>checker class</em>
   539   that makes it possible to check whether a certain implementation of a
   540   concept indeed provides all the required features.
   541 
   542 - Finally, They can serve as a skeleton of a new implementation of a concept.
   543 
   544 */
   545 
   546 
   547 /**
   548 @defgroup graph_concepts Graph Structure Concepts
   549 @ingroup concept
   550 \brief Skeleton and concept checking classes for graph structures
   551 
   552 This group describes the skeletons and concept checking classes of LEMON's
   553 graph structures and helper classes used to implement these.
   554 */
   555 
   556 /* --- Unused group
   557 @defgroup experimental Experimental Structures and Algorithms
   558 This group describes some Experimental structures and algorithms.
   559 The stuff here is subject to change.
   560 */
   561 
   562 /**
   563 \anchor demoprograms
   564 
   565 @defgroup demos Demo programs
   566 
   567 Some demo programs are listed here. Their full source codes can be found in
   568 the \c demo subdirectory of the source tree.
   569 
   570 It order to compile them, use <tt>--enable-demo</tt> configure option when
   571 build the library.
   572 */
   573 
   574 /**
   575 @defgroup tools Standalone utility applications
   576 
   577 Some utility applications are listed here. 
   578 
   579 The standard compilation procedure (<tt>./configure;make</tt>) will compile
   580 them, as well. 
   581 */
   582