COIN-OR::LEMON - Graph Library

Changeset 669:28f58740b6f8 in lemon


Ignore:
Timestamp:
04/25/09 18:25:59 (16 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Support infinite bounds in Circulation + fixes (#270, #266)

  • Support infinite capacities.
  • Bug fix in upperMap().
  • Fixes and improvements in the documentation.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/circulation.h

    r658 r669  
    2222#include <lemon/tolerance.h>
    2323#include <lemon/elevator.h>
     24#include <limits>
    2425
    2526///\ingroup max_flow
     
    120121
    121122     The exact formulation of this problem is the following.
    122      Let \f$G=(V,A)\f$ be a digraph,
    123      \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$ denote the lower and
    124      upper bounds on the arcs, for which \f$0 \leq lower(uv) \leq upper(uv)\f$
     123     Let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$
     124     \f$upper: A\rightarrow\mathbf{R}\cup\{\infty\}\f$ denote the lower and
     125     upper bounds on the arcs, for which \f$lower(uv) \leq upper(uv)\f$
    125126     holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$
    126127     denotes the signed supply values of the nodes.
     
    128129     supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
    129130     \f$-sup(u)\f$ demand.
    130      A feasible circulation is an \f$f: A\rightarrow\mathbf{R}^+_0\f$
     131     A feasible circulation is an \f$f: A\rightarrow\mathbf{R}\f$
    131132     solution of the following problem.
    132133
     
    151152     the direction of the arcs and taking the negative of the supply values
    152153     (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
     154
     155     This algorithm either calculates a feasible circulation, or provides
     156     a \ref barrier() "barrier", which prooves that a feasible soultion
     157     cannot exist.
    153158
    154159     Note that this algorithm also provides a feasible solution for the
     
    338343  private:
    339344
     345    bool checkBoundMaps() {
     346      for (ArcIt e(_g);e!=INVALID;++e) {
     347        if (_tol.less((*_up)[e], (*_lo)[e])) return false;
     348      }
     349      return true;
     350    }
     351
    340352    void createStructures() {
    341353      _node_num = _el = countNodes(_g);
     
    381393    /// Sets the upper bound (capacity) map.
    382394    /// \return <tt>(*this)</tt>
    383     Circulation& upperMap(const LowerMap& map) {
     395    Circulation& upperMap(const UpperMap& map) {
    384396      _up = &map;
    385397      return *this;
     
    468480    void init()
    469481    {
     482      LEMON_DEBUG(checkBoundMaps(),
     483        "Upper bounds must be greater or equal to the lower bounds");
     484
    470485      createStructures();
    471486
     
    497512    void greedyInit()
    498513    {
     514      LEMON_DEBUG(checkBoundMaps(),
     515        "Upper bounds must be greater or equal to the lower bounds");
     516
    499517      createStructures();
    500518
     
    504522
    505523      for (ArcIt e(_g);e!=INVALID;++e) {
    506         if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) {
     524        if (!_tol.less(-(*_excess)[_g.target(e)], (*_up)[e])) {
    507525          _flow->set(e, (*_up)[e]);
    508526          (*_excess)[_g.target(e)] += (*_up)[e];
    509527          (*_excess)[_g.source(e)] -= (*_up)[e];
    510         } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) {
     528        } else if (_tol.less(-(*_excess)[_g.target(e)], (*_lo)[e])) {
    511529          _flow->set(e, (*_lo)[e]);
    512530          (*_excess)[_g.target(e)] += (*_lo)[e];
     
    749767    {
    750768      Flow delta=0;
     769      Flow inf_cap = std::numeric_limits<Flow>::has_infinity ?
     770        std::numeric_limits<Flow>::infinity() :
     771        std::numeric_limits<Flow>::max();
    751772      for(NodeIt n(_g);n!=INVALID;++n)
    752773        if(barrier(n))
     
    756777          Node s=_g.source(e);
    757778          Node t=_g.target(e);
    758           if(barrier(s)&&!barrier(t)) delta+=(*_up)[e];
     779          if(barrier(s)&&!barrier(t)) {
     780            if (_tol.less(inf_cap - (*_up)[e], delta)) return false;
     781            delta+=(*_up)[e];
     782          }
    759783          else if(barrier(t)&&!barrier(s)) delta-=(*_lo)[e];
    760784        }
Note: See TracChangeset for help on using the changeset viewer.