1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/doc/groups.dox Mon Jan 07 19:22:09 2008 +0100
1.3 @@ -0,0 +1,585 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +/**
1.23 +@defgroup datas Data Structures
1.24 +This group describes the several graph structures implemented in LEMON.
1.25 +*/
1.26 +
1.27 +/**
1.28 +@defgroup graphs Graph Structures
1.29 +@ingroup datas
1.30 +\brief Graph structures implemented in LEMON.
1.31 +
1.32 +The implementation of combinatorial algorithms heavily relies on
1.33 +efficient graph implementations. LEMON offers data structures which are
1.34 +planned to be easily used in an experimental phase of implementation studies,
1.35 +and thereafter the program code can be made efficient by small modifications.
1.36 +
1.37 +The most efficient implementation of diverse applications require the
1.38 +usage of different physical graph implementations. These differences
1.39 +appear in the size of graph we require to handle, memory or time usage
1.40 +limitations or in the set of operations through which the graph can be
1.41 +accessed. LEMON provides several physical graph structures to meet
1.42 +the diverging requirements of the possible users. In order to save on
1.43 +running time or on memory usage, some structures may fail to provide
1.44 +some graph features like edge or node deletion.
1.45 +
1.46 +Alteration of standard containers need a very limited number of
1.47 +operations, these together satisfy the everyday requirements.
1.48 +In the case of graph structures, different operations are needed which do
1.49 +not alter the physical graph, but gives another view. If some nodes or
1.50 +edges have to be hidden or the reverse oriented graph have to be used, then
1.51 +this is the case. It also may happen that in a flow implementation
1.52 +the residual graph can be accessed by another algorithm, or a node-set
1.53 +is to be shrunk for another algorithm.
1.54 +LEMON also provides a variety of graphs for these requirements called
1.55 +\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
1.56 +in conjunction with other graph representation.
1.57 +
1.58 +You are free to use the graph structure that fit your requirements
1.59 +the best, most graph algorithms and auxiliary data structures can be used
1.60 +with any graph structures.
1.61 +*/
1.62 +
1.63 +/**
1.64 +@defgroup semi_adaptors Semi-Adaptors Classes for Graphs
1.65 +@ingroup graphs
1.66 +\brief Graph types between real graphs and graph adaptors.
1.67 +
1.68 +Graph types between real graphs and graph adaptors. These classes wrap
1.69 +graphs to give new functionality as the adaptors do it. On the other
1.70 +hand they are not light-weight structures as the adaptors.
1.71 +*/
1.72 +
1.73 +/**
1.74 +@defgroup maps Maps
1.75 +@ingroup datas
1.76 +\brief Some special purpose map to make life easier.
1.77 +
1.78 +LEMON provides several special maps that e.g. combine
1.79 +new maps from existing ones.
1.80 +*/
1.81 +
1.82 +/**
1.83 +@defgroup graph_maps Graph Maps
1.84 +@ingroup maps
1.85 +\brief Special Graph-Related Maps.
1.86 +
1.87 +These maps are specifically designed to assign values to the nodes and edges of
1.88 +graphs.
1.89 +*/
1.90 +
1.91 +
1.92 +/**
1.93 +\defgroup map_adaptors Map Adaptors
1.94 +\ingroup maps
1.95 +\brief Tools to create new maps from existing ones
1.96 +
1.97 +Map adaptors are used to create "implicit" maps from other maps.
1.98 +
1.99 +Most of them are \ref lemon::concepts::ReadMap "ReadMap"s. They can
1.100 +make arithmetic operations between one or two maps (negation, scaling,
1.101 +addition, multiplication etc.) or e.g. convert a map to another one
1.102 +of different Value type.
1.103 +
1.104 +The typical usage of this classes is the passing implicit maps to
1.105 +algorithms. If a function type algorithm is called then the function
1.106 +type map adaptors can be used comfortable. For example let's see the
1.107 +usage of map adaptors with the \c graphToEps() function:
1.108 +\code
1.109 + Color nodeColor(int deg) {
1.110 + if (deg >= 2) {
1.111 + return Color(0.5, 0.0, 0.5);
1.112 + } else if (deg == 1) {
1.113 + return Color(1.0, 0.5, 1.0);
1.114 + } else {
1.115 + return Color(0.0, 0.0, 0.0);
1.116 + }
1.117 + }
1.118 +
1.119 + Graph::NodeMap<int> degree_map(graph);
1.120 +
1.121 + graphToEps(graph, "graph.eps")
1.122 + .coords(coords).scaleToA4().undirected()
1.123 + .nodeColors(composeMap(functorMap(nodeColor), degree_map))
1.124 + .run();
1.125 +\endcode
1.126 +The \c functorMap() function makes an \c int to \c Color map from the
1.127 +\e nodeColor() function. The \c composeMap() compose the \e degree_map
1.128 +and the previous created map. The composed map is proper function to
1.129 +get color of each node.
1.130 +
1.131 +The usage with class type algorithms is little bit harder. In this
1.132 +case the function type map adaptors can not be used, because the
1.133 +function map adaptors give back temporarly objects.
1.134 +\code
1.135 + Graph graph;
1.136 +
1.137 + typedef Graph::EdgeMap<double> DoubleEdgeMap;
1.138 + DoubleEdgeMap length(graph);
1.139 + DoubleEdgeMap speed(graph);
1.140 +
1.141 + typedef DivMap<DoubleEdgeMap, DoubleEdgeMap> TimeMap;
1.142 +
1.143 + TimeMap time(length, speed);
1.144 +
1.145 + Dijkstra<Graph, TimeMap> dijkstra(graph, time);
1.146 + dijkstra.run(source, target);
1.147 +\endcode
1.148 +
1.149 +We have a length map and a maximum speed map on a graph. The minimum
1.150 +time to pass the edge can be calculated as the division of the two
1.151 +maps which can be done implicitly with the \c DivMap template
1.152 +class. We use the implicit minimum time map as the length map of the
1.153 +\c Dijkstra algorithm.
1.154 +*/
1.155 +
1.156 +/**
1.157 +@defgroup matrices Matrices
1.158 +@ingroup datas
1.159 +\brief Two dimensional data storages.
1.160 +
1.161 +Two dimensional data storages.
1.162 +*/
1.163 +
1.164 +/**
1.165 +@defgroup paths Path Structures
1.166 +@ingroup datas
1.167 +\brief Path structures implemented in LEMON.
1.168 +
1.169 +LEMON provides flexible data structures
1.170 +to work with paths.
1.171 +
1.172 +All of them have similar interfaces, and it can be copied easily with
1.173 +assignment operator and copy constructor. This make it easy and
1.174 +efficient to have e.g. the Dijkstra algorithm to store its result in
1.175 +any kind of path structure.
1.176 +
1.177 +\sa lemon::concepts::Path
1.178 +
1.179 +*/
1.180 +
1.181 +/**
1.182 +@defgroup auxdat Auxiliary Data Structures
1.183 +@ingroup datas
1.184 +\brief Some data structures implemented in LEMON.
1.185 +
1.186 +This group describes the data structures implemented in LEMON in
1.187 +order to make it easier to implement combinatorial algorithms.
1.188 +*/
1.189 +
1.190 +
1.191 +/**
1.192 +@defgroup algs Algorithms
1.193 +\brief This group describes the several algorithms
1.194 +implemented in LEMON.
1.195 +
1.196 +This group describes the several algorithms
1.197 +implemented in LEMON.
1.198 +*/
1.199 +
1.200 +/**
1.201 +@defgroup search Graph Search
1.202 +@ingroup algs
1.203 +\brief This group contains the common graph
1.204 +search algorithms.
1.205 +
1.206 +This group contains the common graph
1.207 +search algorithms like Bfs and Dfs.
1.208 +*/
1.209 +
1.210 +/**
1.211 +@defgroup shortest_path Shortest Path algorithms
1.212 +@ingroup algs
1.213 +\brief This group describes the algorithms
1.214 +for finding shortest paths.
1.215 +
1.216 +This group describes the algorithms for finding shortest paths in
1.217 +graphs.
1.218 +
1.219 +*/
1.220 +
1.221 +/**
1.222 +@defgroup max_flow Maximum Flow algorithms
1.223 +@ingroup algs
1.224 +\brief This group describes the algorithms for finding maximum flows.
1.225 +
1.226 +This group describes the algorithms for finding maximum flows and
1.227 +feasible circulations.
1.228 +
1.229 +The maximum flow problem is to find a flow between a single-source and
1.230 +single-target that is maximum. Formally, there is \f$G=(V,A)\f$
1.231 +directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
1.232 +function and given \f$s, t \in V\f$ source and target node. The
1.233 +maximum flow is the solution of the next optimization problem:
1.234 +
1.235 +\f[ 0 \le f_a \le c_a \f]
1.236 +\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \quad u \in V \setminus \{s,t\}\f]
1.237 +\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
1.238 +
1.239 +The lemon contains several algorithms for solve maximum flow problems:
1.240 +- \ref lemon::EdmondsKarp "Edmonds-Karp"
1.241 +- \ref lemon::Preflow "Goldberg's Preflow algorithm"
1.242 +- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic tree"
1.243 +- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
1.244 +
1.245 +In most cases the \ref lemon::Preflow "preflow" algorithm provides the
1.246 +fastest method to compute the maximum flow. All impelementations
1.247 +provides functions for query the minimum cut, which is the dual linear
1.248 +programming probelm of the maximum flow.
1.249 +
1.250 +*/
1.251 +
1.252 +/**
1.253 +@defgroup min_cost_flow Minimum Cost Flow algorithms
1.254 +@ingroup algs
1.255 +
1.256 +\brief This group describes the algorithms
1.257 +for finding minimum cost flows and circulations.
1.258 +
1.259 +This group describes the algorithms for finding minimum cost flows and
1.260 +circulations.
1.261 +*/
1.262 +
1.263 +/**
1.264 +@defgroup min_cut Minimum Cut algorithms
1.265 +@ingroup algs
1.266 +
1.267 +\brief This group describes the algorithms for finding minimum cut in
1.268 +graphs.
1.269 +
1.270 +This group describes the algorithms for finding minimum cut in graphs.
1.271 +
1.272 +The minimum cut problem is to find a non-empty and non-complete
1.273 +\f$X\f$ subset of the vertices with minimum overall capacity on
1.274 +outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
1.275 +\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
1.276 +cut is the solution of the next optimization problem:
1.277 +
1.278 +\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
1.279 +
1.280 +The lemon contains several algorithms related to minimum cut problems:
1.281 +
1.282 +- \ref lemon::HaoOrlin "Hao-Orlin algorithm" for calculate minimum cut
1.283 + in directed graphs
1.284 +- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
1.285 + calculate minimum cut in undirected graphs
1.286 +- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" for calculate all
1.287 + pairs minimum cut in undirected graphs
1.288 +
1.289 +If you want to find minimum cut just between two distinict nodes,
1.290 +please see the \ref max_flow "Maximum Flow page".
1.291 +
1.292 +*/
1.293 +
1.294 +/**
1.295 +@defgroup graph_prop Connectivity and other graph properties
1.296 +@ingroup algs
1.297 +\brief This group describes the algorithms
1.298 +for discover the graph properties
1.299 +
1.300 +This group describes the algorithms for discover the graph properties
1.301 +like connectivity, bipartiteness, euler property, simplicity, etc...
1.302 +
1.303 +\image html edge_biconnected_components.png
1.304 +\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
1.305 +*/
1.306 +
1.307 +/**
1.308 +@defgroup planar Planarity embedding and drawing
1.309 +@ingroup algs
1.310 +\brief This group contains algorithms for planarity embedding and drawing
1.311 +
1.312 +This group contains algorithms for planarity checking, embedding and drawing.
1.313 +
1.314 +\image html planar.png
1.315 +\image latex planar.eps "Plane graph" width=\textwidth
1.316 +*/
1.317 +
1.318 +/**
1.319 +@defgroup matching Matching algorithms
1.320 +@ingroup algs
1.321 +\brief This group describes the algorithms
1.322 +for find matchings in graphs and bipartite graphs.
1.323 +
1.324 +This group provides some algorithm objects and function to calculate
1.325 +matchings in graphs and bipartite graphs. The general matching problem is
1.326 +finding a subset of the edges which does not shares common endpoints.
1.327 +
1.328 +There are several different algorithms for calculate matchings in
1.329 +graphs. The matching problems in bipartite graphs are generally
1.330 +easier than in general graphs. The goal of the matching optimization
1.331 +can be the finding maximum cardinality, maximum weight or minimum cost
1.332 +matching. The search can be constrained to find perfect or
1.333 +maximum cardinality matching.
1.334 +
1.335 +Lemon contains the next algorithms:
1.336 +- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
1.337 + augmenting path algorithm for calculate maximum cardinality matching in
1.338 + bipartite graphs
1.339 +- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
1.340 + algorithm for calculate maximum cardinality matching in bipartite graphs
1.341 +- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
1.342 + Successive shortest path algorithm for calculate maximum weighted matching
1.343 + and maximum weighted bipartite matching in bipartite graph
1.344 +- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
1.345 + Successive shortest path algorithm for calculate minimum cost maximum
1.346 + matching in bipartite graph
1.347 +- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
1.348 + for calculate maximum cardinality matching in general graph
1.349 +- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
1.350 + shrinking algorithm for calculate maximum weighted matching in general
1.351 + graph
1.352 +- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
1.353 + Edmond's blossom shrinking algorithm for calculate maximum weighted
1.354 + perfect matching in general graph
1.355 +
1.356 +\image html bipartite_matching.png
1.357 +\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
1.358 +
1.359 +*/
1.360 +
1.361 +/**
1.362 +@defgroup spantree Minimum Spanning Tree algorithms
1.363 +@ingroup algs
1.364 +\brief This group contains the algorithms for finding a minimum cost spanning
1.365 +tree in a graph
1.366 +
1.367 +This group contains the algorithms for finding a minimum cost spanning
1.368 +tree in a graph
1.369 +*/
1.370 +
1.371 +
1.372 +/**
1.373 +@defgroup auxalg Auxiliary algorithms
1.374 +@ingroup algs
1.375 +\brief Some algorithms implemented in LEMON.
1.376 +
1.377 +This group describes the algorithms in LEMON in order to make
1.378 +it easier to implement complex algorithms.
1.379 +*/
1.380 +
1.381 +/**
1.382 +@defgroup approx Approximation algorithms
1.383 +\brief Approximation algorithms
1.384 +
1.385 +Approximation and heuristic algorithms
1.386 +*/
1.387 +
1.388 +/**
1.389 +@defgroup gen_opt_group General Optimization Tools
1.390 +\brief This group describes some general optimization frameworks
1.391 +implemented in LEMON.
1.392 +
1.393 +This group describes some general optimization frameworks
1.394 +implemented in LEMON.
1.395 +
1.396 +*/
1.397 +
1.398 +/**
1.399 +@defgroup lp_group Lp and Mip solvers
1.400 +@ingroup gen_opt_group
1.401 +\brief Lp and Mip solver interfaces for LEMON.
1.402 +
1.403 +This group describes Lp and Mip solver interfaces for LEMON. The
1.404 +various LP solvers could be used in the same manner with this
1.405 +interface.
1.406 +
1.407 +*/
1.408 +
1.409 +/**
1.410 +@defgroup lp_utils Tools for Lp and Mip solvers
1.411 +@ingroup lp_group
1.412 +\brief This group adds some helper tools to the Lp and Mip solvers
1.413 +implemented in LEMON.
1.414 +
1.415 +This group adds some helper tools to general optimization framework
1.416 +implemented in LEMON.
1.417 +*/
1.418 +
1.419 +/**
1.420 +@defgroup metah Metaheuristics
1.421 +@ingroup gen_opt_group
1.422 +\brief Metaheuristics for LEMON library.
1.423 +
1.424 +This group contains some metaheuristic optimization tools.
1.425 +*/
1.426 +
1.427 +/**
1.428 +@defgroup utils Tools and Utilities
1.429 +\brief Tools and Utilities for Programming in LEMON
1.430 +
1.431 +Tools and Utilities for Programming in LEMON
1.432 +*/
1.433 +
1.434 +/**
1.435 +@defgroup gutils Basic Graph Utilities
1.436 +@ingroup utils
1.437 +\brief This group describes some simple basic graph utilities.
1.438 +
1.439 +This group describes some simple basic graph utilities.
1.440 +*/
1.441 +
1.442 +/**
1.443 +@defgroup misc Miscellaneous Tools
1.444 +@ingroup utils
1.445 +Here you can find several useful tools for development,
1.446 +debugging and testing.
1.447 +*/
1.448 +
1.449 +
1.450 +/**
1.451 +@defgroup timecount Time measuring and Counting
1.452 +@ingroup misc
1.453 +Here you can find simple tools for measuring the performance
1.454 +of algorithms.
1.455 +*/
1.456 +
1.457 +/**
1.458 +@defgroup graphbits Tools for Graph Implementation
1.459 +@ingroup utils
1.460 +\brief Tools to Make It Easier to Make Graphs.
1.461 +
1.462 +This group describes the tools that makes it easier to make graphs and
1.463 +the maps that dynamically update with the graph changes.
1.464 +*/
1.465 +
1.466 +/**
1.467 +@defgroup exceptions Exceptions
1.468 +@ingroup utils
1.469 +This group contains the exceptions thrown by LEMON library
1.470 +*/
1.471 +
1.472 +/**
1.473 +@defgroup io_group Input-Output
1.474 +\brief Several Graph Input-Output methods
1.475 +
1.476 +Here you can find tools for importing and exporting graphs
1.477 +and graph related data. Now it supports the LEMON format, the
1.478 +\c DIMACS format and the encapsulated postscript format.
1.479 +*/
1.480 +
1.481 +/**
1.482 +@defgroup lemon_io Lemon Input-Output
1.483 +@ingroup io_group
1.484 +\brief Reading and writing LEMON format
1.485 +
1.486 +Methods for reading and writing LEMON format. More about this
1.487 +format you can find on the \ref graph-io-page "Graph Input-Output"
1.488 +tutorial pages.
1.489 +*/
1.490 +
1.491 +/**
1.492 +@defgroup section_io Section readers and writers
1.493 +@ingroup lemon_io
1.494 +\brief Section readers and writers for lemon Input-Output.
1.495 +
1.496 +Here you can find which section readers and writers can attach to
1.497 +the LemonReader and LemonWriter.
1.498 +*/
1.499 +
1.500 +/**
1.501 +@defgroup item_io Item Readers and Writers
1.502 +@ingroup lemon_io
1.503 +\brief Item readers and writers for lemon Input-Output.
1.504 +
1.505 +The Input-Output classes can handle more data type by example
1.506 +as map or attribute value. Each of these should be written and
1.507 +read some way. The module make possible to do this.
1.508 +*/
1.509 +
1.510 +/**
1.511 +@defgroup eps_io Postscript exporting
1.512 +@ingroup io_group
1.513 +\brief General \c EPS drawer and graph exporter
1.514 +
1.515 +This group contains general \c EPS drawing methods and special
1.516 +graph exporting tools.
1.517 +*/
1.518 +
1.519 +
1.520 +/**
1.521 +@defgroup concept Concepts
1.522 +\brief Skeleton classes and concept checking classes
1.523 +
1.524 +This group describes the data/algorithm skeletons and concept checking
1.525 +classes implemented in LEMON.
1.526 +
1.527 +The purpose of the classes in this group is fourfold.
1.528 +
1.529 +- These classes contain the documentations of the concepts. In order
1.530 + to avoid document multiplications, an implementation of a concept
1.531 + simply refers to the corresponding concept class.
1.532 +
1.533 +- These classes declare every functions, <tt>typedef</tt>s etc. an
1.534 + implementation of the concepts should provide, however completely
1.535 + without implementations and real data structures behind the
1.536 + interface. On the other hand they should provide nothing else. All
1.537 + the algorithms working on a data structure meeting a certain concept
1.538 + should compile with these classes. (Though it will not run properly,
1.539 + of course.) In this way it is easily to check if an algorithm
1.540 + doesn't use any extra feature of a certain implementation.
1.541 +
1.542 +- The concept descriptor classes also provide a <em>checker class</em>
1.543 + that makes it possible check whether a certain implementation of a
1.544 + concept indeed provides all the required features.
1.545 +
1.546 +- Finally, They can serve as a skeleton of a new implementation of a concept.
1.547 +
1.548 +*/
1.549 +
1.550 +
1.551 +/**
1.552 +@defgroup graph_concepts Graph Structure Concepts
1.553 +@ingroup concept
1.554 +\brief Skeleton and concept checking classes for graph structures
1.555 +
1.556 +This group contains the skeletons and concept checking classes of LEMON's
1.557 +graph structures and helper classes used to implement these.
1.558 +*/
1.559 +
1.560 +/* --- Unused group
1.561 +@defgroup experimental Experimental Structures and Algorithms
1.562 +This group contains some Experimental structures and algorithms.
1.563 +The stuff here is subject to change.
1.564 +*/
1.565 +
1.566 +/**
1.567 +\anchor demoprograms
1.568 +
1.569 +@defgroup demos Demo programs
1.570 +
1.571 +Some demo programs are listed here. Their full source codes can be found in
1.572 +the \c demo subdirectory of the source tree.
1.573 +
1.574 +The standard compilation procedure (<tt>./configure;make</tt>) will compile
1.575 +them, as well.
1.576 +
1.577 +*/
1.578 +
1.579 +/**
1.580 +@defgroup tools Standalone utility applications
1.581 +
1.582 +Some utility applications are listed here.
1.583 +
1.584 +The standard compilation procedure (<tt>./configure;make</tt>) will compile
1.585 +them, as well.
1.586 +
1.587 +*/
1.588 +