1.1 --- a/doc/groups.dox Thu May 07 02:05:12 2009 +0200
1.2 +++ b/doc/groups.dox Tue May 12 12:09:55 2009 +0100
1.3 @@ -138,16 +138,6 @@
1.4 */
1.5
1.6 /**
1.7 -@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
1.8 -@ingroup graphs
1.9 -\brief Graph types between real graphs and graph adaptors.
1.10 -
1.11 -This group contains some graph types between real graphs and graph adaptors.
1.12 -These classes wrap graphs to give new functionality as the adaptors do it.
1.13 -On the other hand they are not light-weight structures as the adaptors.
1.14 -*/
1.15 -
1.16 -/**
1.17 @defgroup maps Maps
1.18 @ingroup datas
1.19 \brief Map structures implemented in LEMON.
1.20 @@ -315,6 +305,7 @@
1.21 Tarjan for solving this problem. It also provides functions to query the
1.22 minimum cut, which is the dual problem of maximum flow.
1.23
1.24 +
1.25 \ref Circulation is a preflow push-relabel algorithm implemented directly
1.26 for finding feasible circulations, which is a somewhat different problem,
1.27 but it is strongly related to maximum flow.
1.28 @@ -322,86 +313,14 @@
1.29 */
1.30
1.31 /**
1.32 -@defgroup min_cost_flow Minimum Cost Flow Algorithms
1.33 +@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
1.34 @ingroup algs
1.35
1.36 \brief Algorithms for finding minimum cost flows and circulations.
1.37
1.38 This group contains the algorithms for finding minimum cost flows and
1.39 -circulations.
1.40 -
1.41 -The \e minimum \e cost \e flow \e problem is to find a feasible flow of
1.42 -minimum total cost from a set of supply nodes to a set of demand nodes
1.43 -in a network with capacity constraints (lower and upper bounds)
1.44 -and arc costs.
1.45 -Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$,
1.46 -\f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and
1.47 -upper bounds for the flow values on the arcs, for which
1.48 -\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
1.49 -\f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow
1.50 -on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
1.51 -signed supply values of the nodes.
1.52 -If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
1.53 -supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
1.54 -\f$-sup(u)\f$ demand.
1.55 -A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution
1.56 -of the following optimization problem.
1.57 -
1.58 -\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
1.59 -\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
1.60 - sup(u) \quad \forall u\in V \f]
1.61 -\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
1.62 -
1.63 -The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
1.64 -zero or negative in order to have a feasible solution (since the sum
1.65 -of the expressions on the left-hand side of the inequalities is zero).
1.66 -It means that the total demand must be greater or equal to the total
1.67 -supply and all the supplies have to be carried out from the supply nodes,
1.68 -but there could be demands that are not satisfied.
1.69 -If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
1.70 -constraints have to be satisfied with equality, i.e. all demands
1.71 -have to be satisfied and all supplies have to be used.
1.72 -
1.73 -If you need the opposite inequalities in the supply/demand constraints
1.74 -(i.e. the total demand is less than the total supply and all the demands
1.75 -have to be satisfied while there could be supplies that are not used),
1.76 -then you could easily transform the problem to the above form by reversing
1.77 -the direction of the arcs and taking the negative of the supply values
1.78 -(e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
1.79 -However \ref NetworkSimplex algorithm also supports this form directly
1.80 -for the sake of convenience.
1.81 -
1.82 -A feasible solution for this problem can be found using \ref Circulation.
1.83 -
1.84 -Note that the above formulation is actually more general than the usual
1.85 -definition of the minimum cost flow problem, in which strict equalities
1.86 -are required in the supply/demand contraints, i.e.
1.87 -
1.88 -\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
1.89 - sup(u) \quad \forall u\in V. \f]
1.90 -
1.91 -However if the sum of the supply values is zero, then these two problems
1.92 -are equivalent. So if you need the equality form, you have to ensure this
1.93 -additional contraint for the algorithms.
1.94 -
1.95 -The dual solution of the minimum cost flow problem is represented by node
1.96 -potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
1.97 -An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem
1.98 -is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
1.99 -node potentials the following \e complementary \e slackness optimality
1.100 -conditions hold.
1.101 -
1.102 - - For all \f$uv\in A\f$ arcs:
1.103 - - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
1.104 - - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
1.105 - - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
1.106 - - For all \f$u\in V\f$ nodes:
1.107 - - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
1.108 - then \f$\pi(u)=0\f$.
1.109 -
1.110 -Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
1.111 -\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
1.112 -\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
1.113 +circulations. For more information about this problem and its dual
1.114 +solution see \ref min_cost_flow "Minimum Cost Flow Problem".
1.115
1.116 \ref NetworkSimplex is an efficient implementation of the primal Network
1.117 Simplex algorithm for finding minimum cost flows. It also provides dual
1.118 @@ -479,10 +398,10 @@
1.119 /**
1.120 @defgroup spantree Minimum Spanning Tree Algorithms
1.121 @ingroup algs
1.122 -\brief Algorithms for finding a minimum cost spanning tree in a graph.
1.123 +\brief Algorithms for finding minimum cost spanning trees and arborescences.
1.124
1.125 -This group contains the algorithms for finding a minimum cost spanning
1.126 -tree in a graph.
1.127 +This group contains the algorithms for finding minimum cost spanning
1.128 +trees and arborescences.
1.129 */
1.130
1.131 /**