COIN-OR::LEMON - Graph Library

Changeset 657:dacc2cee2b4c in lemon for lemon/circulation.h


Ignore:
Timestamp:
04/17/09 18:14:35 (11 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Slightly modify the interface of Circulation and Preflow (#266)
in order to synchronize them to the interface of NetworkSimplex?.

Circulation:

  • The "delta" notation is replaced by "supply".
  • lowerCapMap(), upperCapMap() are renamed to lowerMap() and upperMap().
  • Value is renamed to Flow.

Preflow:

  • Value is renamed to Flow.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/circulation.h

    r525 r657  
    3232  ///
    3333  /// Default traits class of Circulation class.
    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.
     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.
    3839  template <typename GR, typename LM,
    39             typename UM, typename DM>
     40            typename UM, typename SM>
    4041  struct CirculationDefaultTraits {
    4142
     
    4344    typedef GR Digraph;
    4445
    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"
     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;
     65
     66    /// \brief The type of the flow values.
     67    typedef typename SupplyMap::Value Flow;
     68
     69    /// \brief The type of the map that stores the flow values.
     70    ///
     71    /// The type of the map that stores the flow values.
     72    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
    6473    /// concept.
    65     typedef DM DeltaMap;
    66 
    67     /// \brief The type of the flow values.
    68     typedef typename DeltaMap::Value Value;
    69 
    70     /// \brief The type of the map that stores the flow values.
    71     ///
    72     /// The type of the map that stores the flow values.
    73     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    74     typedef typename Digraph::template ArcMap<Value> FlowMap;
     74    typedef typename Digraph::template ArcMap<Flow> FlowMap;
    7575
    7676    /// \brief Instantiates a FlowMap.
    7777    ///
    7878    /// This function instantiates a \ref FlowMap.
    79     /// \param digraph The digraph, to which we would like to define
     79    /// \param digraph The digraph for 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, to which we would like to define
     96    /// \param digraph The digraph for 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<Value> Tolerance;
     106    typedef lemon::Tolerance<Flow> Tolerance;
    107107
    108108  };
     
    112112
    113113     \ingroup max_flow
    114      This class implements a push-relabel algorithm for the network
    115      circulation problem.
     114     This class implements a push-relabel algorithm for the \e network
     115     \e 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
    118      are given for the supply values of the nodes.
     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.
    119120
    120121     The exact formulation of this problem is the following.
    121122     Let \f$G=(V,A)\f$ be a digraph,
    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.
     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".
    139156
    140157     \tparam GR The type of the digraph the algorithm runs on.
    141      \tparam LM The type of the lower bound capacity map. The default
     158     \tparam LM The type of the lower bound map. The default
    142159     map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    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
     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
    147163     \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
    148164  */
     
    151167          typename LM,
    152168          typename UM,
    153           typename DM,
     169          typename SM,
    154170          typename TR >
    155171#else
     
    157173          typename LM = typename GR::template ArcMap<int>,
    158174          typename UM = LM,
    159           typename DM = typename GR::template NodeMap<typename UM::Value>,
    160           typename TR = CirculationDefaultTraits<GR, LM, UM, DM> >
     175          typename SM = typename GR::template NodeMap<typename UM::Value>,
     176          typename TR = CirculationDefaultTraits<GR, LM, UM, SM> >
    161177#endif
    162178  class Circulation {
     
    168184    typedef typename Traits::Digraph Digraph;
    169185    ///The type of the flow values.
    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;
     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;
    179194    ///The type of the flow map.
    180195    typedef typename Traits::FlowMap FlowMap;
     
    192207    int _node_num;
    193208
    194     const LCapMap *_lo;
    195     const UCapMap *_up;
    196     const DeltaMap *_delta;
     209    const LowerMap *_lo;
     210    const UpperMap *_up;
     211    const SupplyMap *_supply;
    197212
    198213    FlowMap *_flow;
     
    202217    bool _local_level;
    203218
    204     typedef typename Digraph::template NodeMap<Value> ExcessMap;
     219    typedef typename Digraph::template NodeMap<Flow> ExcessMap;
    205220    ExcessMap* _excess;
    206221
     
    232247    template <typename _FlowMap>
    233248    struct SetFlowMap
    234       : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
     249      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    235250                           SetFlowMapTraits<_FlowMap> > {
    236       typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
     251      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    237252                          SetFlowMapTraits<_FlowMap> > Create;
    238253    };
     
    258273    template <typename _Elevator>
    259274    struct SetElevator
    260       : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
     275      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    261276                           SetElevatorTraits<_Elevator> > {
    262       typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
     277      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    263278                          SetElevatorTraits<_Elevator> > Create;
    264279    };
     
    286301    template <typename _Elevator>
    287302    struct SetStandardElevator
    288       : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
     303      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    289304                       SetStandardElevatorTraits<_Elevator> > {
    290       typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
     305      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    291306                      SetStandardElevatorTraits<_Elevator> > Create;
    292307    };
     
    300315  public:
    301316
     317    /// Constructor.
     318
    302319    /// The constructor of the class.
    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() {}
     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) {}
    314331
    315332    /// Destructor.
     
    351368  public:
    352369
    353     /// Sets the lower bound capacity map.
    354 
    355     /// Sets the lower bound capacity map.
     370    /// Sets the lower bound map.
     371
     372    /// Sets the lower bound map.
    356373    /// \return <tt>(*this)</tt>
    357     Circulation& lowerCapMap(const LCapMap& map) {
     374    Circulation& lowerMap(const LowerMap& map) {
    358375      _lo = &map;
    359376      return *this;
    360377    }
    361378
    362     /// Sets the upper bound capacity map.
    363 
    364     /// Sets the upper bound capacity map.
     379    /// Sets the upper bound (capacity) map.
     380
     381    /// Sets the upper bound (capacity) map.
    365382    /// \return <tt>(*this)</tt>
    366     Circulation& upperCapMap(const LCapMap& map) {
     383    Circulation& upperMap(const LowerMap& map) {
    367384      _up = &map;
    368385      return *this;
    369386    }
    370387
    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.
     388    /// Sets the supply map.
     389
     390    /// Sets the supply map.
    374391    /// \return <tt>(*this)</tt>
    375     Circulation& deltaMap(const DeltaMap& map) {
    376       _delta = &map;
     392    Circulation& supplyMap(const SupplyMap& map) {
     393      _supply = &map;
    377394      return *this;
    378395    }
     
    454471
    455472      for(NodeIt n(_g);n!=INVALID;++n) {
    456         _excess->set(n, (*_delta)[n]);
     473        _excess->set(n, (*_supply)[n]);
    457474      }
    458475
     
    483500
    484501      for(NodeIt n(_g);n!=INVALID;++n) {
    485         _excess->set(n, (*_delta)[n]);
     502        _excess->set(n, (*_supply)[n]);
    486503      }
    487504
     
    496513          _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_lo)[e]);
    497514        } else {
    498           Value fc = -(*_excess)[_g.target(e)];
     515          Flow fc = -(*_excess)[_g.target(e)];
    499516          _flow->set(e, fc);
    500517          _excess->set(_g.target(e), 0);
     
    529546        int actlevel=(*_level)[act];
    530547        int mlevel=_node_num;
    531         Value exc=(*_excess)[act];
     548        Flow exc=(*_excess)[act];
    532549
    533550        for(OutArcIt e(_g,act);e!=INVALID; ++e) {
    534551          Node v = _g.target(e);
    535           Value fc=(*_up)[e]-(*_flow)[e];
     552          Flow fc=(*_up)[e]-(*_flow)[e];
    536553          if(!_tol.positive(fc)) continue;
    537554          if((*_level)[v]<actlevel) {
     
    557574        for(InArcIt e(_g,act);e!=INVALID; ++e) {
    558575          Node v = _g.source(e);
    559           Value fc=(*_flow)[e]-(*_lo)[e];
     576          Flow fc=(*_flow)[e]-(*_lo)[e];
    560577          if(!_tol.positive(fc)) continue;
    561578          if((*_level)[v]<actlevel) {
     
    633650    /// \pre Either \ref run() or \ref init() must be called before
    634651    /// using this function.
    635     Value flow(const Arc& arc) const {
     652    Flow flow(const Arc& arc) const {
    636653      return (*_flow)[arc];
    637654    }
     
    652669       Barrier is a set \e B of nodes for which
    653670
    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]
     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]
    656673
    657674       holds. The existence of a set with this property prooves that a
     
    716733      for(NodeIt n(_g);n!=INVALID;++n)
    717734        {
    718           Value dif=-(*_delta)[n];
     735          Flow dif=-(*_supply)[n];
    719736          for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
    720737          for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
     
    731748    bool checkBarrier() const
    732749    {
    733       Value delta=0;
     750      Flow delta=0;
    734751      for(NodeIt n(_g);n!=INVALID;++n)
    735752        if(barrier(n))
    736           delta-=(*_delta)[n];
     753          delta-=(*_supply)[n];
    737754      for(ArcIt e(_g);e!=INVALID;++e)
    738755        {
Note: See TracChangeset for help on using the changeset viewer.