lemon/circulation.h
changeset 610 dacc2cee2b4c
parent 492 9605e051942f
child 611 85cb3aa71cce
     1.1 --- a/lemon/circulation.h	Fri Apr 17 18:04:36 2009 +0200
     1.2 +++ b/lemon/circulation.h	Fri Apr 17 18:14:35 2009 +0200
     1.3 @@ -31,52 +31,52 @@
     1.4    /// \brief Default traits class of Circulation class.
     1.5    ///
     1.6    /// Default traits class of Circulation class.
     1.7 -  /// \tparam GR Digraph type.
     1.8 -  /// \tparam LM Lower bound capacity map type.
     1.9 -  /// \tparam UM Upper bound capacity map type.
    1.10 -  /// \tparam DM Delta map type.
    1.11 +  ///
    1.12 +  /// \tparam GR Type of the digraph the algorithm runs on.
    1.13 +  /// \tparam LM The type of the lower bound map.
    1.14 +  /// \tparam UM The type of the upper bound (capacity) map.
    1.15 +  /// \tparam SM The type of the supply map.
    1.16    template <typename GR, typename LM,
    1.17 -            typename UM, typename DM>
    1.18 +            typename UM, typename SM>
    1.19    struct CirculationDefaultTraits {
    1.20  
    1.21      /// \brief The type of the digraph the algorithm runs on.
    1.22      typedef GR Digraph;
    1.23  
    1.24 -    /// \brief The type of the map that stores the circulation lower
    1.25 -    /// bound.
    1.26 +    /// \brief The type of the lower bound map.
    1.27      ///
    1.28 -    /// The type of the map that stores the circulation lower bound.
    1.29 -    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    1.30 -    typedef LM LCapMap;
    1.31 +    /// The type of the map that stores the lower bounds on the arcs.
    1.32 +    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    1.33 +    typedef LM LowerMap;
    1.34  
    1.35 -    /// \brief The type of the map that stores the circulation upper
    1.36 -    /// bound.
    1.37 +    /// \brief The type of the upper bound (capacity) map.
    1.38      ///
    1.39 -    /// The type of the map that stores the circulation upper bound.
    1.40 -    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    1.41 -    typedef UM UCapMap;
    1.42 +    /// The type of the map that stores the upper bounds (capacities)
    1.43 +    /// on the arcs.
    1.44 +    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    1.45 +    typedef UM UpperMap;
    1.46  
    1.47 -    /// \brief The type of the map that stores the lower bound for
    1.48 -    /// the supply of the nodes.
    1.49 +    /// \brief The type of supply map.
    1.50      ///
    1.51 -    /// The type of the map that stores the lower bound for the supply
    1.52 -    /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap"
    1.53 -    /// concept.
    1.54 -    typedef DM DeltaMap;
    1.55 +    /// The type of the map that stores the signed supply values of the 
    1.56 +    /// nodes. 
    1.57 +    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    1.58 +    typedef SM SupplyMap;
    1.59  
    1.60      /// \brief The type of the flow values.
    1.61 -    typedef typename DeltaMap::Value Value;
    1.62 +    typedef typename SupplyMap::Value Flow;
    1.63  
    1.64      /// \brief The type of the map that stores the flow values.
    1.65      ///
    1.66      /// The type of the map that stores the flow values.
    1.67 -    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    1.68 -    typedef typename Digraph::template ArcMap<Value> FlowMap;
    1.69 +    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
    1.70 +    /// concept.
    1.71 +    typedef typename Digraph::template ArcMap<Flow> FlowMap;
    1.72  
    1.73      /// \brief Instantiates a FlowMap.
    1.74      ///
    1.75      /// This function instantiates a \ref FlowMap.
    1.76 -    /// \param digraph The digraph, to which we would like to define
    1.77 +    /// \param digraph The digraph for which we would like to define
    1.78      /// the flow map.
    1.79      static FlowMap* createFlowMap(const Digraph& digraph) {
    1.80        return new FlowMap(digraph);
    1.81 @@ -93,7 +93,7 @@
    1.82      /// \brief Instantiates an Elevator.
    1.83      ///
    1.84      /// This function instantiates an \ref Elevator.
    1.85 -    /// \param digraph The digraph, to which we would like to define
    1.86 +    /// \param digraph The digraph for which we would like to define
    1.87      /// the elevator.
    1.88      /// \param max_level The maximum level of the elevator.
    1.89      static Elevator* createElevator(const Digraph& digraph, int max_level) {
    1.90 @@ -103,7 +103,7 @@
    1.91      /// \brief The tolerance used by the algorithm
    1.92      ///
    1.93      /// The tolerance used by the algorithm to handle inexact computation.
    1.94 -    typedef lemon::Tolerance<Value> Tolerance;
    1.95 +    typedef lemon::Tolerance<Flow> Tolerance;
    1.96  
    1.97    };
    1.98  
    1.99 @@ -111,53 +111,69 @@
   1.100       \brief Push-relabel algorithm for the network circulation problem.
   1.101  
   1.102       \ingroup max_flow
   1.103 -     This class implements a push-relabel algorithm for the network
   1.104 -     circulation problem.
   1.105 +     This class implements a push-relabel algorithm for the \e network
   1.106 +     \e circulation problem.
   1.107       It is to find a feasible circulation when lower and upper bounds
   1.108 -     are given for the flow values on the arcs and lower bounds
   1.109 -     are given for the supply values of the nodes.
   1.110 +     are given for the flow values on the arcs and lower bounds are
   1.111 +     given for the difference between the outgoing and incoming flow
   1.112 +     at the nodes.
   1.113  
   1.114       The exact formulation of this problem is the following.
   1.115       Let \f$G=(V,A)\f$ be a digraph,
   1.116 -     \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$,
   1.117 -     \f$delta: V\rightarrow\mathbf{R}\f$. Find a feasible circulation
   1.118 -     \f$f: A\rightarrow\mathbf{R}^+_0\f$ so that
   1.119 -     \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a)
   1.120 -     \geq delta(v) \quad \forall v\in V, \f]
   1.121 -     \f[ lower(a)\leq f(a) \leq upper(a) \quad \forall a\in A. \f]
   1.122 -     \note \f$delta(v)\f$ specifies a lower bound for the supply of node
   1.123 -     \f$v\f$. It can be either positive or negative, however note that
   1.124 -     \f$\sum_{v\in V}delta(v)\f$ should be zero or negative in order to
   1.125 -     have a feasible solution.
   1.126 +     \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$ denote the lower and
   1.127 +     upper bounds on the arcs, for which \f$0 \leq lower(uv) \leq upper(uv)\f$
   1.128 +     holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$
   1.129 +     denotes the signed supply values of the nodes.
   1.130 +     If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
   1.131 +     supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
   1.132 +     \f$-sup(u)\f$ demand.
   1.133 +     A feasible circulation is an \f$f: A\rightarrow\mathbf{R}^+_0\f$
   1.134 +     solution of the following problem.
   1.135  
   1.136 -     \note A special case of this problem is when
   1.137 -     \f$\sum_{v\in V}delta(v) = 0\f$. Then the supply of each node \f$v\f$
   1.138 -     will be \e equal \e to \f$delta(v)\f$, if a circulation can be found.
   1.139 -     Thus a feasible solution for the
   1.140 -     \ref min_cost_flow "minimum cost flow" problem can be calculated
   1.141 -     in this way.
   1.142 +     \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)
   1.143 +     \geq sup(u) \quad \forall u\in V, \f]
   1.144 +     \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
   1.145 +     
   1.146 +     The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
   1.147 +     zero or negative in order to have a feasible solution (since the sum
   1.148 +     of the expressions on the left-hand side of the inequalities is zero).
   1.149 +     It means that the total demand must be greater or equal to the total
   1.150 +     supply and all the supplies have to be carried out from the supply nodes,
   1.151 +     but there could be demands that are not satisfied.
   1.152 +     If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
   1.153 +     constraints have to be satisfied with equality, i.e. all demands
   1.154 +     have to be satisfied and all supplies have to be used.
   1.155 +     
   1.156 +     If you need the opposite inequalities in the supply/demand constraints
   1.157 +     (i.e. the total demand is less than the total supply and all the demands
   1.158 +     have to be satisfied while there could be supplies that are not used),
   1.159 +     then you could easily transform the problem to the above form by reversing
   1.160 +     the direction of the arcs and taking the negative of the supply values
   1.161 +     (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
   1.162 +
   1.163 +     Note that this algorithm also provides a feasible solution for the
   1.164 +     \ref min_cost_flow "minimum cost flow problem".
   1.165  
   1.166       \tparam GR The type of the digraph the algorithm runs on.
   1.167 -     \tparam LM The type of the lower bound capacity map. The default
   1.168 +     \tparam LM The type of the lower bound map. The default
   1.169       map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
   1.170 -     \tparam UM The type of the upper bound capacity map. The default
   1.171 -     map type is \c LM.
   1.172 -     \tparam DM The type of the map that stores the lower bound
   1.173 -     for the supply of the nodes. The default map type is
   1.174 +     \tparam UM The type of the upper bound (capacity) map.
   1.175 +     The default map type is \c LM.
   1.176 +     \tparam SM The type of the supply map. The default map type is
   1.177       \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
   1.178    */
   1.179  #ifdef DOXYGEN
   1.180  template< typename GR,
   1.181            typename LM,
   1.182            typename UM,
   1.183 -          typename DM,
   1.184 +          typename SM,
   1.185            typename TR >
   1.186  #else
   1.187  template< typename GR,
   1.188            typename LM = typename GR::template ArcMap<int>,
   1.189            typename UM = LM,
   1.190 -          typename DM = typename GR::template NodeMap<typename UM::Value>,
   1.191 -          typename TR = CirculationDefaultTraits<GR, LM, UM, DM> >
   1.192 +          typename SM = typename GR::template NodeMap<typename UM::Value>,
   1.193 +          typename TR = CirculationDefaultTraits<GR, LM, UM, SM> >
   1.194  #endif
   1.195    class Circulation {
   1.196    public:
   1.197 @@ -167,15 +183,14 @@
   1.198      ///The type of the digraph the algorithm runs on.
   1.199      typedef typename Traits::Digraph Digraph;
   1.200      ///The type of the flow values.
   1.201 -    typedef typename Traits::Value Value;
   1.202 +    typedef typename Traits::Flow Flow;
   1.203  
   1.204 -    /// The type of the lower bound capacity map.
   1.205 -    typedef typename Traits::LCapMap LCapMap;
   1.206 -    /// The type of the upper bound capacity map.
   1.207 -    typedef typename Traits::UCapMap UCapMap;
   1.208 -    /// \brief The type of the map that stores the lower bound for
   1.209 -    /// the supply of the nodes.
   1.210 -    typedef typename Traits::DeltaMap DeltaMap;
   1.211 +    ///The type of the lower bound map.
   1.212 +    typedef typename Traits::LowerMap LowerMap;
   1.213 +    ///The type of the upper bound (capacity) map.
   1.214 +    typedef typename Traits::UpperMap UpperMap;
   1.215 +    ///The type of the supply map.
   1.216 +    typedef typename Traits::SupplyMap SupplyMap;
   1.217      ///The type of the flow map.
   1.218      typedef typename Traits::FlowMap FlowMap;
   1.219  
   1.220 @@ -191,9 +206,9 @@
   1.221      const Digraph &_g;
   1.222      int _node_num;
   1.223  
   1.224 -    const LCapMap *_lo;
   1.225 -    const UCapMap *_up;
   1.226 -    const DeltaMap *_delta;
   1.227 +    const LowerMap *_lo;
   1.228 +    const UpperMap *_up;
   1.229 +    const SupplyMap *_supply;
   1.230  
   1.231      FlowMap *_flow;
   1.232      bool _local_flow;
   1.233 @@ -201,7 +216,7 @@
   1.234      Elevator* _level;
   1.235      bool _local_level;
   1.236  
   1.237 -    typedef typename Digraph::template NodeMap<Value> ExcessMap;
   1.238 +    typedef typename Digraph::template NodeMap<Flow> ExcessMap;
   1.239      ExcessMap* _excess;
   1.240  
   1.241      Tolerance _tol;
   1.242 @@ -231,9 +246,9 @@
   1.243      /// type.
   1.244      template <typename _FlowMap>
   1.245      struct SetFlowMap
   1.246 -      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
   1.247 +      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
   1.248                             SetFlowMapTraits<_FlowMap> > {
   1.249 -      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
   1.250 +      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
   1.251                            SetFlowMapTraits<_FlowMap> > Create;
   1.252      };
   1.253  
   1.254 @@ -257,9 +272,9 @@
   1.255      /// \sa SetStandardElevator
   1.256      template <typename _Elevator>
   1.257      struct SetElevator
   1.258 -      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
   1.259 +      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
   1.260                             SetElevatorTraits<_Elevator> > {
   1.261 -      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
   1.262 +      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
   1.263                            SetElevatorTraits<_Elevator> > Create;
   1.264      };
   1.265  
   1.266 @@ -285,9 +300,9 @@
   1.267      /// \sa SetElevator
   1.268      template <typename _Elevator>
   1.269      struct SetStandardElevator
   1.270 -      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
   1.271 +      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
   1.272                         SetStandardElevatorTraits<_Elevator> > {
   1.273 -      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
   1.274 +      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
   1.275                        SetStandardElevatorTraits<_Elevator> > Create;
   1.276      };
   1.277  
   1.278 @@ -299,18 +314,20 @@
   1.279  
   1.280    public:
   1.281  
   1.282 -    /// The constructor of the class.
   1.283 +    /// Constructor.
   1.284  
   1.285      /// The constructor of the class.
   1.286 -    /// \param g The digraph the algorithm runs on.
   1.287 -    /// \param lo The lower bound capacity of the arcs.
   1.288 -    /// \param up The upper bound capacity of the arcs.
   1.289 -    /// \param delta The lower bound for the supply of the nodes.
   1.290 -    Circulation(const Digraph &g,const LCapMap &lo,
   1.291 -                const UCapMap &up,const DeltaMap &delta)
   1.292 -      : _g(g), _node_num(),
   1.293 -        _lo(&lo),_up(&up),_delta(&delta),_flow(0),_local_flow(false),
   1.294 -        _level(0), _local_level(false), _excess(0), _el() {}
   1.295 +    ///
   1.296 +    /// \param graph The digraph the algorithm runs on.
   1.297 +    /// \param lower The lower bounds for the flow values on the arcs.
   1.298 +    /// \param upper The upper bounds (capacities) for the flow values 
   1.299 +    /// on the arcs.
   1.300 +    /// \param supply The signed supply values of the nodes.
   1.301 +    Circulation(const Digraph &graph, const LowerMap &lower,
   1.302 +                const UpperMap &upper, const SupplyMap &supply)
   1.303 +      : _g(graph), _lo(&lower), _up(&upper), _supply(&supply),
   1.304 +        _flow(NULL), _local_flow(false), _level(NULL), _local_level(false),
   1.305 +        _excess(NULL) {}
   1.306  
   1.307      /// Destructor.
   1.308      ~Circulation() {
   1.309 @@ -350,30 +367,30 @@
   1.310  
   1.311    public:
   1.312  
   1.313 -    /// Sets the lower bound capacity map.
   1.314 +    /// Sets the lower bound map.
   1.315  
   1.316 -    /// Sets the lower bound capacity map.
   1.317 +    /// Sets the lower bound map.
   1.318      /// \return <tt>(*this)</tt>
   1.319 -    Circulation& lowerCapMap(const LCapMap& map) {
   1.320 +    Circulation& lowerMap(const LowerMap& map) {
   1.321        _lo = &map;
   1.322        return *this;
   1.323      }
   1.324  
   1.325 -    /// Sets the upper bound capacity map.
   1.326 +    /// Sets the upper bound (capacity) map.
   1.327  
   1.328 -    /// Sets the upper bound capacity map.
   1.329 +    /// Sets the upper bound (capacity) map.
   1.330      /// \return <tt>(*this)</tt>
   1.331 -    Circulation& upperCapMap(const LCapMap& map) {
   1.332 +    Circulation& upperMap(const LowerMap& map) {
   1.333        _up = &map;
   1.334        return *this;
   1.335      }
   1.336  
   1.337 -    /// Sets the lower bound map for the supply of the nodes.
   1.338 +    /// Sets the supply map.
   1.339  
   1.340 -    /// Sets the lower bound map for the supply of the nodes.
   1.341 +    /// Sets the supply map.
   1.342      /// \return <tt>(*this)</tt>
   1.343 -    Circulation& deltaMap(const DeltaMap& map) {
   1.344 -      _delta = &map;
   1.345 +    Circulation& supplyMap(const SupplyMap& map) {
   1.346 +      _supply = &map;
   1.347        return *this;
   1.348      }
   1.349  
   1.350 @@ -453,7 +470,7 @@
   1.351        createStructures();
   1.352  
   1.353        for(NodeIt n(_g);n!=INVALID;++n) {
   1.354 -        _excess->set(n, (*_delta)[n]);
   1.355 +        _excess->set(n, (*_supply)[n]);
   1.356        }
   1.357  
   1.358        for (ArcIt e(_g);e!=INVALID;++e) {
   1.359 @@ -482,7 +499,7 @@
   1.360        createStructures();
   1.361  
   1.362        for(NodeIt n(_g);n!=INVALID;++n) {
   1.363 -        _excess->set(n, (*_delta)[n]);
   1.364 +        _excess->set(n, (*_supply)[n]);
   1.365        }
   1.366  
   1.367        for (ArcIt e(_g);e!=INVALID;++e) {
   1.368 @@ -495,7 +512,7 @@
   1.369            _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_lo)[e]);
   1.370            _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_lo)[e]);
   1.371          } else {
   1.372 -          Value fc = -(*_excess)[_g.target(e)];
   1.373 +          Flow fc = -(*_excess)[_g.target(e)];
   1.374            _flow->set(e, fc);
   1.375            _excess->set(_g.target(e), 0);
   1.376            _excess->set(_g.source(e), (*_excess)[_g.source(e)] - fc);
   1.377 @@ -528,11 +545,11 @@
   1.378        while((act=_level->highestActive())!=INVALID) {
   1.379          int actlevel=(*_level)[act];
   1.380          int mlevel=_node_num;
   1.381 -        Value exc=(*_excess)[act];
   1.382 +        Flow exc=(*_excess)[act];
   1.383  
   1.384          for(OutArcIt e(_g,act);e!=INVALID; ++e) {
   1.385            Node v = _g.target(e);
   1.386 -          Value fc=(*_up)[e]-(*_flow)[e];
   1.387 +          Flow fc=(*_up)[e]-(*_flow)[e];
   1.388            if(!_tol.positive(fc)) continue;
   1.389            if((*_level)[v]<actlevel) {
   1.390              if(!_tol.less(fc, exc)) {
   1.391 @@ -556,7 +573,7 @@
   1.392          }
   1.393          for(InArcIt e(_g,act);e!=INVALID; ++e) {
   1.394            Node v = _g.source(e);
   1.395 -          Value fc=(*_flow)[e]-(*_lo)[e];
   1.396 +          Flow fc=(*_flow)[e]-(*_lo)[e];
   1.397            if(!_tol.positive(fc)) continue;
   1.398            if((*_level)[v]<actlevel) {
   1.399              if(!_tol.less(fc, exc)) {
   1.400 @@ -632,7 +649,7 @@
   1.401      ///
   1.402      /// \pre Either \ref run() or \ref init() must be called before
   1.403      /// using this function.
   1.404 -    Value flow(const Arc& arc) const {
   1.405 +    Flow flow(const Arc& arc) const {
   1.406        return (*_flow)[arc];
   1.407      }
   1.408  
   1.409 @@ -651,8 +668,8 @@
   1.410  
   1.411         Barrier is a set \e B of nodes for which
   1.412  
   1.413 -       \f[ \sum_{a\in\delta_{out}(B)} upper(a) -
   1.414 -           \sum_{a\in\delta_{in}(B)} lower(a) < \sum_{v\in B}delta(v) \f]
   1.415 +       \f[ \sum_{uv\in A: u\in B} upper(uv) -
   1.416 +           \sum_{uv\in A: v\in B} lower(uv) < \sum_{v\in B} sup(v) \f]
   1.417  
   1.418         holds. The existence of a set with this property prooves that a
   1.419         feasible circualtion cannot exist.
   1.420 @@ -715,7 +732,7 @@
   1.421          if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false;
   1.422        for(NodeIt n(_g);n!=INVALID;++n)
   1.423          {
   1.424 -          Value dif=-(*_delta)[n];
   1.425 +          Flow dif=-(*_supply)[n];
   1.426            for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
   1.427            for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
   1.428            if(_tol.negative(dif)) return false;
   1.429 @@ -730,10 +747,10 @@
   1.430      ///\sa barrierMap()
   1.431      bool checkBarrier() const
   1.432      {
   1.433 -      Value delta=0;
   1.434 +      Flow delta=0;
   1.435        for(NodeIt n(_g);n!=INVALID;++n)
   1.436          if(barrier(n))
   1.437 -          delta-=(*_delta)[n];
   1.438 +          delta-=(*_supply)[n];
   1.439        for(ArcIt e(_g);e!=INVALID;++e)
   1.440          {
   1.441            Node s=_g.source(e);