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