COIN-OR::LEMON - Graph Library

Changeset 688:756a5ec551c8 in lemon for lemon/network_simplex.h


Ignore:
Timestamp:
04/29/09 14:25:51 (10 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.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/network_simplex.h

    r687 r688  
    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]) {
Note: See TracChangeset for help on using the changeset viewer.