doc/groups.dox
branch1.1
changeset 714 c6f725eff737
parent 644 189760a7cdd0
parent 661 8b0df68370a4
child 761 f1398882a928
equal deleted inserted replaced
27:b6e4f7d1e3a3 31:6c6a7b2f441f
   136 }
   136 }
   137 \endcode
   137 \endcode
   138 */
   138 */
   139 
   139 
   140 /**
   140 /**
   141 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs
       
   142 @ingroup graphs
       
   143 \brief Graph types between real graphs and graph adaptors.
       
   144 
       
   145 This group contains some graph types between real graphs and graph adaptors.
       
   146 These classes wrap graphs to give new functionality as the adaptors do it.
       
   147 On the other hand they are not light-weight structures as the adaptors.
       
   148 */
       
   149 
       
   150 /**
       
   151 @defgroup maps Maps
   141 @defgroup maps Maps
   152 @ingroup datas
   142 @ingroup datas
   153 \brief Map structures implemented in LEMON.
   143 \brief Map structures implemented in LEMON.
   154 
   144 
   155 This group contains the map structures implemented in LEMON.
   145 This group contains the map structures implemented in LEMON.
   313 
   303 
   314 \ref Preflow implements the preflow push-relabel algorithm of Goldberg and
   304 \ref Preflow implements the preflow push-relabel algorithm of Goldberg and
   315 Tarjan for solving this problem. It also provides functions to query the
   305 Tarjan for solving this problem. It also provides functions to query the
   316 minimum cut, which is the dual problem of maximum flow.
   306 minimum cut, which is the dual problem of maximum flow.
   317 
   307 
       
   308 
   318 \ref Circulation is a preflow push-relabel algorithm implemented directly 
   309 \ref Circulation is a preflow push-relabel algorithm implemented directly 
   319 for finding feasible circulations, which is a somewhat different problem,
   310 for finding feasible circulations, which is a somewhat different problem,
   320 but it is strongly related to maximum flow.
   311 but it is strongly related to maximum flow.
   321 For more information, see \ref Circulation.
   312 For more information, see \ref Circulation.
   322 */
   313 */
   323 
   314 
   324 /**
   315 /**
   325 @defgroup min_cost_flow Minimum Cost Flow Algorithms
   316 @defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
   326 @ingroup algs
   317 @ingroup algs
   327 
   318 
   328 \brief Algorithms for finding minimum cost flows and circulations.
   319 \brief Algorithms for finding minimum cost flows and circulations.
   329 
   320 
   330 This group contains the algorithms for finding minimum cost flows and
   321 This group contains the algorithms for finding minimum cost flows and
   331 circulations.
   322 circulations. For more information about this problem and its dual
   332 
   323 solution see \ref min_cost_flow "Minimum Cost Flow Problem".
   333 The \e minimum \e cost \e flow \e problem is to find a feasible flow of
       
   334 minimum total cost from a set of supply nodes to a set of demand nodes
       
   335 in a network with capacity constraints (lower and upper bounds)
       
   336 and arc costs.
       
   337 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$,
       
   338 \f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and
       
   339 upper bounds for the flow values on the arcs, for which
       
   340 \f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
       
   341 \f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow
       
   342 on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
       
   343 signed supply values of the nodes.
       
   344 If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
       
   345 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
       
   346 \f$-sup(u)\f$ demand.
       
   347 A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution
       
   348 of the following optimization problem.
       
   349 
       
   350 \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
       
   351 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
       
   352     sup(u) \quad \forall u\in V \f]
       
   353 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
       
   354 
       
   355 The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
       
   356 zero or negative in order to have a feasible solution (since the sum
       
   357 of the expressions on the left-hand side of the inequalities is zero).
       
   358 It means that the total demand must be greater or equal to the total
       
   359 supply and all the supplies have to be carried out from the supply nodes,
       
   360 but there could be demands that are not satisfied.
       
   361 If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
       
   362 constraints have to be satisfied with equality, i.e. all demands
       
   363 have to be satisfied and all supplies have to be used.
       
   364 
       
   365 If you need the opposite inequalities in the supply/demand constraints
       
   366 (i.e. the total demand is less than the total supply and all the demands
       
   367 have to be satisfied while there could be supplies that are not used),
       
   368 then you could easily transform the problem to the above form by reversing
       
   369 the direction of the arcs and taking the negative of the supply values
       
   370 (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
       
   371 However \ref NetworkSimplex algorithm also supports this form directly
       
   372 for the sake of convenience.
       
   373 
       
   374 A feasible solution for this problem can be found using \ref Circulation.
       
   375 
       
   376 Note that the above formulation is actually more general than the usual
       
   377 definition of the minimum cost flow problem, in which strict equalities
       
   378 are required in the supply/demand contraints, i.e.
       
   379 
       
   380 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
       
   381     sup(u) \quad \forall u\in V. \f]
       
   382 
       
   383 However if the sum of the supply values is zero, then these two problems
       
   384 are equivalent. So if you need the equality form, you have to ensure this
       
   385 additional contraint for the algorithms.
       
   386 
       
   387 The dual solution of the minimum cost flow problem is represented by node 
       
   388 potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
       
   389 An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem
       
   390 is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
       
   391 node potentials the following \e complementary \e slackness optimality
       
   392 conditions hold.
       
   393 
       
   394  - For all \f$uv\in A\f$ arcs:
       
   395    - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
       
   396    - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
       
   397    - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
       
   398  - For all \f$u\in V\f$ nodes:
       
   399    - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
       
   400      then \f$\pi(u)=0\f$.
       
   401  
       
   402 Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
       
   403 \f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
       
   404 \f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
       
   405 
   324 
   406 \ref NetworkSimplex is an efficient implementation of the primal Network
   325 \ref NetworkSimplex is an efficient implementation of the primal Network
   407 Simplex algorithm for finding minimum cost flows. It also provides dual
   326 Simplex algorithm for finding minimum cost flows. It also provides dual
   408 solution (node potentials), if an optimal flow is found.
   327 solution (node potentials), if an optimal flow is found.
   409 */
   328 */
   477 */
   396 */
   478 
   397 
   479 /**
   398 /**
   480 @defgroup spantree Minimum Spanning Tree Algorithms
   399 @defgroup spantree Minimum Spanning Tree Algorithms
   481 @ingroup algs
   400 @ingroup algs
   482 \brief Algorithms for finding a minimum cost spanning tree in a graph.
   401 \brief Algorithms for finding minimum cost spanning trees and arborescences.
   483 
   402 
   484 This group contains the algorithms for finding a minimum cost spanning
   403 This group contains the algorithms for finding minimum cost spanning
   485 tree in a graph.
   404 trees and arborescences.
   486 */
   405 */
   487 
   406 
   488 /**
   407 /**
   489 @defgroup auxalg Auxiliary Algorithms
   408 @defgroup auxalg Auxiliary Algorithms
   490 @ingroup algs
   409 @ingroup algs