COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 641:756a5ec551c8 in lemon-main


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

Rename Flow to Value in the flow algorithms (#266)

We agreed that using Flow for the value type is misleading, since
a flow should be rather a function on the arcs, not a single value.

This patch reverts the changes of [dacc2cee2b4c] for Preflow and
Circulation.

Location:
lemon
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • lemon/circulation.h

    r622 r641  
    6565    typedef SM SupplyMap;
    6666
    67     /// \brief The type of the flow values.
    68     typedef typename SupplyMap::Value Flow;
     67    /// \brief The type of the flow and supply values.
     68    typedef typename SupplyMap::Value Value;
    6969
    7070    /// \brief The type of the map that stores the flow values.
    … …  
    7373    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
    7474    /// concept.
    75     typedef typename Digraph::template ArcMap<Flow> FlowMap;
     75    typedef typename Digraph::template ArcMap<Value> FlowMap;
    7676
    7777    /// \brief Instantiates a FlowMap.
    … …  
    105105    ///
    106106    /// The tolerance used by the algorithm to handle inexact computation.
    107     typedef lemon::Tolerance<Flow> Tolerance;
     107    typedef lemon::Tolerance<Value> Tolerance;
    108108
    109109  };
    … …  
    188188    ///The type of the digraph the algorithm runs on.
    189189    typedef typename Traits::Digraph Digraph;
    190     ///The type of the flow values.
    191     typedef typename Traits::Flow Flow;
     190    ///The type of the flow and supply values.
     191    typedef typename Traits::Value Value;
    192192
    193193    ///The type of the lower bound map.
    … …  
    222222    bool _local_level;
    223223
    224     typedef typename Digraph::template NodeMap<Flow> ExcessMap;
     224    typedef typename Digraph::template NodeMap<Value> ExcessMap;
    225225    ExcessMap* _excess;
    226226
    … …  
    531531          (*_excess)[_g.source(e)] -= (*_lo)[e];
    532532        } else {
    533           Flow fc = -(*_excess)[_g.target(e)];
     533          Value fc = -(*_excess)[_g.target(e)];
    534534          _flow->set(e, fc);
    535535          (*_excess)[_g.target(e)] = 0;
    … …  
    564564        int actlevel=(*_level)[act];
    565565        int mlevel=_node_num;
    566         Flow exc=(*_excess)[act];
     566        Value exc=(*_excess)[act];
    567567
    568568        for(OutArcIt e(_g,act);e!=INVALID; ++e) {
    569569          Node v = _g.target(e);
    570           Flow fc=(*_up)[e]-(*_flow)[e];
     570          Value fc=(*_up)[e]-(*_flow)[e];
    571571          if(!_tol.positive(fc)) continue;
    572572          if((*_level)[v]<actlevel) {
    … …  
    592592        for(InArcIt e(_g,act);e!=INVALID; ++e) {
    593593          Node v = _g.source(e);
    594           Flow fc=(*_flow)[e]-(*_lo)[e];
     594          Value fc=(*_flow)[e]-(*_lo)[e];
    595595          if(!_tol.positive(fc)) continue;
    596596          if((*_level)[v]<actlevel) {
    … …  
    662662    ///@{
    663663
    664     /// \brief Returns the flow on the given arc.
    665     ///
    666     /// Returns the flow on the given arc.
     664    /// \brief Returns the flow value on the given arc.
     665    ///
     666    /// Returns the flow value on the given arc.
    667667    ///
    668668    /// \pre Either \ref run() or \ref init() must be called before
    669669    /// using this function.
    670     Flow flow(const Arc& arc) const {
     670    Value flow(const Arc& arc) const {
    671671      return (*_flow)[arc];
    672672    }
    … …  
    751751      for(NodeIt n(_g);n!=INVALID;++n)
    752752        {
    753           Flow dif=-(*_supply)[n];
     753          Value dif=-(*_supply)[n];
    754754          for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
    755755          for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
    … …  
    766766    bool checkBarrier() const
    767767    {
    768       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();
     768      Value delta=0;
     769      Value inf_cap = std::numeric_limits<Value>::has_infinity ?
     770        std::numeric_limits<Value>::infinity() :
     771        std::numeric_limits<Value>::max();
    772772      for(NodeIt n(_g);n!=INVALID;++n)
    773773        if(barrier(n))

  • lemon/network_simplex.h

    r640 r641  
    5757  ///
    5858  /// \tparam GR The digraph type the algorithm runs on.
    59   /// \tparam F The value type used for flow amounts, capacity bounds
     59  /// \tparam V The value type used for flow amounts, capacity bounds
    6060  /// and supply values in the algorithm. By default it is \c int.
    6161  /// \tparam C The value type used for costs and potentials in the
    62   /// algorithm. By default it is the same as \c F.
     62  /// algorithm. By default it is the same as \c V.
    6363  ///
    6464  /// \warning Both value types must be signed and all input data must
    … …  
    6868  /// implementations, from which the most efficient one is used
    6969  /// by default. For more information see \ref PivotRule.
    70   template <typename GR, typename F = int, typename C = F>
     70  template <typename GR, typename V = int, typename C = V>
    7171  class NetworkSimplex
    7272  {
    … …  
    7474
    7575    /// The flow type of the algorithm
    76     typedef F Flow;
     76    typedef V Value;
    7777    /// The cost type of the algorithm
    7878    typedef C Cost;
    7979#ifdef DOXYGEN
    8080    /// The type of the flow map
    81     typedef GR::ArcMap<Flow> FlowMap;
     81    typedef GR::ArcMap<Value> FlowMap;
    8282    /// The type of the potential map
    8383    typedef GR::NodeMap<Cost> PotentialMap;
    8484#else
    8585    /// The type of the flow map
    86     typedef typename GR::template ArcMap<Flow> FlowMap;
     86    typedef typename GR::template ArcMap<Value> FlowMap;
    8787    /// The type of the potential map
    8888    typedef typename GR::template NodeMap<Cost> PotentialMap;
    … …  
    207207    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    208208
    209     typedef typename GR::template ArcMap<Flow> FlowArcMap;
     209    typedef typename GR::template ArcMap<Value> ValueArcMap;
    210210    typedef typename GR::template ArcMap<Cost> CostArcMap;
    211     typedef typename GR::template NodeMap<Flow> FlowNodeMap;
     211    typedef typename GR::template NodeMap<Value> ValueNodeMap;
    212212
    213213    typedef std::vector<Arc> ArcVector;
    … …  
    215215    typedef std::vector<int> IntVector;
    216216    typedef std::vector<bool> BoolVector;
    217     typedef std::vector<Flow> FlowVector;
     217    typedef std::vector<Value> FlowVector;
    218218    typedef std::vector<Cost> CostVector;
    219219
    … …  
    233233
    234234    // Parameters of the problem
    235     FlowArcMap *_plower;
    236     FlowArcMap *_pupper;
     235    ValueArcMap *_plower;
     236    ValueArcMap *_pupper;
    237237    CostArcMap *_pcost;
    238     FlowNodeMap *_psupply;
     238    ValueNodeMap *_psupply;
    239239    bool _pstsup;
    240240    Node _psource, _ptarget;
    241     Flow _pstflow;
     241    Value _pstflow;
    242242    SupplyType _stype;
    243243   
    244     Flow _sum_supply;
     244    Value _sum_supply;
    245245
    246246    // Result maps
    … …  
    279279    int first, second, right, last;
    280280    int stem, par_stem, new_stem;
    281     Flow delta;
     281    Value delta;
    282282
    283283  public:
    … …  
    286286    ///
    287287    /// Constant for infinite upper bounds (capacities).
    288     /// It is \c std::numeric_limits<Flow>::infinity() if available,
    289     /// \c std::numeric_limits<Flow>::max() otherwise.
    290     const Flow INF;
     288    /// It is \c std::numeric_limits<Value>::infinity() if available,
     289    /// \c std::numeric_limits<Value>::max() otherwise.
     290    const Value INF;
    291291
    292292  private:
    … …  
    696696      _local_flow(false), _local_potential(false),
    697697      _node_id(graph),
    698       INF(std::numeric_limits<Flow>::has_infinity ?
    699           std::numeric_limits<Flow>::infinity() :
    700           std::numeric_limits<Flow>::max())
     698      INF(std::numeric_limits<Value>::has_infinity ?
     699          std::numeric_limits<Value>::infinity() :
     700          std::numeric_limits<Value>::max())
    701701    {
    702702      // Check the value types
    703       LEMON_ASSERT(std::numeric_limits<Flow>::is_signed,
     703      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
    704704        "The flow type of NetworkSimplex must be signed");
    705705      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
    … …  
    726726    ///
    727727    /// \param map An arc map storing the lower bounds.
    728     /// Its \c Value type must be convertible to the \c Flow type
     728    /// Its \c Value type must be convertible to the \c Value type
    729729    /// of the algorithm.
    730730    ///
    … …  
    733733    NetworkSimplex& lowerMap(const LowerMap& map) {
    734734      delete _plower;
    735       _plower = new FlowArcMap(_graph);
     735      _plower = new ValueArcMap(_graph);
    736736      for (ArcIt a(_graph); a != INVALID; ++a) {
    737737        (*_plower)[a] = map[a];
    … …  
    748748    ///
    749749    /// \param map An arc map storing the upper bounds.
    750     /// Its \c Value type must be convertible to the \c Flow type
     750    /// Its \c Value type must be convertible to the \c Value type
    751751    /// of the algorithm.
    752752    ///
    … …  
    755755    NetworkSimplex& upperMap(const UpperMap& map) {
    756756      delete _pupper;
    757       _pupper = new FlowArcMap(_graph);
     757      _pupper = new ValueArcMap(_graph);
    758758      for (ArcIt a(_graph); a != INVALID; ++a) {
    759759        (*_pupper)[a] = map[a];
    … …  
    791791    ///
    792792    /// \param map A node map storing the supply values.
    793     /// Its \c Value type must be convertible to the \c Flow type
     793    /// Its \c Value type must be convertible to the \c Value type
    794794    /// of the algorithm.
    795795    ///
    … …  
    799799      delete _psupply;
    800800      _pstsup = false;
    801       _psupply = new FlowNodeMap(_graph);
     801      _psupply = new ValueNodeMap(_graph);
    802802      for (NodeIt n(_graph); n != INVALID; ++n) {
    803803        (*_psupply)[n] = map[n];
    … …  
    824824    ///
    825825    /// \return <tt>(*this)</tt>
    826     NetworkSimplex& stSupply(const Node& s, const Node& t, Flow k) {
     826    NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) {
    827827      delete _psupply;
    828828      _psupply = NULL;
    … …  
    10261026    ///
    10271027    /// \pre \ref run() must be called before using this function.
    1028     Flow flow(const Arc& a) const {
     1028    Value flow(const Arc& a) const {
    10291029      return (*_flow_map)[a];
    10301030    }
    … …  
    12051205      if (_plower) {
    12061206        for (int i = 0; i != _arc_num; ++i) {
    1207           Flow c = (*_plower)[_arc_ref[i]];
     1207          Value c = (*_plower)[_arc_ref[i]];
    12081208          if (c > 0) {
    12091209            if (_cap[i] < INF) _cap[i] -= c;
    … …  
    12761276      delta = _cap[in_arc];
    12771277      int result = 0;
    1278       Flow d;
     1278      Value d;
    12791279      int e;
    12801280
    … …  
    13161316      // Augment along the cycle
    13171317      if (delta > 0) {
    1318         Flow val = _state[in_arc] * delta;
     1318        Value val = _state[in_arc] * delta;
    13191319        _flow[in_arc] += val;
    13201320        for (int u = _source[in_arc]; u != join; u = _parent[u]) {

  • lemon/preflow.h

    r611 r641  
    4747
    4848    /// \brief The type of the flow values.
    49     typedef typename CapacityMap::Value Flow;
     49    typedef typename CapacityMap::Value Value;
    5050
    5151    /// \brief The type of the map that stores the flow values.
    … …  
    5353    /// The type of the map that stores the flow values.
    5454    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    55     typedef typename Digraph::template ArcMap<Flow> FlowMap;
     55    typedef typename Digraph::template ArcMap<Value> FlowMap;
    5656
    5757    /// \brief Instantiates a FlowMap.
    … …  
    8585    ///
    8686    /// The tolerance used by the algorithm to handle inexact computation.
    87     typedef lemon::Tolerance<Flow> Tolerance;
     87    typedef lemon::Tolerance<Value> Tolerance;
    8888
    8989  };
    … …  
    126126    typedef typename Traits::CapacityMap CapacityMap;
    127127    ///The type of the flow values.
    128     typedef typename Traits::Flow Flow;
     128    typedef typename Traits::Value Value;
    129129
    130130    ///The type of the flow map.
    … …  
    152152    bool _local_level;
    153153
    154     typedef typename Digraph::template NodeMap<Flow> ExcessMap;
     154    typedef typename Digraph::template NodeMap<Value> ExcessMap;
    155155    ExcessMap* _excess;
    156156
    … …  
    471471
    472472      for (NodeIt n(_graph); n != INVALID; ++n) {
    473         Flow excess = 0;
     473        Value excess = 0;
    474474        for (InArcIt e(_graph, n); e != INVALID; ++e) {
    475475          excess += (*_flow)[e];
    … …  
    520520
    521521      for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
    522         Flow rem = (*_capacity)[e] - (*_flow)[e];
     522        Value rem = (*_capacity)[e] - (*_flow)[e];
    523523        if (_tolerance.positive(rem)) {
    524524          Node u = _graph.target(e);
    … …  
    532532      }
    533533      for (InArcIt e(_graph, _source); e != INVALID; ++e) {
    534         Flow rem = (*_flow)[e];
     534        Value rem = (*_flow)[e];
    535535        if (_tolerance.positive(rem)) {
    536536          Node v = _graph.source(e);
    … …  
    565565
    566566        while (num > 0 && n != INVALID) {
    567           Flow excess = (*_excess)[n];
     567          Value excess = (*_excess)[n];
    568568          int new_level = _level->maxLevel();
    569569
    570570          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
    571             Flow rem = (*_capacity)[e] - (*_flow)[e];
     571            Value rem = (*_capacity)[e] - (*_flow)[e];
    572572            if (!_tolerance.positive(rem)) continue;
    573573            Node v = _graph.target(e);
    … …  
    592592
    593593          for (InArcIt e(_graph, n); e != INVALID; ++e) {
    594             Flow rem = (*_flow)[e];
     594            Value rem = (*_flow)[e];
    595595            if (!_tolerance.positive(rem)) continue;
    596596            Node v = _graph.source(e);
    … …  
    638638        num = _node_num * 20;
    639639        while (num > 0 && n != INVALID) {
    640           Flow excess = (*_excess)[n];
     640          Value excess = (*_excess)[n];
    641641          int new_level = _level->maxLevel();
    642642
    643643          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
    644             Flow rem = (*_capacity)[e] - (*_flow)[e];
     644            Value rem = (*_capacity)[e] - (*_flow)[e];
    645645            if (!_tolerance.positive(rem)) continue;
    646646            Node v = _graph.target(e);
    … …  
    665665
    666666          for (InArcIt e(_graph, n); e != INVALID; ++e) {
    667             Flow rem = (*_flow)[e];
     667            Value rem = (*_flow)[e];
    668668            if (!_tolerance.positive(rem)) continue;
    669669            Node v = _graph.source(e);
    … …  
    779779      Node n;
    780780      while ((n = _level->highestActive()) != INVALID) {
    781         Flow excess = (*_excess)[n];
     781        Value excess = (*_excess)[n];
    782782        int level = _level->highestActiveLevel();
    783783        int new_level = _level->maxLevel();
    784784
    785785        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
    786           Flow rem = (*_capacity)[e] - (*_flow)[e];
     786          Value rem = (*_capacity)[e] - (*_flow)[e];
    787787          if (!_tolerance.positive(rem)) continue;
    788788          Node v = _graph.target(e);
    … …  
    807807
    808808        for (InArcIt e(_graph, n); e != INVALID; ++e) {
    809           Flow rem = (*_flow)[e];
     809          Value rem = (*_flow)[e];
    810810          if (!_tolerance.positive(rem)) continue;
    811811          Node v = _graph.source(e);
    … …  
    898898    /// \pre Either \ref run() or \ref init() must be called before
    899899    /// using this function.
    900     Flow flowValue() const {
     900    Value flowValue() const {
    901901      return (*_excess)[_target];
    902902    }
    903903
    904     /// \brief Returns the flow on the given arc.
    905     ///
    906     /// Returns the flow on the given arc. This method can
     904    /// \brief Returns the flow value on the given arc.
     905    ///
     906    /// Returns the flow value on the given arc. This method can
    907907    /// be called after the second phase of the algorithm.
    908908    ///
    909909    /// \pre Either \ref run() or \ref init() must be called before
    910910    /// using this function.
    911     Flow flow(const Arc& arc) const {
     911    Value flow(const Arc& arc) const {
    912912      return (*_flow)[arc];
    913913    }
Note: See TracChangeset for help on using the changeset viewer.