summary |
shortlog |
changelog |
graph |
tags |
bookmarks |
branches |
files |
changeset |
file |
latest |
revisions |
annotate |
diff |
comparison |
raw |
help

doc/groups.dox

changeset 40 | 8f4e8273a458 |

child 41 | b11737922197 |

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 +