Index: doc/groups.dox =================================================================== --- doc/groups.dox (revision 325) +++ doc/groups.dox (revision 326) @@ -41,16 +41,4 @@ some graph features like arc/edge or node deletion. -Alteration of standard containers need a very limited number of -operations, these together satisfy the everyday requirements. -In the case of graph structures, different operations are needed which do -not alter the physical graph, but gives another view. If some nodes or -arcs have to be hidden or the reverse oriented graph have to be used, then -this is the case. It also may happen that in a flow implementation -the residual graph can be accessed by another algorithm, or a node-set -is to be shrunk for another algorithm. -LEMON also provides a variety of graphs for these requirements called -\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only -in conjunction with other graph representations. - You are free to use the graph structure that fit your requirements the best, most graph algorithms and auxiliary data structures can be used @@ -58,14 +46,4 @@ See also: \ref graph_concepts "Graph Structure Concepts". -*/ - -/** -@defgroup semi_adaptors Semi-Adaptor Classes for Graphs -@ingroup graphs -\brief Graph types between real graphs and graph adaptors. - -This group describes some graph types between real graphs and graph adaptors. -These classes wrap graphs to give new functionality as the adaptors do it. -On the other hand they are not light-weight structures as the adaptors. */ @@ -156,12 +134,4 @@ /** -@defgroup matrices Matrices -@ingroup datas -\brief Two dimensional data storages implemented in LEMON. - -This group describes two dimensional data storages implemented in LEMON. -*/ - -/** @defgroup paths Path Structures @ingroup datas @@ -215,140 +185,4 @@ /** -@defgroup max_flow Maximum Flow Algorithms -@ingroup algs -\brief Algorithms for finding maximum flows. - -This group describes the algorithms for finding maximum flows and -feasible circulations. - -The maximum flow problem is to find a flow between a single source and -a single target that is maximum. Formally, there is a \f$G=(V,A)\f$ -directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity -function and given \f$s, t \in V\f$ source and target node. The -maximum flow is the \f$f_a\f$ solution of the next optimization problem: - -\f[ 0 \le f_a \le c_a \f] -\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} -\qquad \forall u \in V \setminus \{s,t\}\f] -\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f] - -LEMON contains several algorithms for solving maximum flow problems: -- \ref lemon::EdmondsKarp "Edmonds-Karp" -- \ref lemon::Preflow "Goldberg's Preflow algorithm" -- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees" -- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees" - -In most cases the \ref lemon::Preflow "Preflow" algorithm provides the -fastest method to compute the maximum flow. All impelementations -provides functions to query the minimum cut, which is the dual linear -programming problem of the maximum flow. -*/ - -/** -@defgroup min_cost_flow Minimum Cost Flow Algorithms -@ingroup algs - -\brief Algorithms for finding minimum cost flows and circulations. - -This group describes the algorithms for finding minimum cost flows and -circulations. -*/ - -/** -@defgroup min_cut Minimum Cut Algorithms -@ingroup algs - -\brief Algorithms for finding minimum cut in graphs. - -This group describes the algorithms for finding minimum cut in graphs. - -The minimum cut problem is to find a non-empty and non-complete -\f$X\f$ subset of the vertices with minimum overall capacity on -outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an -\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum -cut is the \f$X\f$ solution of the next optimization problem: - -\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}} -\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f] - -LEMON contains several algorithms related to minimum cut problems: - -- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut - in directed graphs -- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to - calculate minimum cut in undirected graphs -- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all - pairs minimum cut in undirected graphs - -If you want to find minimum cut just between two distinict nodes, -please see the \ref max_flow "Maximum Flow page". -*/ - -/** -@defgroup graph_prop Connectivity and Other Graph Properties -@ingroup algs -\brief Algorithms for discovering the graph properties - -This group describes the algorithms for discovering the graph properties -like connectivity, bipartiteness, euler property, simplicity etc. - -\image html edge_biconnected_components.png -\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth -*/ - -/** -@defgroup planar Planarity Embedding and Drawing -@ingroup algs -\brief Algorithms for planarity checking, embedding and drawing - -This group describes the algorithms for planarity checking, -embedding and drawing. - -\image html planar.png -\image latex planar.eps "Plane graph" width=\textwidth -*/ - -/** -@defgroup matching Matching Algorithms -@ingroup algs -\brief Algorithms for finding matchings in graphs and bipartite graphs. - -This group contains algorithm objects and functions to calculate -matchings in graphs and bipartite graphs. The general matching problem is -finding a subset of the arcs which does not shares common endpoints. - -There are several different algorithms for calculate matchings in -graphs. The matching problems in bipartite graphs are generally -easier than in general graphs. The goal of the matching optimization -can be the finding maximum cardinality, maximum weight or minimum cost -matching. The search can be constrained to find perfect or -maximum cardinality matching. - -LEMON contains the next algorithms: -- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp - augmenting path algorithm for calculate maximum cardinality matching in - bipartite graphs -- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel - algorithm for calculate maximum cardinality matching in bipartite graphs -- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching" - Successive shortest path algorithm for calculate maximum weighted matching - and maximum weighted bipartite matching in bipartite graph -- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching" - Successive shortest path algorithm for calculate minimum cost maximum - matching in bipartite graph -- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm - for calculate maximum cardinality matching in general graph -- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom - shrinking algorithm for calculate maximum weighted matching in general - graph -- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching" - Edmond's blossom shrinking algorithm for calculate maximum weighted - perfect matching in general graph - -\image html bipartite_matching.png -\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth -*/ - -/** @defgroup spantree Minimum Spanning Tree Algorithms @ingroup algs @@ -360,58 +194,4 @@ /** -@defgroup auxalg Auxiliary Algorithms -@ingroup algs -\brief Auxiliary algorithms implemented in LEMON. - -This group describes some algorithms implemented in LEMON -in order to make it easier to implement complex algorithms. -*/ - -/** -@defgroup approx Approximation Algorithms -@ingroup algs -\brief Approximation algorithms. - -This group describes the approximation and heuristic algorithms -implemented in LEMON. -*/ - -/** -@defgroup gen_opt_group General Optimization Tools -\brief This group describes some general optimization frameworks -implemented in LEMON. - -This group describes some general optimization frameworks -implemented in LEMON. -*/ - -/** -@defgroup lp_group Lp and Mip Solvers -@ingroup gen_opt_group -\brief Lp and Mip solver interfaces for LEMON. - -This group describes Lp and Mip solver interfaces for LEMON. The -various LP solvers could be used in the same manner with this -interface. -*/ - -/** -@defgroup lp_utils Tools for Lp and Mip Solvers -@ingroup lp_group -\brief Helper tools to the Lp and Mip solvers. - -This group adds some helper tools to general optimization framework -implemented in LEMON. -*/ - -/** -@defgroup metah Metaheuristics -@ingroup gen_opt_group -\brief Metaheuristics for LEMON library. - -This group describes some metaheuristic optimization tools. -*/ - -/** @defgroup utils Tools and Utilities \brief Tools and utilities for programming in LEMON @@ -459,6 +239,6 @@ This group describes the tools for importing and exporting graphs -and graph related data. Now it supports the \ref lgf-format -"LEMON Graph Format", the \c DIMACS format and the encapsulated +and graph related data. Now it supports the LEMON format +and the encapsulated postscript (EPS) format. postscript (EPS) format. */ @@ -524,5 +304,5 @@ @ingroup concept \brief Skeleton and concept checking classes for maps - + This group describes the skeletons and concept checking classes of maps. */ @@ -539,12 +319,2 @@ build the library. */ - -/** -@defgroup tools Standalone utility applications - -Some utility applications are listed here. - -The standard compilation procedure (./configure;make) will compile -them, as well. -*/ - Index: doc/mainpage.dox =================================================================== --- doc/mainpage.dox (revision 318) +++ doc/mainpage.dox (revision 320) @@ -42,11 +42,4 @@ \subsection howtoread How to read the documentation -If you want to get a quick start and see the most important features then -take a look at our \ref quicktour -"Quick Tour to LEMON" which will guide you along. - -If you already feel like using our library, see the page that tells you -\ref getstart "How to start using LEMON". - If you want to see how LEMON works, see