1.1 --- a/doc/groups.dox Sun Nov 30 09:39:34 2008 +0000
1.2 +++ b/doc/groups.dox Sun Nov 30 21:53:24 2008 +0100
1.3 @@ -16,6 +16,8 @@
1.4 *
1.5 */
1.6
1.7 +namespace lemon {
1.8 +
1.9 /**
1.10 @defgroup datas Data Structures
1.11 This group describes the several data structures implemented in LEMON.
1.12 @@ -88,7 +90,10 @@
1.13 \brief Special graph-related maps.
1.14
1.15 This group describes maps that are specifically designed to assign
1.16 -values to the nodes and arcs of graphs.
1.17 +values to the nodes and arcs/edges of graphs.
1.18 +
1.19 +If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
1.20 +\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
1.21 */
1.22
1.23 /**
1.24 @@ -99,7 +104,7 @@
1.25 This group describes map adaptors that are used to create "implicit"
1.26 maps from other maps.
1.27
1.28 -Most of them are \ref lemon::concepts::ReadMap "read-only maps".
1.29 +Most of them are \ref concepts::ReadMap "read-only maps".
1.30 They can make arithmetic and logical operations between one or two maps
1.31 (negation, shifting, addition, multiplication, logical 'and', 'or',
1.32 'not' etc.) or e.g. convert a map to another one of different Value type.
1.33 @@ -201,8 +206,8 @@
1.34 @ingroup algs
1.35 \brief Common graph search algorithms.
1.36
1.37 -This group describes the common graph search algorithms like
1.38 -Breadth-First Search (BFS) and Depth-First Search (DFS).
1.39 +This group describes the common graph search algorithms, namely
1.40 +\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
1.41 */
1.42
1.43 /**
1.44 @@ -210,7 +215,20 @@
1.45 @ingroup algs
1.46 \brief Algorithms for finding shortest paths.
1.47
1.48 -This group describes the algorithms for finding shortest paths in graphs.
1.49 +This group describes the algorithms for finding shortest paths in digraphs.
1.50 +
1.51 + - \ref Dijkstra algorithm for finding shortest paths from a source node
1.52 + when all arc lengths are non-negative.
1.53 + - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
1.54 + from a source node when arc lenghts can be either positive or negative,
1.55 + but the digraph should not contain directed cycles with negative total
1.56 + length.
1.57 + - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
1.58 + for solving the \e all-pairs \e shortest \e paths \e problem when arc
1.59 + lenghts can be either positive or negative, but the digraph should
1.60 + not contain directed cycles with negative total length.
1.61 + - \ref Suurballe A successive shortest path algorithm for finding
1.62 + arc-disjoint paths between two nodes having minimum total length.
1.63 */
1.64
1.65 /**
1.66 @@ -221,27 +239,28 @@
1.67 This group describes the algorithms for finding maximum flows and
1.68 feasible circulations.
1.69
1.70 -The maximum flow problem is to find a flow between a single source and
1.71 -a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
1.72 -directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
1.73 -function and given \f$s, t \in V\f$ source and target node. The
1.74 -maximum flow is the \f$f_a\f$ solution of the next optimization problem:
1.75 +The \e maximum \e flow \e problem is to find a flow of maximum value between
1.76 +a single source and a single target. Formally, there is a \f$G=(V,A)\f$
1.77 +digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
1.78 +\f$s, t \in V\f$ source and target nodes.
1.79 +A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
1.80 +following optimization problem.
1.81
1.82 -\f[ 0 \le f_a \le c_a \f]
1.83 -\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
1.84 -\qquad \forall u \in V \setminus \{s,t\}\f]
1.85 -\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
1.86 +\f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]
1.87 +\f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)
1.88 + \qquad \forall v\in V\setminus\{s,t\} \f]
1.89 +\f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]
1.90
1.91 LEMON contains several algorithms for solving maximum flow problems:
1.92 -- \ref lemon::EdmondsKarp "Edmonds-Karp"
1.93 -- \ref lemon::Preflow "Goldberg's Preflow algorithm"
1.94 -- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
1.95 -- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
1.96 +- \ref EdmondsKarp Edmonds-Karp algorithm.
1.97 +- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
1.98 +- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
1.99 +- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
1.100
1.101 -In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
1.102 -fastest method to compute the maximum flow. All impelementations
1.103 -provides functions to query the minimum cut, which is the dual linear
1.104 -programming problem of the maximum flow.
1.105 +In most cases the \ref Preflow "Preflow" algorithm provides the
1.106 +fastest method for computing a maximum flow. All implementations
1.107 +provides functions to also query the minimum cut, which is the dual
1.108 +problem of the maximum flow.
1.109 */
1.110
1.111 /**
1.112 @@ -252,6 +271,33 @@
1.113
1.114 This group describes the algorithms for finding minimum cost flows and
1.115 circulations.
1.116 +
1.117 +The \e minimum \e cost \e flow \e problem is to find a feasible flow of
1.118 +minimum total cost from a set of supply nodes to a set of demand nodes
1.119 +in a network with capacity constraints and arc costs.
1.120 +Formally, let \f$G=(V,A)\f$ be a digraph,
1.121 +\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
1.122 +upper bounds for the flow values on the arcs,
1.123 +\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
1.124 +on the arcs, and
1.125 +\f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
1.126 +of the nodes.
1.127 +A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
1.128 +the following optimization problem.
1.129 +
1.130 +\f[ \min\sum_{a\in A} f(a) cost(a) \f]
1.131 +\f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =
1.132 + supply(v) \qquad \forall v\in V \f]
1.133 +\f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]
1.134 +
1.135 +LEMON contains several algorithms for solving minimum cost flow problems:
1.136 + - \ref CycleCanceling Cycle-canceling algorithms.
1.137 + - \ref CapacityScaling Successive shortest path algorithm with optional
1.138 + capacity scaling.
1.139 + - \ref CostScaling Push-relabel and augment-relabel algorithms based on
1.140 + cost scaling.
1.141 + - \ref NetworkSimplex Primal network simplex algorithm with various
1.142 + pivot strategies.
1.143 */
1.144
1.145 /**
1.146 @@ -262,26 +308,26 @@
1.147
1.148 This group describes the algorithms for finding minimum cut in graphs.
1.149
1.150 -The minimum cut problem is to find a non-empty and non-complete
1.151 -\f$X\f$ subset of the vertices with minimum overall capacity on
1.152 -outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
1.153 -\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
1.154 +The \e minimum \e cut \e problem is to find a non-empty and non-complete
1.155 +\f$X\f$ subset of the nodes with minimum overall capacity on
1.156 +outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
1.157 +\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
1.158 cut is the \f$X\f$ solution of the next optimization problem:
1.159
1.160 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
1.161 -\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
1.162 + \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
1.163
1.164 LEMON contains several algorithms related to minimum cut problems:
1.165
1.166 -- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
1.167 - in directed graphs
1.168 -- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
1.169 - calculate minimum cut in undirected graphs
1.170 -- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
1.171 - pairs minimum cut in undirected graphs
1.172 +- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
1.173 + in directed graphs.
1.174 +- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
1.175 + calculating minimum cut in undirected graphs.
1.176 +- \ref GomoryHuTree "Gomory-Hu tree computation" for calculating
1.177 + all-pairs minimum cut in undirected graphs.
1.178
1.179 If you want to find minimum cut just between two distinict nodes,
1.180 -please see the \ref max_flow "Maximum Flow page".
1.181 +see the \ref max_flow "maximum flow problem".
1.182 */
1.183
1.184 /**
1.185 @@ -320,30 +366,28 @@
1.186 There are several different algorithms for calculate matchings in
1.187 graphs. The matching problems in bipartite graphs are generally
1.188 easier than in general graphs. The goal of the matching optimization
1.189 -can be the finding maximum cardinality, maximum weight or minimum cost
1.190 +can be finding maximum cardinality, maximum weight or minimum cost
1.191 matching. The search can be constrained to find perfect or
1.192 maximum cardinality matching.
1.193
1.194 -LEMON contains the next algorithms:
1.195 -- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
1.196 - augmenting path algorithm for calculate maximum cardinality matching in
1.197 - bipartite graphs
1.198 -- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
1.199 - algorithm for calculate maximum cardinality matching in bipartite graphs
1.200 -- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
1.201 - Successive shortest path algorithm for calculate maximum weighted matching
1.202 - and maximum weighted bipartite matching in bipartite graph
1.203 -- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
1.204 - Successive shortest path algorithm for calculate minimum cost maximum
1.205 - matching in bipartite graph
1.206 -- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
1.207 - for calculate maximum cardinality matching in general graph
1.208 -- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
1.209 - shrinking algorithm for calculate maximum weighted matching in general
1.210 - graph
1.211 -- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
1.212 - Edmond's blossom shrinking algorithm for calculate maximum weighted
1.213 - perfect matching in general graph
1.214 +The matching algorithms implemented in LEMON:
1.215 +- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
1.216 + for calculating maximum cardinality matching in bipartite graphs.
1.217 +- \ref PrBipartiteMatching Push-relabel algorithm
1.218 + for calculating maximum cardinality matching in bipartite graphs.
1.219 +- \ref MaxWeightedBipartiteMatching
1.220 + Successive shortest path algorithm for calculating maximum weighted
1.221 + matching and maximum weighted bipartite matching in bipartite graphs.
1.222 +- \ref MinCostMaxBipartiteMatching
1.223 + Successive shortest path algorithm for calculating minimum cost maximum
1.224 + matching in bipartite graphs.
1.225 +- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
1.226 + maximum cardinality matching in general graphs.
1.227 +- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
1.228 + maximum weighted matching in general graphs.
1.229 +- \ref MaxWeightedPerfectMatching
1.230 + Edmond's blossom shrinking algorithm for calculating maximum weighted
1.231 + perfect matching in general graphs.
1.232
1.233 \image html bipartite_matching.png
1.234 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
1.235 @@ -355,7 +399,7 @@
1.236 \brief Algorithms for finding a minimum cost spanning tree in a graph.
1.237
1.238 This group describes the algorithms for finding a minimum cost spanning
1.239 -tree in a graph
1.240 +tree in a graph.
1.241 */
1.242
1.243 /**
1.244 @@ -546,7 +590,7 @@
1.245 /**
1.246 \anchor demoprograms
1.247
1.248 -@defgroup demos Demo programs
1.249 +@defgroup demos Demo Programs
1.250
1.251 Some demo programs are listed here. Their full source codes can be found in
1.252 the \c demo subdirectory of the source tree.
1.253 @@ -556,7 +600,7 @@
1.254 */
1.255
1.256 /**
1.257 -@defgroup tools Standalone utility applications
1.258 +@defgroup tools Standalone Utility Applications
1.259
1.260 Some utility applications are listed here.
1.261
1.262 @@ -564,3 +608,4 @@
1.263 them, as well.
1.264 */
1.265
1.266 +}