doc/groups.dox
author deba
Tue, 11 Dec 2007 17:42:49 +0000
changeset 2540 8ab1d3d7dea7
parent 2514 57143c09dc20
child 2548 a3ba22ebccc6
permissions -rw-r--r--
Avoiding warnings
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2007
     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
   322 to calculate matchings in graphs and bipartite graphs.
   323 
   324 \image html bipartite_matching.png
   325 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
   326 
   327 */
   328 
   329 /**
   330 @defgroup spantree Minimum Spanning Tree algorithms
   331 @ingroup algs
   332 \brief This group contains the algorithms for finding a minimum cost spanning
   333 tree in a graph
   334 
   335 This group contains the algorithms for finding a minimum cost spanning
   336 tree in a graph
   337 */
   338 
   339 
   340 /**
   341 @defgroup auxalg Auxiliary algorithms
   342 @ingroup algs
   343 \brief Some algorithms implemented in LEMON.
   344 
   345 This group describes the algorithms in LEMON in order to make 
   346 it easier to implement complex algorithms.
   347 */
   348 
   349 /**
   350 @defgroup approx Approximation algorithms
   351 \brief Approximation algorithms
   352 
   353 Approximation and heuristic algorithms
   354 */
   355 
   356 /**
   357 @defgroup gen_opt_group General Optimization Tools
   358 \brief This group describes some general optimization frameworks
   359 implemented in LEMON.
   360 
   361 This group describes some general optimization frameworks
   362 implemented in LEMON.
   363 
   364 */
   365 
   366 /**
   367 @defgroup lp_group Lp and Mip solvers
   368 @ingroup gen_opt_group
   369 \brief Lp and Mip solver interfaces for LEMON.
   370 
   371 This group describes Lp and Mip solver interfaces for LEMON. The
   372 various LP solvers could be used in the same manner with this
   373 interface.
   374 
   375 */
   376 
   377 /** 
   378 @defgroup lp_utils Tools for Lp and Mip solvers 
   379 @ingroup lp_group
   380 \brief This group adds some helper tools to the Lp and Mip solvers
   381 implemented in LEMON.
   382 
   383 This group adds some helper tools to general optimization framework
   384 implemented in LEMON.
   385 */
   386 
   387 /**
   388 @defgroup metah Metaheuristics
   389 @ingroup gen_opt_group
   390 \brief Metaheuristics for LEMON library.
   391 
   392 This group contains some metaheuristic optimization tools.
   393 */
   394 
   395 /**
   396 @defgroup utils Tools and Utilities 
   397 \brief Tools and Utilities for Programming in LEMON
   398 
   399 Tools and Utilities for Programming in LEMON
   400 */
   401 
   402 /**
   403 @defgroup gutils Basic Graph Utilities
   404 @ingroup utils
   405 \brief This group describes some simple basic graph utilities.
   406 
   407 This group describes some simple basic graph utilities.
   408 */
   409 
   410 /**
   411 @defgroup misc Miscellaneous Tools
   412 @ingroup utils
   413 Here you can find several useful tools for development,
   414 debugging and testing.
   415 */
   416 
   417 
   418 /**
   419 @defgroup timecount Time measuring and Counting
   420 @ingroup misc
   421 Here you can find simple tools for measuring the performance
   422 of algorithms.
   423 */
   424 
   425 /**
   426 @defgroup graphbits Tools for Graph Implementation
   427 @ingroup utils
   428 \brief Tools to Make It Easier to Make Graphs.
   429 
   430 This group describes the tools that makes it easier to make graphs and
   431 the maps that dynamically update with the graph changes.
   432 */
   433 
   434 /**
   435 @defgroup exceptions Exceptions
   436 @ingroup utils
   437 This group contains the exceptions thrown by LEMON library
   438 */
   439 
   440 /**
   441 @defgroup io_group Input-Output
   442 \brief Several Graph Input-Output methods
   443 
   444 Here you can find tools for importing and exporting graphs 
   445 and graph related data. Now it supports the LEMON format, the
   446 \c DIMACS format and the encapsulated postscript format.
   447 */
   448 
   449 /**
   450 @defgroup lemon_io Lemon Input-Output
   451 @ingroup io_group
   452 \brief Reading and writing LEMON format
   453 
   454 Methods for reading and writing LEMON format. More about this
   455 format you can find on the \ref graph-io-page "Graph Input-Output"
   456 tutorial pages.
   457 */
   458 
   459 /**
   460 @defgroup section_io Section readers and writers
   461 @ingroup lemon_io
   462 \brief Section readers and writers for lemon Input-Output.
   463 
   464 Here you can find which section readers and writers can attach to
   465 the LemonReader and LemonWriter.
   466 */
   467 
   468 /**
   469 @defgroup item_io Item Readers and Writers
   470 @ingroup lemon_io
   471 \brief Item readers and writers for lemon Input-Output.
   472 
   473 The Input-Output classes can handle more data type by example
   474 as map or attribute value. Each of these should be written and
   475 read some way. The module make possible to do this.  
   476 */
   477 
   478 /**
   479 @defgroup eps_io Postscript exporting
   480 @ingroup io_group
   481 \brief General \c EPS drawer and graph exporter
   482 
   483 This group contains general \c EPS drawing methods and special
   484 graph exporting tools. 
   485 */
   486 
   487 
   488 /**
   489 @defgroup concept Concepts
   490 \brief Skeleton classes and concept checking classes
   491 
   492 This group describes the data/algorithm skeletons and concept checking
   493 classes implemented in LEMON.
   494 
   495 The purpose of the classes in this group is fourfold.
   496  
   497 - These classes contain the documentations of the concepts. In order
   498   to avoid document multiplications, an implementation of a concept
   499   simply refers to the corresponding concept class.
   500 
   501 - These classes declare every functions, <tt>typedef</tt>s etc. an
   502   implementation of the concepts should provide, however completely
   503   without implementations and real data structures behind the
   504   interface. On the other hand they should provide nothing else. All
   505   the algorithms working on a data structure meeting a certain concept
   506   should compile with these classes. (Though it will not run properly,
   507   of course.) In this way it is easily to check if an algorithm
   508   doesn't use any extra feature of a certain implementation.
   509 
   510 - The concept descriptor classes also provide a <em>checker class</em>
   511   that makes it possible check whether a certain implementation of a
   512   concept indeed provides all the required features.
   513 
   514 - Finally, They can serve as a skeleton of a new implementation of a concept.
   515 
   516 */
   517 
   518 
   519 /**
   520 @defgroup graph_concepts Graph Structure Concepts
   521 @ingroup concept
   522 \brief Skeleton and concept checking classes for graph structures
   523 
   524 This group contains the skeletons and concept checking classes of LEMON's
   525 graph structures and helper classes used to implement these.
   526 */
   527 
   528 /* --- Unused group
   529 @defgroup experimental Experimental Structures and Algorithms
   530 This group contains some Experimental structures and algorithms.
   531 The stuff here is subject to change.
   532 */
   533 
   534 /**
   535 \anchor demoprograms
   536 
   537 @defgroup demos Demo programs
   538 
   539 Some demo programs are listed here. Their full source codes can be found in
   540 the \c demo subdirectory of the source tree.
   541 
   542 The standard compilation procedure (<tt>./configure;make</tt>) will compile
   543 them, as well. 
   544 
   545 */
   546 
   547 /**
   548 @defgroup tools Standalone utility applications
   549 
   550 Some utility applications are listed here. 
   551 
   552 The standard compilation procedure (<tt>./configure;make</tt>) will compile
   553 them, as well. 
   554 
   555 */
   556