1.1 --- a/doc/groups.dox Sun Jul 13 16:46:56 2008 +0100
1.2 +++ b/doc/groups.dox Sun Jul 13 19:51:02 2008 +0100
1.3 @@ -1,6 +1,6 @@
1.4 -/* -*- C++ -*-
1.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.6 *
1.7 - * This file is a part of LEMON, a generic C++ optimization library
1.8 + * This file is a part of LEMON, a generic C++ optimization library.
1.9 *
1.10 * Copyright (C) 2003-2008
1.11 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.12 @@ -26,10 +26,10 @@
1.13 @ingroup datas
1.14 \brief Graph structures implemented in LEMON.
1.15
1.16 -The implementation of combinatorial algorithms heavily relies on
1.17 -efficient graph implementations. LEMON offers data structures which are
1.18 -planned to be easily used in an experimental phase of implementation studies,
1.19 -and thereafter the program code can be made efficient by small modifications.
1.20 +The implementation of combinatorial algorithms heavily relies on
1.21 +efficient graph implementations. LEMON offers data structures which are
1.22 +planned to be easily used in an experimental phase of implementation studies,
1.23 +and thereafter the program code can be made efficient by small modifications.
1.24
1.25 The most efficient implementation of diverse applications require the
1.26 usage of different physical graph implementations. These differences
1.27 @@ -40,21 +40,21 @@
1.28 running time or on memory usage, some structures may fail to provide
1.29 some graph features like arc/edge or node deletion.
1.30
1.31 -Alteration of standard containers need a very limited number of
1.32 -operations, these together satisfy the everyday requirements.
1.33 -In the case of graph structures, different operations are needed which do
1.34 -not alter the physical graph, but gives another view. If some nodes or
1.35 +Alteration of standard containers need a very limited number of
1.36 +operations, these together satisfy the everyday requirements.
1.37 +In the case of graph structures, different operations are needed which do
1.38 +not alter the physical graph, but gives another view. If some nodes or
1.39 arcs have to be hidden or the reverse oriented graph have to be used, then
1.40 -this is the case. It also may happen that in a flow implementation
1.41 -the residual graph can be accessed by another algorithm, or a node-set
1.42 -is to be shrunk for another algorithm.
1.43 -LEMON also provides a variety of graphs for these requirements called
1.44 -\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
1.45 -in conjunction with other graph representations.
1.46 +this is the case. It also may happen that in a flow implementation
1.47 +the residual graph can be accessed by another algorithm, or a node-set
1.48 +is to be shrunk for another algorithm.
1.49 +LEMON also provides a variety of graphs for these requirements called
1.50 +\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
1.51 +in conjunction with other graph representations.
1.52
1.53 You are free to use the graph structure that fit your requirements
1.54 the best, most graph algorithms and auxiliary data structures can be used
1.55 -with any graph structures.
1.56 +with any graph structures.
1.57 */
1.58
1.59 /**
1.60 @@ -63,12 +63,12 @@
1.61 \brief Graph types between real graphs and graph adaptors.
1.62
1.63 This group describes some graph types between real graphs and graph adaptors.
1.64 -These classes wrap graphs to give new functionality as the adaptors do it.
1.65 +These classes wrap graphs to give new functionality as the adaptors do it.
1.66 On the other hand they are not light-weight structures as the adaptors.
1.67 */
1.68
1.69 /**
1.70 -@defgroup maps Maps
1.71 +@defgroup maps Maps
1.72 @ingroup datas
1.73 \brief Map structures implemented in LEMON.
1.74
1.75 @@ -79,7 +79,7 @@
1.76 */
1.77
1.78 /**
1.79 -@defgroup graph_maps Graph Maps
1.80 +@defgroup graph_maps Graph Maps
1.81 @ingroup maps
1.82 \brief Special graph-related maps.
1.83
1.84 @@ -115,14 +115,14 @@
1.85 return Color(0.0, 0.0, 0.0);
1.86 }
1.87 }
1.88 -
1.89 +
1.90 Digraph::NodeMap<int> degree_map(graph);
1.91 -
1.92 +
1.93 digraphToEps(graph, "graph.eps")
1.94 .coords(coords).scaleToA4().undirected()
1.95 .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
1.96 .run();
1.97 -\endcode
1.98 +\endcode
1.99 The \c functorToMap() function makes an \c int to \c Color map from the
1.100 \e nodeColor() function. The \c composeMap() compose the \e degree_map
1.101 and the previously created map. The composed map is a proper function to
1.102 @@ -140,7 +140,7 @@
1.103
1.104 typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
1.105 TimeMap time(length, speed);
1.106 -
1.107 +
1.108 Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
1.109 dijkstra.run(source, target);
1.110 \endcode
1.111 @@ -152,7 +152,7 @@
1.112 */
1.113
1.114 /**
1.115 -@defgroup matrices Matrices
1.116 +@defgroup matrices Matrices
1.117 @ingroup datas
1.118 \brief Two dimensional data storages implemented in LEMON.
1.119
1.120 @@ -200,7 +200,7 @@
1.121 @ingroup algs
1.122 \brief Common graph search algorithms.
1.123
1.124 -This group describes the common graph search algorithms like
1.125 +This group describes the common graph search algorithms like
1.126 Breadth-first search (Bfs) and Depth-first search (Dfs).
1.127 */
1.128
1.129 @@ -212,9 +212,9 @@
1.130 This group describes the algorithms for finding shortest paths in graphs.
1.131 */
1.132
1.133 -/**
1.134 -@defgroup max_flow Maximum Flow algorithms
1.135 -@ingroup algs
1.136 +/**
1.137 +@defgroup max_flow Maximum Flow algorithms
1.138 +@ingroup algs
1.139 \brief Algorithms for finding maximum flows.
1.140
1.141 This group describes the algorithms for finding maximum flows and
1.142 @@ -231,7 +231,7 @@
1.143 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
1.144
1.145 LEMON contains several algorithms for solving maximum flow problems:
1.146 -- \ref lemon::EdmondsKarp "Edmonds-Karp"
1.147 +- \ref lemon::EdmondsKarp "Edmonds-Karp"
1.148 - \ref lemon::Preflow "Goldberg's Preflow algorithm"
1.149 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
1.150 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
1.151 @@ -250,12 +250,12 @@
1.152 \brief Algorithms for finding minimum cost flows and circulations.
1.153
1.154 This group describes the algorithms for finding minimum cost flows and
1.155 -circulations.
1.156 +circulations.
1.157 */
1.158
1.159 /**
1.160 -@defgroup min_cut Minimum Cut algorithms
1.161 -@ingroup algs
1.162 +@defgroup min_cut Minimum Cut algorithms
1.163 +@ingroup algs
1.164
1.165 \brief Algorithms for finding minimum cut in graphs.
1.166
1.167 @@ -272,7 +272,7 @@
1.168 LEMON contains several algorithms related to minimum cut problems:
1.169
1.170 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
1.171 - in directed graphs
1.172 + in directed graphs
1.173 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
1.174 calculate minimum cut in undirected graphs
1.175 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
1.176 @@ -307,14 +307,14 @@
1.177 */
1.178
1.179 /**
1.180 -@defgroup matching Matching algorithms
1.181 +@defgroup matching Matching algorithms
1.182 @ingroup algs
1.183 \brief Algorithms for finding matchings in graphs and bipartite graphs.
1.184
1.185 This group contains algorithm objects and functions to calculate
1.186 matchings in graphs and bipartite graphs. The general matching problem is
1.187 finding a subset of the arcs which does not shares common endpoints.
1.188 -
1.189 +
1.190 There are several different algorithms for calculate matchings in
1.191 graphs. The matching problems in bipartite graphs are generally
1.192 easier than in general graphs. The goal of the matching optimization
1.193 @@ -323,16 +323,16 @@
1.194 maximum cardinality matching.
1.195
1.196 Lemon contains the next algorithms:
1.197 -- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
1.198 - augmenting path algorithm for calculate maximum cardinality matching in
1.199 +- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
1.200 + augmenting path algorithm for calculate maximum cardinality matching in
1.201 bipartite graphs
1.202 -- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
1.203 - algorithm for calculate maximum cardinality matching in bipartite graphs
1.204 -- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
1.205 - Successive shortest path algorithm for calculate maximum weighted matching
1.206 +- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
1.207 + algorithm for calculate maximum cardinality matching in bipartite graphs
1.208 +- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
1.209 + Successive shortest path algorithm for calculate maximum weighted matching
1.210 and maximum weighted bipartite matching in bipartite graph
1.211 -- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
1.212 - Successive shortest path algorithm for calculate minimum cost maximum
1.213 +- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
1.214 + Successive shortest path algorithm for calculate minimum cost maximum
1.215 matching in bipartite graph
1.216 - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
1.217 for calculate maximum cardinality matching in general graph
1.218 @@ -396,8 +396,8 @@
1.219
1.220 */
1.221
1.222 -/**
1.223 -@defgroup lp_utils Tools for Lp and Mip solvers
1.224 +/**
1.225 +@defgroup lp_utils Tools for Lp and Mip solvers
1.226 @ingroup lp_group
1.227 \brief Helper tools to the Lp and Mip solvers.
1.228
1.229 @@ -414,7 +414,7 @@
1.230 */
1.231
1.232 /**
1.233 -@defgroup utils Tools and Utilities
1.234 +@defgroup utils Tools and Utilities
1.235 \brief Tools and utilities for programming in LEMON
1.236
1.237 Tools and utilities for programming in LEMON.
1.238 @@ -467,7 +467,7 @@
1.239 @defgroup io_group Input-Output
1.240 \brief Graph Input-Output methods
1.241
1.242 -This group describes the tools for importing and exporting graphs
1.243 +This group describes the tools for importing and exporting graphs
1.244 and graph related data. Now it supports the LEMON format, the
1.245 \c DIMACS format and the encapsulated postscript (EPS) format.
1.246 */
1.247 @@ -486,7 +486,7 @@
1.248 \brief General \c EPS drawer and graph exporter
1.249
1.250 This group describes general \c EPS drawing methods and special
1.251 -graph exporting tools.
1.252 +graph exporting tools.
1.253 */
1.254
1.255
1.256 @@ -498,7 +498,7 @@
1.257 classes implemented in LEMON.
1.258
1.259 The purpose of the classes in this group is fourfold.
1.260 -
1.261 +
1.262 - These classes contain the documentations of the concepts. In order
1.263 to avoid document multiplications, an implementation of a concept
1.264 simply refers to the corresponding concept class.
1.265 @@ -551,9 +551,9 @@
1.266 /**
1.267 @defgroup tools Standalone utility applications
1.268
1.269 -Some utility applications are listed here.
1.270 +Some utility applications are listed here.
1.271
1.272 The standard compilation procedure (<tt>./configure;make</tt>) will compile
1.273 -them, as well.
1.274 +them, as well.
1.275 */
1.276