COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/circulation.h

    r611 r581  
    3232  ///
    3333  /// Default traits class of Circulation class.
    34   ///
    35   /// \tparam GR Type of the digraph the algorithm runs on.
    36   /// \tparam LM The type of the lower bound map.
    37   /// \tparam UM The type of the upper bound (capacity) map.
    38   /// \tparam SM The type of the supply map.
     34  /// \tparam GR Digraph type.
     35  /// \tparam LM Lower bound capacity map type.
     36  /// \tparam UM Upper bound capacity map type.
     37  /// \tparam DM Delta map type.
    3938  template <typename GR, typename LM,
    40             typename UM, typename SM>
     39            typename UM, typename DM>
    4140  struct CirculationDefaultTraits {
    4241
    … …  
    4443    typedef GR Digraph;
    4544
    46     /// \brief The type of the lower bound map.
    47     ///
    48     /// The type of the map that stores the lower bounds on the arcs.
    49     /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    50     typedef LM LowerMap;
    51 
    52     /// \brief The type of the upper bound (capacity) map.
    53     ///
    54     /// The type of the map that stores the upper bounds (capacities)
    55     /// on the arcs.
    56     /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    57     typedef UM UpperMap;
    58 
    59     /// \brief The type of supply map.
    60     ///
    61     /// The type of the map that stores the signed supply values of the
    62     /// nodes.
    63     /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    64     typedef SM SupplyMap;
     45    /// \brief The type of the map that stores the circulation lower
     46    /// bound.
     47    ///
     48    /// The type of the map that stores the circulation lower bound.
     49    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
     50    typedef LM LCapMap;
     51
     52    /// \brief The type of the map that stores the circulation upper
     53    /// bound.
     54    ///
     55    /// The type of the map that stores the circulation upper bound.
     56    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
     57    typedef UM UCapMap;
     58
     59    /// \brief The type of the map that stores the lower bound for
     60    /// the supply of the nodes.
     61    ///
     62    /// The type of the map that stores the lower bound for the supply
     63    /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap"
     64    /// concept.
     65    typedef DM DeltaMap;
    6566
    6667    /// \brief The type of the flow values.
    67     typedef typename SupplyMap::Value Flow;
     68    typedef typename DeltaMap::Value Value;
    6869
    6970    /// \brief The type of the map that stores the flow values.
    7071    ///
    7172    /// The type of the map that stores the flow values.
    72     /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
    73     /// concept.
    74     typedef typename Digraph::template ArcMap<Flow> FlowMap;
     73    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     74    typedef typename Digraph::template ArcMap<Value> FlowMap;
    7575
    7676    /// \brief Instantiates a FlowMap.
    7777    ///
    7878    /// This function instantiates a \ref FlowMap.
    79     /// \param digraph The digraph for which we would like to define
     79    /// \param digraph The digraph, to which we would like to define
    8080    /// the flow map.
    8181    static FlowMap* createFlowMap(const Digraph& digraph) {
    … …  
    9494    ///
    9595    /// This function instantiates an \ref Elevator.
    96     /// \param digraph The digraph for which we would like to define
     96    /// \param digraph The digraph, to which we would like to define
    9797    /// the elevator.
    9898    /// \param max_level The maximum level of the elevator.
    … …  
    104104    ///
    105105    /// The tolerance used by the algorithm to handle inexact computation.
    106     typedef lemon::Tolerance<Flow> Tolerance;
     106    typedef lemon::Tolerance<Value> Tolerance;
    107107
    108108  };
    … …  
    112112
    113113     \ingroup max_flow
    114      This class implements a push-relabel algorithm for the \e network
    115      \e circulation problem.
     114     This class implements a push-relabel algorithm for the network
     115     circulation problem.
    116116     It is to find a feasible circulation when lower and upper bounds
    117      are given for the flow values on the arcs and lower bounds are
    118      given for the difference between the outgoing and incoming flow
    119      at the nodes.
     117     are given for the flow values on the arcs and lower bounds
     118     are given for the supply values of the nodes.
    120119
    121120     The exact formulation of this problem is the following.
    122121     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$
    125      holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$
    126      denotes the signed supply values of the nodes.
    127      If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
    128      supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
    129      \f$-sup(u)\f$ demand.
    130      A feasible circulation is an \f$f: A\rightarrow\mathbf{R}^+_0\f$
    131      solution of the following problem.
    132 
    133      \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)
    134      \geq sup(u) \quad \forall u\in V, \f]
    135      \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
    136      
    137      The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
    138      zero or negative in order to have a feasible solution (since the sum
    139      of the expressions on the left-hand side of the inequalities is zero).
    140      It means that the total demand must be greater or equal to the total
    141      supply and all the supplies have to be carried out from the supply nodes,
    142      but there could be demands that are not satisfied.
    143      If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
    144      constraints have to be satisfied with equality, i.e. all demands
    145      have to be satisfied and all supplies have to be used.
    146      
    147      If you need the opposite inequalities in the supply/demand constraints
    148      (i.e. the total demand is less than the total supply and all the demands
    149      have to be satisfied while there could be supplies that are not used),
    150      then you could easily transform the problem to the above form by reversing
    151      the direction of the arcs and taking the negative of the supply values
    152      (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
    153 
    154      Note that this algorithm also provides a feasible solution for the
    155      \ref min_cost_flow "minimum cost flow problem".
     122     \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$,
     123     \f$delta: V\rightarrow\mathbf{R}\f$. Find a feasible circulation
     124     \f$f: A\rightarrow\mathbf{R}^+_0\f$ so that
     125     \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a)
     126     \geq delta(v) \quad \forall v\in V, \f]
     127     \f[ lower(a)\leq f(a) \leq upper(a) \quad \forall a\in A. \f]
     128     \note \f$delta(v)\f$ specifies a lower bound for the supply of node
     129     \f$v\f$. It can be either positive or negative, however note that
     130     \f$\sum_{v\in V}delta(v)\f$ should be zero or negative in order to
     131     have a feasible solution.
     132
     133     \note A special case of this problem is when
     134     \f$\sum_{v\in V}delta(v) = 0\f$. Then the supply of each node \f$v\f$
     135     will be \e equal \e to \f$delta(v)\f$, if a circulation can be found.
     136     Thus a feasible solution for the
     137     \ref min_cost_flow "minimum cost flow" problem can be calculated
     138     in this way.
    156139
    157140     \tparam GR The type of the digraph the algorithm runs on.
    158      \tparam LM The type of the lower bound map. The default
     141     \tparam LM The type of the lower bound capacity map. The default
    159142     map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    160      \tparam UM The type of the upper bound (capacity) map.
    161      The default map type is \c LM.
    162      \tparam SM The type of the supply map. The default map type is
     143     \tparam UM The type of the upper bound capacity map. The default
     144     map type is \c LM.
     145     \tparam DM The type of the map that stores the lower bound
     146     for the supply of the nodes. The default map type is
    163147     \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
    164148  */
    … …  
    167151          typename LM,
    168152          typename UM,
    169           typename SM,
     153          typename DM,
    170154          typename TR >
    171155#else
    … …  
    173157          typename LM = typename GR::template ArcMap<int>,
    174158          typename UM = LM,
    175           typename SM = typename GR::template NodeMap<typename UM::Value>,
    176           typename TR = CirculationDefaultTraits<GR, LM, UM, SM> >
     159          typename DM = typename GR::template NodeMap<typename UM::Value>,
     160          typename TR = CirculationDefaultTraits<GR, LM, UM, DM> >
    177161#endif
    178162  class Circulation {
    … …  
    184168    typedef typename Traits::Digraph Digraph;
    185169    ///The type of the flow values.
    186     typedef typename Traits::Flow Flow;
    187 
    188     ///The type of the lower bound map.
    189     typedef typename Traits::LowerMap LowerMap;
    190     ///The type of the upper bound (capacity) map.
    191     typedef typename Traits::UpperMap UpperMap;
    192     ///The type of the supply map.
    193     typedef typename Traits::SupplyMap SupplyMap;
     170    typedef typename Traits::Value Value;
     171
     172    /// The type of the lower bound capacity map.
     173    typedef typename Traits::LCapMap LCapMap;
     174    /// The type of the upper bound capacity map.
     175    typedef typename Traits::UCapMap UCapMap;
     176    /// \brief The type of the map that stores the lower bound for
     177    /// the supply of the nodes.
     178    typedef typename Traits::DeltaMap DeltaMap;
    194179    ///The type of the flow map.
    195180    typedef typename Traits::FlowMap FlowMap;
    … …  
    207192    int _node_num;
    208193
    209     const LowerMap *_lo;
    210     const UpperMap *_up;
    211     const SupplyMap *_supply;
     194    const LCapMap *_lo;
     195    const UCapMap *_up;
     196    const DeltaMap *_delta;
    212197
    213198    FlowMap *_flow;
    … …  
    217202    bool _local_level;
    218203
    219     typedef typename Digraph::template NodeMap<Flow> ExcessMap;
     204    typedef typename Digraph::template NodeMap<Value> ExcessMap;
    220205    ExcessMap* _excess;
    221206
    … …  
    247232    template <typename T>
    248233    struct SetFlowMap
    249       : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
     234      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    250235                           SetFlowMapTraits<T> > {
    251       typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
     236      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    252237                          SetFlowMapTraits<T> > Create;
    253238    };
    … …  
    273258    template <typename T>
    274259    struct SetElevator
    275       : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
     260      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    276261                           SetElevatorTraits<T> > {
    277       typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
     262      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    278263                          SetElevatorTraits<T> > Create;
    279264    };
    … …  
    301286    template <typename T>
    302287    struct SetStandardElevator
    303       : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
     288      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    304289                       SetStandardElevatorTraits<T> > {
    305       typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
     290      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    306291                      SetStandardElevatorTraits<T> > Create;
    307292    };
    … …  
    315300  public:
    316301
    317     /// Constructor.
    318 
    319302    /// The constructor of the class.
    320     ///
    321     /// \param graph The digraph the algorithm runs on.
    322     /// \param lower The lower bounds for the flow values on the arcs.
    323     /// \param upper The upper bounds (capacities) for the flow values
    324     /// on the arcs.
    325     /// \param supply The signed supply values of the nodes.
    326     Circulation(const Digraph &graph, const LowerMap &lower,
    327                 const UpperMap &upper, const SupplyMap &supply)
    328       : _g(graph), _lo(&lower), _up(&upper), _supply(&supply),
    329         _flow(NULL), _local_flow(false), _level(NULL), _local_level(false),
    330         _excess(NULL) {}
     303
     304    /// The constructor of the class.
     305    /// \param g The digraph the algorithm runs on.
     306    /// \param lo The lower bound capacity of the arcs.
     307    /// \param up The upper bound capacity of the arcs.
     308    /// \param delta The lower bound for the supply of the nodes.
     309    Circulation(const Digraph &g,const LCapMap &lo,
     310                const UCapMap &up,const DeltaMap &delta)
     311      : _g(g), _node_num(),
     312        _lo(&lo),_up(&up),_delta(&delta),_flow(0),_local_flow(false),
     313        _level(0), _local_level(false), _excess(0), _el() {}
    331314
    332315    /// Destructor.
    … …  
    368351  public:
    369352
    370     /// Sets the lower bound map.
    371 
    372     /// Sets the lower bound map.
     353    /// Sets the lower bound capacity map.
     354
     355    /// Sets the lower bound capacity map.
    373356    /// \return <tt>(*this)</tt>
    374     Circulation& lowerMap(const LowerMap& map) {
     357    Circulation& lowerCapMap(const LCapMap& map) {
    375358      _lo = &map;
    376359      return *this;
    377360    }
    378361
    379     /// Sets the upper bound (capacity) map.
    380 
    381     /// Sets the upper bound (capacity) map.
     362    /// Sets the upper bound capacity map.
     363
     364    /// Sets the upper bound capacity map.
    382365    /// \return <tt>(*this)</tt>
    383     Circulation& upperMap(const LowerMap& map) {
     366    Circulation& upperCapMap(const LCapMap& map) {
    384367      _up = &map;
    385368      return *this;
    386369    }
    387370
    388     /// Sets the supply map.
    389 
    390     /// Sets the supply map.
     371    /// Sets the lower bound map for the supply of the nodes.
     372
     373    /// Sets the lower bound map for the supply of the nodes.
    391374    /// \return <tt>(*this)</tt>
    392     Circulation& supplyMap(const SupplyMap& map) {
    393       _supply = &map;
     375    Circulation& deltaMap(const DeltaMap& map) {
     376      _delta = &map;
    394377      return *this;
    395378    }
    … …  
    471454
    472455      for(NodeIt n(_g);n!=INVALID;++n) {
    473         (*_excess)[n] = (*_supply)[n];
     456        (*_excess)[n] = (*_delta)[n];
    474457      }
    475458
    … …  
    500483
    501484      for(NodeIt n(_g);n!=INVALID;++n) {
    502         (*_excess)[n] = (*_supply)[n];
     485        (*_excess)[n] = (*_delta)[n];
    503486      }
    504487
    … …  
    513496          (*_excess)[_g.source(e)] -= (*_lo)[e];
    514497        } else {
    515           Flow fc = -(*_excess)[_g.target(e)];
     498          Value fc = -(*_excess)[_g.target(e)];
    516499          _flow->set(e, fc);
    517500          (*_excess)[_g.target(e)] = 0;
    … …  
    546529        int actlevel=(*_level)[act];
    547530        int mlevel=_node_num;
    548         Flow exc=(*_excess)[act];
     531        Value exc=(*_excess)[act];
    549532
    550533        for(OutArcIt e(_g,act);e!=INVALID; ++e) {
    551534          Node v = _g.target(e);
    552           Flow fc=(*_up)[e]-(*_flow)[e];
     535          Value fc=(*_up)[e]-(*_flow)[e];
    553536          if(!_tol.positive(fc)) continue;
    554537          if((*_level)[v]<actlevel) {
    … …  
    574557        for(InArcIt e(_g,act);e!=INVALID; ++e) {
    575558          Node v = _g.source(e);
    576           Flow fc=(*_flow)[e]-(*_lo)[e];
     559          Value fc=(*_flow)[e]-(*_lo)[e];
    577560          if(!_tol.positive(fc)) continue;
    578561          if((*_level)[v]<actlevel) {
    … …  
    650633    /// \pre Either \ref run() or \ref init() must be called before
    651634    /// using this function.
    652     Flow flow(const Arc& arc) const {
     635    Value flow(const Arc& arc) const {
    653636      return (*_flow)[arc];
    654637    }
    … …  
    669652       Barrier is a set \e B of nodes for which
    670653
    671        \f[ \sum_{uv\in A: u\in B} upper(uv) -
    672            \sum_{uv\in A: v\in B} lower(uv) < \sum_{v\in B} sup(v) \f]
     654       \f[ \sum_{a\in\delta_{out}(B)} upper(a) -
     655           \sum_{a\in\delta_{in}(B)} lower(a) < \sum_{v\in B}delta(v) \f]
    673656
    674657       holds. The existence of a set with this property prooves that a
    … …  
    733716      for(NodeIt n(_g);n!=INVALID;++n)
    734717        {
    735           Flow dif=-(*_supply)[n];
     718          Value dif=-(*_delta)[n];
    736719          for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
    737720          for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
    … …  
    748731    bool checkBarrier() const
    749732    {
    750       Flow delta=0;
     733      Value delta=0;
    751734      for(NodeIt n(_g);n!=INVALID;++n)
    752735        if(barrier(n))
    753           delta-=(*_supply)[n];
     736          delta-=(*_delta)[n];
    754737      for(ArcIt e(_g);e!=INVALID;++e)
    755738        {
Note: See TracChangeset for help on using the changeset viewer.