COIN-OR::LEMON - Graph Library

Changeset 1155:9fd86ec2cb81 in lemon-main


Ignore:
Timestamp:
10/08/15 10:13:24 (9 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
1156:f51c01a1b88e, 1163:db1d342a1087
Parents:
1154:9b4503108cc0 (diff), 1151:43647f48e971 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge #600

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/capacity_scaling.h

    r1151 r1155  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6868  /// \ref CapacityScaling implements the capacity scaling version
    6969  /// of the successive shortest path algorithm for finding a
    70   /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
    71   /// \ref edmondskarp72theoretical. It is an efficient dual
    72   /// solution method.
     70  /// \ref min_cost_flow "minimum cost flow" \cite amo93networkflows,
     71  /// \cite edmondskarp72theoretical. It is an efficient dual
     72  /// solution method, which runs in polynomial time
     73  /// \f$O(m\log U (n+m)\log n)\f$, where <i>U</i> denotes the maximum
     74  /// of node supply and arc capacity values.
     75  ///
     76  /// This algorithm is typically slower than \ref CostScaling and
     77  /// \ref NetworkSimplex, but in special cases, it can be more
     78  /// efficient than them.
     79  /// (For more information, see \ref min_cost_flow_algs "the module page".)
    7380  ///
    7481  /// Most of the parameters of the problem (except for the digraph)
     
    7986  /// \tparam GR The digraph type the algorithm runs on.
    8087  /// \tparam V The number type used for flow amounts, capacity bounds
    81   /// and supply values in the algorithm. By default it is \c int.
     88  /// and supply values in the algorithm. By default, it is \c int.
    8289  /// \tparam C The number type used for costs and potentials in the
    83   /// algorithm. By default it is the same as \c V.
     90  /// algorithm. By default, it is the same as \c V.
     91  /// \tparam TR The traits class that defines various types used by the
     92  /// algorithm. By default, it is \ref CapacityScalingDefaultTraits
     93  /// "CapacityScalingDefaultTraits<GR, V, C>".
     94  /// In most cases, this parameter should not be set directly,
     95  /// consider to use the named template parameters instead.
    8496  ///
    85   /// \warning Both number types must be signed and all input data must
    86   /// be integer.
    87   /// \warning This algorithm does not support negative costs for such
    88   /// arcs that have infinite upper bound.
     97  /// \warning Both \c V and \c C must be signed number types.
     98  /// \warning Capacity bounds and supply values must be integer, but
     99  /// arc costs can be arbitrary real numbers.
     100  /// \warning This algorithm does not support negative costs for
     101  /// arcs having infinite upper bound.
    89102#ifdef DOXYGEN
    90103  template <typename GR, typename V, typename C, typename TR>
     
    107120    typedef typename TR::Heap Heap;
    108121
    109     /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm
     122    /// \brief The \ref lemon::CapacityScalingDefaultTraits "traits class"
     123    /// of the algorithm
    110124    typedef TR Traits;
    111125
     
    130144      UNBOUNDED
    131145    };
    132  
     146
    133147  private:
    134148
     
    136150
    137151    typedef std::vector<int> IntVector;
    138     typedef std::vector<char> BoolVector;
    139152    typedef std::vector<Value> ValueVector;
    140153    typedef std::vector<Cost> CostVector;
     154    typedef std::vector<char> BoolVector;
     155    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
    141156
    142157  private:
     
    150165
    151166    // Parameters of the problem
    152     bool _have_lower;
     167    bool _has_lower;
    153168    Value _sum_supply;
    154169
     
    180195
    181196  public:
    182  
     197
    183198    /// \brief Constant for infinite upper bounds (capacities).
    184199    ///
     
    207222      CostVector &_pi;
    208223      IntVector &_pred;
    209      
     224
    210225      IntVector _proc_nodes;
    211226      CostVector _dist;
    212      
     227
    213228    public:
    214229
     
    297312    /// @}
    298313
     314  protected:
     315
     316    CapacityScaling() {}
     317
    299318  public:
    300319
     
    316335        "The cost type of CapacityScaling must be signed");
    317336
     337      // Reset data structures
     338      reset();
     339    }
     340
     341    /// \name Parameters
     342    /// The parameters of the algorithm can be specified using these
     343    /// functions.
     344
     345    /// @{
     346
     347    /// \brief Set the lower bounds on the arcs.
     348    ///
     349    /// This function sets the lower bounds on the arcs.
     350    /// If it is not used before calling \ref run(), the lower bounds
     351    /// will be set to zero on all arcs.
     352    ///
     353    /// \param map An arc map storing the lower bounds.
     354    /// Its \c Value type must be convertible to the \c Value type
     355    /// of the algorithm.
     356    ///
     357    /// \return <tt>(*this)</tt>
     358    template <typename LowerMap>
     359    CapacityScaling& lowerMap(const LowerMap& map) {
     360      _has_lower = true;
     361      for (ArcIt a(_graph); a != INVALID; ++a) {
     362        _lower[_arc_idf[a]] = map[a];
     363      }
     364      return *this;
     365    }
     366
     367    /// \brief Set the upper bounds (capacities) on the arcs.
     368    ///
     369    /// This function sets the upper bounds (capacities) on the arcs.
     370    /// If it is not used before calling \ref run(), the upper bounds
     371    /// will be set to \ref INF on all arcs (i.e. the flow value will be
     372    /// unbounded from above).
     373    ///
     374    /// \param map An arc map storing the upper bounds.
     375    /// Its \c Value type must be convertible to the \c Value type
     376    /// of the algorithm.
     377    ///
     378    /// \return <tt>(*this)</tt>
     379    template<typename UpperMap>
     380    CapacityScaling& upperMap(const UpperMap& map) {
     381      for (ArcIt a(_graph); a != INVALID; ++a) {
     382        _upper[_arc_idf[a]] = map[a];
     383      }
     384      return *this;
     385    }
     386
     387    /// \brief Set the costs of the arcs.
     388    ///
     389    /// This function sets the costs of the arcs.
     390    /// If it is not used before calling \ref run(), the costs
     391    /// will be set to \c 1 on all arcs.
     392    ///
     393    /// \param map An arc map storing the costs.
     394    /// Its \c Value type must be convertible to the \c Cost type
     395    /// of the algorithm.
     396    ///
     397    /// \return <tt>(*this)</tt>
     398    template<typename CostMap>
     399    CapacityScaling& costMap(const CostMap& map) {
     400      for (ArcIt a(_graph); a != INVALID; ++a) {
     401        _cost[_arc_idf[a]] =  map[a];
     402        _cost[_arc_idb[a]] = -map[a];
     403      }
     404      return *this;
     405    }
     406
     407    /// \brief Set the supply values of the nodes.
     408    ///
     409    /// This function sets the supply values of the nodes.
     410    /// If neither this function nor \ref stSupply() is used before
     411    /// calling \ref run(), the supply of each node will be set to zero.
     412    ///
     413    /// \param map A node map storing the supply values.
     414    /// Its \c Value type must be convertible to the \c Value type
     415    /// of the algorithm.
     416    ///
     417    /// \return <tt>(*this)</tt>
     418    template<typename SupplyMap>
     419    CapacityScaling& supplyMap(const SupplyMap& map) {
     420      for (NodeIt n(_graph); n != INVALID; ++n) {
     421        _supply[_node_id[n]] = map[n];
     422      }
     423      return *this;
     424    }
     425
     426    /// \brief Set single source and target nodes and a supply value.
     427    ///
     428    /// This function sets a single source node and a single target node
     429    /// and the required flow value.
     430    /// If neither this function nor \ref supplyMap() is used before
     431    /// calling \ref run(), the supply of each node will be set to zero.
     432    ///
     433    /// Using this function has the same effect as using \ref supplyMap()
     434    /// with a map in which \c k is assigned to \c s, \c -k is
     435    /// assigned to \c t and all other nodes have zero supply value.
     436    ///
     437    /// \param s The source node.
     438    /// \param t The target node.
     439    /// \param k The required amount of flow from node \c s to node \c t
     440    /// (i.e. the supply of \c s and the demand of \c t).
     441    ///
     442    /// \return <tt>(*this)</tt>
     443    CapacityScaling& stSupply(const Node& s, const Node& t, Value k) {
     444      for (int i = 0; i != _node_num; ++i) {
     445        _supply[i] = 0;
     446      }
     447      _supply[_node_id[s]] =  k;
     448      _supply[_node_id[t]] = -k;
     449      return *this;
     450    }
     451
     452    /// @}
     453
     454    /// \name Execution control
     455    /// The algorithm can be executed using \ref run().
     456
     457    /// @{
     458
     459    /// \brief Run the algorithm.
     460    ///
     461    /// This function runs the algorithm.
     462    /// The paramters can be specified using functions \ref lowerMap(),
     463    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
     464    /// For example,
     465    /// \code
     466    ///   CapacityScaling<ListDigraph> cs(graph);
     467    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
     468    ///     .supplyMap(sup).run();
     469    /// \endcode
     470    ///
     471    /// This function can be called more than once. All the given parameters
     472    /// are kept for the next call, unless \ref resetParams() or \ref reset()
     473    /// is used, thus only the modified parameters have to be set again.
     474    /// If the underlying digraph was also modified after the construction
     475    /// of the class (or the last \ref reset() call), then the \ref reset()
     476    /// function must be called.
     477    ///
     478    /// \param factor The capacity scaling factor. It must be larger than
     479    /// one to use scaling. If it is less or equal to one, then scaling
     480    /// will be disabled.
     481    ///
     482    /// \return \c INFEASIBLE if no feasible flow exists,
     483    /// \n \c OPTIMAL if the problem has optimal solution
     484    /// (i.e. it is feasible and bounded), and the algorithm has found
     485    /// optimal flow and node potentials (primal and dual solutions),
     486    /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
     487    /// and infinite upper bound. It means that the objective function
     488    /// is unbounded on that arc, however, note that it could actually be
     489    /// bounded over the feasible flows, but this algroithm cannot handle
     490    /// these cases.
     491    ///
     492    /// \see ProblemType
     493    /// \see resetParams(), reset()
     494    ProblemType run(int factor = 4) {
     495      _factor = factor;
     496      ProblemType pt = init();
     497      if (pt != OPTIMAL) return pt;
     498      return start();
     499    }
     500
     501    /// \brief Reset all the parameters that have been given before.
     502    ///
     503    /// This function resets all the paramaters that have been given
     504    /// before using functions \ref lowerMap(), \ref upperMap(),
     505    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
     506    ///
     507    /// It is useful for multiple \ref run() calls. Basically, all the given
     508    /// parameters are kept for the next \ref run() call, unless
     509    /// \ref resetParams() or \ref reset() is used.
     510    /// If the underlying digraph was also modified after the construction
     511    /// of the class or the last \ref reset() call, then the \ref reset()
     512    /// function must be used, otherwise \ref resetParams() is sufficient.
     513    ///
     514    /// For example,
     515    /// \code
     516    ///   CapacityScaling<ListDigraph> cs(graph);
     517    ///
     518    ///   // First run
     519    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
     520    ///     .supplyMap(sup).run();
     521    ///
     522    ///   // Run again with modified cost map (resetParams() is not called,
     523    ///   // so only the cost map have to be set again)
     524    ///   cost[e] += 100;
     525    ///   cs.costMap(cost).run();
     526    ///
     527    ///   // Run again from scratch using resetParams()
     528    ///   // (the lower bounds will be set to zero on all arcs)
     529    ///   cs.resetParams();
     530    ///   cs.upperMap(capacity).costMap(cost)
     531    ///     .supplyMap(sup).run();
     532    /// \endcode
     533    ///
     534    /// \return <tt>(*this)</tt>
     535    ///
     536    /// \see reset(), run()
     537    CapacityScaling& resetParams() {
     538      for (int i = 0; i != _node_num; ++i) {
     539        _supply[i] = 0;
     540      }
     541      for (int j = 0; j != _res_arc_num; ++j) {
     542        _lower[j] = 0;
     543        _upper[j] = INF;
     544        _cost[j] = _forward[j] ? 1 : -1;
     545      }
     546      _has_lower = false;
     547      return *this;
     548    }
     549
     550    /// \brief Reset the internal data structures and all the parameters
     551    /// that have been given before.
     552    ///
     553    /// This function resets the internal data structures and all the
     554    /// paramaters that have been given before using functions \ref lowerMap(),
     555    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
     556    ///
     557    /// It is useful for multiple \ref run() calls. Basically, all the given
     558    /// parameters are kept for the next \ref run() call, unless
     559    /// \ref resetParams() or \ref reset() is used.
     560    /// If the underlying digraph was also modified after the construction
     561    /// of the class or the last \ref reset() call, then the \ref reset()
     562    /// function must be used, otherwise \ref resetParams() is sufficient.
     563    ///
     564    /// See \ref resetParams() for examples.
     565    ///
     566    /// \return <tt>(*this)</tt>
     567    ///
     568    /// \see resetParams(), run()
     569    CapacityScaling& reset() {
    318570      // Resize vectors
    319571      _node_num = countNodes(_graph);
     
    333585      _cost.resize(_res_arc_num);
    334586      _supply.resize(_node_num);
    335      
     587
    336588      _res_cap.resize(_res_arc_num);
    337589      _pi.resize(_node_num);
     
    377629        _reverse[bi] = fi;
    378630      }
    379      
     631
    380632      // Reset parameters
    381       reset();
    382     }
    383 
    384     /// \name Parameters
    385     /// The parameters of the algorithm can be specified using these
    386     /// functions.
    387 
    388     /// @{
    389 
    390     /// \brief Set the lower bounds on the arcs.
    391     ///
    392     /// This function sets the lower bounds on the arcs.
    393     /// If it is not used before calling \ref run(), the lower bounds
    394     /// will be set to zero on all arcs.
    395     ///
    396     /// \param map An arc map storing the lower bounds.
    397     /// Its \c Value type must be convertible to the \c Value type
    398     /// of the algorithm.
    399     ///
    400     /// \return <tt>(*this)</tt>
    401     template <typename LowerMap>
    402     CapacityScaling& lowerMap(const LowerMap& map) {
    403       _have_lower = true;
    404       for (ArcIt a(_graph); a != INVALID; ++a) {
    405         _lower[_arc_idf[a]] = map[a];
    406         _lower[_arc_idb[a]] = map[a];
    407       }
    408       return *this;
    409     }
    410 
    411     /// \brief Set the upper bounds (capacities) on the arcs.
    412     ///
    413     /// This function sets the upper bounds (capacities) on the arcs.
    414     /// If it is not used before calling \ref run(), the upper bounds
    415     /// will be set to \ref INF on all arcs (i.e. the flow value will be
    416     /// unbounded from above).
    417     ///
    418     /// \param map An arc map storing the upper bounds.
    419     /// Its \c Value type must be convertible to the \c Value type
    420     /// of the algorithm.
    421     ///
    422     /// \return <tt>(*this)</tt>
    423     template<typename UpperMap>
    424     CapacityScaling& upperMap(const UpperMap& map) {
    425       for (ArcIt a(_graph); a != INVALID; ++a) {
    426         _upper[_arc_idf[a]] = map[a];
    427       }
    428       return *this;
    429     }
    430 
    431     /// \brief Set the costs of the arcs.
    432     ///
    433     /// This function sets the costs of the arcs.
    434     /// If it is not used before calling \ref run(), the costs
    435     /// will be set to \c 1 on all arcs.
    436     ///
    437     /// \param map An arc map storing the costs.
    438     /// Its \c Value type must be convertible to the \c Cost type
    439     /// of the algorithm.
    440     ///
    441     /// \return <tt>(*this)</tt>
    442     template<typename CostMap>
    443     CapacityScaling& costMap(const CostMap& map) {
    444       for (ArcIt a(_graph); a != INVALID; ++a) {
    445         _cost[_arc_idf[a]] =  map[a];
    446         _cost[_arc_idb[a]] = -map[a];
    447       }
    448       return *this;
    449     }
    450 
    451     /// \brief Set the supply values of the nodes.
    452     ///
    453     /// This function sets the supply values of the nodes.
    454     /// If neither this function nor \ref stSupply() is used before
    455     /// calling \ref run(), the supply of each node will be set to zero.
    456     ///
    457     /// \param map A node map storing the supply values.
    458     /// Its \c Value type must be convertible to the \c Value type
    459     /// of the algorithm.
    460     ///
    461     /// \return <tt>(*this)</tt>
    462     template<typename SupplyMap>
    463     CapacityScaling& supplyMap(const SupplyMap& map) {
    464       for (NodeIt n(_graph); n != INVALID; ++n) {
    465         _supply[_node_id[n]] = map[n];
    466       }
    467       return *this;
    468     }
    469 
    470     /// \brief Set single source and target nodes and a supply value.
    471     ///
    472     /// This function sets a single source node and a single target node
    473     /// and the required flow value.
    474     /// If neither this function nor \ref supplyMap() is used before
    475     /// calling \ref run(), the supply of each node will be set to zero.
    476     ///
    477     /// Using this function has the same effect as using \ref supplyMap()
    478     /// with such a map in which \c k is assigned to \c s, \c -k is
    479     /// assigned to \c t and all other nodes have zero supply value.
    480     ///
    481     /// \param s The source node.
    482     /// \param t The target node.
    483     /// \param k The required amount of flow from node \c s to node \c t
    484     /// (i.e. the supply of \c s and the demand of \c t).
    485     ///
    486     /// \return <tt>(*this)</tt>
    487     CapacityScaling& stSupply(const Node& s, const Node& t, Value k) {
    488       for (int i = 0; i != _node_num; ++i) {
    489         _supply[i] = 0;
    490       }
    491       _supply[_node_id[s]] =  k;
    492       _supply[_node_id[t]] = -k;
    493       return *this;
    494     }
    495    
    496     /// @}
    497 
    498     /// \name Execution control
    499     /// The algorithm can be executed using \ref run().
    500 
    501     /// @{
    502 
    503     /// \brief Run the algorithm.
    504     ///
    505     /// This function runs the algorithm.
    506     /// The paramters can be specified using functions \ref lowerMap(),
    507     /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
    508     /// For example,
    509     /// \code
    510     ///   CapacityScaling<ListDigraph> cs(graph);
    511     ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
    512     ///     .supplyMap(sup).run();
    513     /// \endcode
    514     ///
    515     /// This function can be called more than once. All the parameters
    516     /// that have been given are kept for the next call, unless
    517     /// \ref reset() is called, thus only the modified parameters
    518     /// have to be set again. See \ref reset() for examples.
    519     /// However, the underlying digraph must not be modified after this
    520     /// class have been constructed, since it copies and extends the graph.
    521     ///
    522     /// \param factor The capacity scaling factor. It must be larger than
    523     /// one to use scaling. If it is less or equal to one, then scaling
    524     /// will be disabled.
    525     ///
    526     /// \return \c INFEASIBLE if no feasible flow exists,
    527     /// \n \c OPTIMAL if the problem has optimal solution
    528     /// (i.e. it is feasible and bounded), and the algorithm has found
    529     /// optimal flow and node potentials (primal and dual solutions),
    530     /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
    531     /// and infinite upper bound. It means that the objective function
    532     /// is unbounded on that arc, however, note that it could actually be
    533     /// bounded over the feasible flows, but this algroithm cannot handle
    534     /// these cases.
    535     ///
    536     /// \see ProblemType
    537     ProblemType run(int factor = 4) {
    538       _factor = factor;
    539       ProblemType pt = init();
    540       if (pt != OPTIMAL) return pt;
    541       return start();
    542     }
    543 
    544     /// \brief Reset all the parameters that have been given before.
    545     ///
    546     /// This function resets all the paramaters that have been given
    547     /// before using functions \ref lowerMap(), \ref upperMap(),
    548     /// \ref costMap(), \ref supplyMap(), \ref stSupply().
    549     ///
    550     /// It is useful for multiple run() calls. If this function is not
    551     /// used, all the parameters given before are kept for the next
    552     /// \ref run() call.
    553     /// However, the underlying digraph must not be modified after this
    554     /// class have been constructed, since it copies and extends the graph.
    555     ///
    556     /// For example,
    557     /// \code
    558     ///   CapacityScaling<ListDigraph> cs(graph);
    559     ///
    560     ///   // First run
    561     ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
    562     ///     .supplyMap(sup).run();
    563     ///
    564     ///   // Run again with modified cost map (reset() is not called,
    565     ///   // so only the cost map have to be set again)
    566     ///   cost[e] += 100;
    567     ///   cs.costMap(cost).run();
    568     ///
    569     ///   // Run again from scratch using reset()
    570     ///   // (the lower bounds will be set to zero on all arcs)
    571     ///   cs.reset();
    572     ///   cs.upperMap(capacity).costMap(cost)
    573     ///     .supplyMap(sup).run();
    574     /// \endcode
    575     ///
    576     /// \return <tt>(*this)</tt>
    577     CapacityScaling& reset() {
    578       for (int i = 0; i != _node_num; ++i) {
    579         _supply[i] = 0;
    580       }
    581       for (int j = 0; j != _res_arc_num; ++j) {
    582         _lower[j] = 0;
    583         _upper[j] = INF;
    584         _cost[j] = _forward[j] ? 1 : -1;
    585       }
    586       _have_lower = false;
     633      resetParams();
    587634      return *this;
    588635    }
     
    600647    ///
    601648    /// This function returns the total cost of the found flow.
    602     /// Its complexity is O(e).
     649    /// Its complexity is O(m).
    603650    ///
    604651    /// \note The return type of the function can be specified as a
     
    638685    }
    639686
    640     /// \brief Return the flow map (the primal solution).
     687    /// \brief Copy the flow values (the primal solution) into the
     688    /// given map.
    641689    ///
    642690    /// This function copies the flow value on each arc into the given
     
    662710    }
    663711
    664     /// \brief Return the potential map (the dual solution).
     712    /// \brief Copy the potential values (the dual solution) into the
     713    /// given map.
    665714    ///
    666715    /// This function copies the potential (dual value) of each node
     
    691740      }
    692741      if (_sum_supply > 0) return INFEASIBLE;
    693      
     742
     743      // Check lower and upper bounds
     744      LEMON_DEBUG(checkBoundMaps(),
     745          "Upper bounds must be greater or equal to the lower bounds");
     746
     747
    694748      // Initialize vectors
    695749      for (int i = 0; i != _root; ++i) {
     
    701755      const Value MAX = std::numeric_limits<Value>::max();
    702756      int last_out;
    703       if (_have_lower) {
     757      if (_has_lower) {
    704758        for (int i = 0; i != _root; ++i) {
    705759          last_out = _first_out[i+1];
     
    739793        }
    740794      }
    741      
     795
    742796      // Handle GEQ supply type
    743797      if (_sum_supply < 0) {
     
    766820      if (_factor > 1) {
    767821        // With scaling
    768         Value max_sup = 0, max_dem = 0;
    769         for (int i = 0; i != _node_num; ++i) {
     822        Value max_sup = 0, max_dem = 0, max_cap = 0;
     823        for (int i = 0; i != _root; ++i) {
    770824          Value ex = _excess[i];
    771825          if ( ex > max_sup) max_sup =  ex;
    772826          if (-ex > max_dem) max_dem = -ex;
    773         }
    774         Value max_cap = 0;
    775         for (int j = 0; j != _res_arc_num; ++j) {
    776           if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
     827          int last_out = _first_out[i+1] - 1;
     828          for (int j = _first_out[i]; j != last_out; ++j) {
     829            if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
     830          }
    777831        }
    778832        max_sup = std::min(std::min(max_sup, max_dem), max_cap);
     
    784838
    785839      return OPTIMAL;
     840    }
     841
     842    // Check if the upper bound is greater than or equal to the lower bound
     843    // on each forward arc.
     844    bool checkBoundMaps() {
     845      for (int j = 0; j != _res_arc_num; ++j) {
     846        if (_forward[j] && _upper[j] < _lower[j]) return false;
     847      }
     848      return true;
    786849    }
    787850
     
    795858
    796859      // Handle non-zero lower bounds
    797       if (_have_lower) {
     860      if (_has_lower) {
    798861        int limit = _first_out[_root];
    799862        for (int j = 0; j != limit; ++j) {
    800           if (!_forward[j]) _res_cap[j] += _lower[j];
     863          if (_forward[j]) _res_cap[_reverse[j]] += _lower[j];
    801864        }
    802865      }
     
    807870        for (int i = 0; i != _node_num; ++i) {
    808871          _pi[i] -= pr;
    809         }       
    810       }
    811      
     872        }
     873      }
     874
    812875      return pt;
    813876    }
  • lemon/capacity_scaling.h

    r1104 r1155  
    2828#include <limits>
    2929#include <lemon/core.h>
     30#include <lemon/maps.h>
    3031#include <lemon/bin_heap.h>
    3132
Note: See TracChangeset for help on using the changeset viewer.