# Changes in /[686:72ac25ad276e:691:8d289c89d43e] in lemon

Ignore:
Files:
6 edited

Unmodified
Removed
• ## doc/groups.dox

 r658 in a network with capacity constraints (lower and upper bounds) and arc costs. Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$, \f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and upper bounds for the flow values on the arcs, for which \f$0 \leq lower(uv) \leq upper(uv)\f$ holds for all \f$uv\in A\f$. \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow on the arcs, and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the \f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$, \f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the signed supply values of the nodes. If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$ supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with \f$-sup(u)\f$ demand. A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}^+_0\f$ solution A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution of the following optimization problem. The dual solution of the minimum cost flow problem is represented by node potentials \f$\pi: V\rightarrow\mathbf{Z}\f$. An \f$f: A\rightarrow\mathbf{Z}^+_0\f$ feasible solution of the problem An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$ node potentials the following \e complementary \e slackness optimality - if \f\$lower(uv)
• ## lemon/circulation.h

 r669 typedef SM SupplyMap; /// \brief The type of the flow values. typedef typename SupplyMap::Value Flow; /// \brief The type of the flow and supply values. typedef typename SupplyMap::Value Value; /// \brief The type of the map that stores the flow values. /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" /// concept. typedef typename Digraph::template ArcMap FlowMap; typedef typename Digraph::template ArcMap FlowMap; /// \brief Instantiates a FlowMap. /// /// The tolerance used by the algorithm to handle inexact computation. typedef lemon::Tolerance Tolerance; typedef lemon::Tolerance Tolerance; }; ///The type of the digraph the algorithm runs on. typedef typename Traits::Digraph Digraph; ///The type of the flow values. typedef typename Traits::Flow Flow; ///The type of the flow and supply values. typedef typename Traits::Value Value; ///The type of the lower bound map. bool _local_level; typedef typename Digraph::template NodeMap ExcessMap; typedef typename Digraph::template NodeMap ExcessMap; ExcessMap* _excess; (*_excess)[_g.source(e)] -= (*_lo)[e]; } else { Flow fc = -(*_excess)[_g.target(e)]; Value fc = -(*_excess)[_g.target(e)]; _flow->set(e, fc); (*_excess)[_g.target(e)] = 0; int actlevel=(*_level)[act]; int mlevel=_node_num; Flow exc=(*_excess)[act]; Value exc=(*_excess)[act]; for(OutArcIt e(_g,act);e!=INVALID; ++e) { Node v = _g.target(e); Flow fc=(*_up)[e]-(*_flow)[e]; Value fc=(*_up)[e]-(*_flow)[e]; if(!_tol.positive(fc)) continue; if((*_level)[v]::has_infinity ? std::numeric_limits::infinity() : std::numeric_limits::max(); Value delta=0; Value inf_cap = std::numeric_limits::has_infinity ? std::numeric_limits::infinity() : std::numeric_limits::max(); for(NodeIt n(_g);n!=INVALID;++n) if(barrier(n))