COIN-OR::LEMON - Graph Library

Changeset 840:2914b6f0fde0 in lemon-1.2 for lemon/capacity_scaling.h


Ignore:
Timestamp:
02/26/10 14:00:20 (10 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
838:2c35bef44dd1 (diff), 839:f3bc4e9b5f3a (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 #340

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/capacity_scaling.h

    r831 r840  
    140140
    141141    typedef std::vector<int> IntVector;
    142     typedef std::vector<char> BoolVector;
    143142    typedef std::vector<Value> ValueVector;
    144143    typedef std::vector<Cost> CostVector;
     144    typedef std::vector<char> BoolVector;
     145    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
    145146
    146147  private:
     
    799800      if (_factor > 1) {
    800801        // With scaling
    801         Value max_sup = 0, max_dem = 0;
    802         for (int i = 0; i != _node_num; ++i) {
     802        Value max_sup = 0, max_dem = 0, max_cap = 0;
     803        for (int i = 0; i != _root; ++i) {
    803804          Value ex = _excess[i];
    804805          if ( ex > max_sup) max_sup =  ex;
    805806          if (-ex > max_dem) max_dem = -ex;
    806         }
    807         Value max_cap = 0;
    808         for (int j = 0; j != _res_arc_num; ++j) {
    809           if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
     807          int last_out = _first_out[i+1] - 1;
     808          for (int j = _first_out[i]; j != last_out; ++j) {
     809            if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
     810          }
    810811        }
    811812        max_sup = std::min(std::min(max_sup, max_dem), max_cap);
  • lemon/capacity_scaling.h

    r839 r840  
    7878  /// \tparam GR The digraph type the algorithm runs on.
    7979  /// \tparam V The number type used for flow amounts, capacity bounds
    80   /// and supply values in the algorithm. By default it is \c int.
     80  /// and supply values in the algorithm. By default, it is \c int.
    8181  /// \tparam C The number type used for costs and potentials in the
    82   /// algorithm. By default it is the same as \c V.
     82  /// algorithm. By default, it is the same as \c V.
     83  /// \tparam TR The traits class that defines various types used by the
     84  /// algorithm. By default, it is \ref CapacityScalingDefaultTraits
     85  /// "CapacityScalingDefaultTraits<GR, V, C>".
     86  /// In most cases, this parameter should not be set directly,
     87  /// consider to use the named template parameters instead.
    8388  ///
    8489  /// \warning Both number types must be signed and all input data must
     
    316321        "The cost type of CapacityScaling must be signed");
    317322
     323      // Reset data structures
     324      reset();
     325    }
     326
     327    /// \name Parameters
     328    /// The parameters of the algorithm can be specified using these
     329    /// functions.
     330
     331    /// @{
     332
     333    /// \brief Set the lower bounds on the arcs.
     334    ///
     335    /// This function sets the lower bounds on the arcs.
     336    /// If it is not used before calling \ref run(), the lower bounds
     337    /// will be set to zero on all arcs.
     338    ///
     339    /// \param map An arc map storing the lower bounds.
     340    /// Its \c Value type must be convertible to the \c Value type
     341    /// of the algorithm.
     342    ///
     343    /// \return <tt>(*this)</tt>
     344    template <typename LowerMap>
     345    CapacityScaling& lowerMap(const LowerMap& map) {
     346      _have_lower = true;
     347      for (ArcIt a(_graph); a != INVALID; ++a) {
     348        _lower[_arc_idf[a]] = map[a];
     349        _lower[_arc_idb[a]] = map[a];
     350      }
     351      return *this;
     352    }
     353
     354    /// \brief Set the upper bounds (capacities) on the arcs.
     355    ///
     356    /// This function sets the upper bounds (capacities) on the arcs.
     357    /// If it is not used before calling \ref run(), the upper bounds
     358    /// will be set to \ref INF on all arcs (i.e. the flow value will be
     359    /// unbounded from above).
     360    ///
     361    /// \param map An arc map storing the upper bounds.
     362    /// Its \c Value type must be convertible to the \c Value type
     363    /// of the algorithm.
     364    ///
     365    /// \return <tt>(*this)</tt>
     366    template<typename UpperMap>
     367    CapacityScaling& upperMap(const UpperMap& map) {
     368      for (ArcIt a(_graph); a != INVALID; ++a) {
     369        _upper[_arc_idf[a]] = map[a];
     370      }
     371      return *this;
     372    }
     373
     374    /// \brief Set the costs of the arcs.
     375    ///
     376    /// This function sets the costs of the arcs.
     377    /// If it is not used before calling \ref run(), the costs
     378    /// will be set to \c 1 on all arcs.
     379    ///
     380    /// \param map An arc map storing the costs.
     381    /// Its \c Value type must be convertible to the \c Cost type
     382    /// of the algorithm.
     383    ///
     384    /// \return <tt>(*this)</tt>
     385    template<typename CostMap>
     386    CapacityScaling& costMap(const CostMap& map) {
     387      for (ArcIt a(_graph); a != INVALID; ++a) {
     388        _cost[_arc_idf[a]] =  map[a];
     389        _cost[_arc_idb[a]] = -map[a];
     390      }
     391      return *this;
     392    }
     393
     394    /// \brief Set the supply values of the nodes.
     395    ///
     396    /// This function sets the supply values of the nodes.
     397    /// If neither this function nor \ref stSupply() is used before
     398    /// calling \ref run(), the supply of each node will be set to zero.
     399    ///
     400    /// \param map A node map storing the supply values.
     401    /// Its \c Value type must be convertible to the \c Value type
     402    /// of the algorithm.
     403    ///
     404    /// \return <tt>(*this)</tt>
     405    template<typename SupplyMap>
     406    CapacityScaling& supplyMap(const SupplyMap& map) {
     407      for (NodeIt n(_graph); n != INVALID; ++n) {
     408        _supply[_node_id[n]] = map[n];
     409      }
     410      return *this;
     411    }
     412
     413    /// \brief Set single source and target nodes and a supply value.
     414    ///
     415    /// This function sets a single source node and a single target node
     416    /// and the required flow value.
     417    /// If neither this function nor \ref supplyMap() is used before
     418    /// calling \ref run(), the supply of each node will be set to zero.
     419    ///
     420    /// Using this function has the same effect as using \ref supplyMap()
     421    /// with such a map in which \c k is assigned to \c s, \c -k is
     422    /// assigned to \c t and all other nodes have zero supply value.
     423    ///
     424    /// \param s The source node.
     425    /// \param t The target node.
     426    /// \param k The required amount of flow from node \c s to node \c t
     427    /// (i.e. the supply of \c s and the demand of \c t).
     428    ///
     429    /// \return <tt>(*this)</tt>
     430    CapacityScaling& stSupply(const Node& s, const Node& t, Value k) {
     431      for (int i = 0; i != _node_num; ++i) {
     432        _supply[i] = 0;
     433      }
     434      _supply[_node_id[s]] =  k;
     435      _supply[_node_id[t]] = -k;
     436      return *this;
     437    }
     438   
     439    /// @}
     440
     441    /// \name Execution control
     442    /// The algorithm can be executed using \ref run().
     443
     444    /// @{
     445
     446    /// \brief Run the algorithm.
     447    ///
     448    /// This function runs the algorithm.
     449    /// The paramters can be specified using functions \ref lowerMap(),
     450    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
     451    /// For example,
     452    /// \code
     453    ///   CapacityScaling<ListDigraph> cs(graph);
     454    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
     455    ///     .supplyMap(sup).run();
     456    /// \endcode
     457    ///
     458    /// This function can be called more than once. All the given parameters
     459    /// are kept for the next call, unless \ref resetParams() or \ref reset()
     460    /// is used, thus only the modified parameters have to be set again.
     461    /// If the underlying digraph was also modified after the construction
     462    /// of the class (or the last \ref reset() call), then the \ref reset()
     463    /// function must be called.
     464    ///
     465    /// \param factor The capacity scaling factor. It must be larger than
     466    /// one to use scaling. If it is less or equal to one, then scaling
     467    /// will be disabled.
     468    ///
     469    /// \return \c INFEASIBLE if no feasible flow exists,
     470    /// \n \c OPTIMAL if the problem has optimal solution
     471    /// (i.e. it is feasible and bounded), and the algorithm has found
     472    /// optimal flow and node potentials (primal and dual solutions),
     473    /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
     474    /// and infinite upper bound. It means that the objective function
     475    /// is unbounded on that arc, however, note that it could actually be
     476    /// bounded over the feasible flows, but this algroithm cannot handle
     477    /// these cases.
     478    ///
     479    /// \see ProblemType
     480    /// \see resetParams(), reset()
     481    ProblemType run(int factor = 4) {
     482      _factor = factor;
     483      ProblemType pt = init();
     484      if (pt != OPTIMAL) return pt;
     485      return start();
     486    }
     487
     488    /// \brief Reset all the parameters that have been given before.
     489    ///
     490    /// This function resets all the paramaters that have been given
     491    /// before using functions \ref lowerMap(), \ref upperMap(),
     492    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
     493    ///
     494    /// It is useful for multiple \ref run() calls. Basically, all the given
     495    /// parameters are kept for the next \ref run() call, unless
     496    /// \ref resetParams() or \ref reset() is used.
     497    /// If the underlying digraph was also modified after the construction
     498    /// of the class or the last \ref reset() call, then the \ref reset()
     499    /// function must be used, otherwise \ref resetParams() is sufficient.
     500    ///
     501    /// For example,
     502    /// \code
     503    ///   CapacityScaling<ListDigraph> cs(graph);
     504    ///
     505    ///   // First run
     506    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
     507    ///     .supplyMap(sup).run();
     508    ///
     509    ///   // Run again with modified cost map (resetParams() is not called,
     510    ///   // so only the cost map have to be set again)
     511    ///   cost[e] += 100;
     512    ///   cs.costMap(cost).run();
     513    ///
     514    ///   // Run again from scratch using resetParams()
     515    ///   // (the lower bounds will be set to zero on all arcs)
     516    ///   cs.resetParams();
     517    ///   cs.upperMap(capacity).costMap(cost)
     518    ///     .supplyMap(sup).run();
     519    /// \endcode
     520    ///
     521    /// \return <tt>(*this)</tt>
     522    ///
     523    /// \see reset(), run()
     524    CapacityScaling& resetParams() {
     525      for (int i = 0; i != _node_num; ++i) {
     526        _supply[i] = 0;
     527      }
     528      for (int j = 0; j != _res_arc_num; ++j) {
     529        _lower[j] = 0;
     530        _upper[j] = INF;
     531        _cost[j] = _forward[j] ? 1 : -1;
     532      }
     533      _have_lower = false;
     534      return *this;
     535    }
     536
     537    /// \brief Reset the internal data structures and all the parameters
     538    /// that have been given before.
     539    ///
     540    /// This function resets the internal data structures and all the
     541    /// paramaters that have been given before using functions \ref lowerMap(),
     542    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
     543    ///
     544    /// It is useful for multiple \ref run() calls. Basically, all the given
     545    /// parameters are kept for the next \ref run() call, unless
     546    /// \ref resetParams() or \ref reset() is used.
     547    /// If the underlying digraph was also modified after the construction
     548    /// of the class or the last \ref reset() call, then the \ref reset()
     549    /// function must be used, otherwise \ref resetParams() is sufficient.
     550    ///
     551    /// See \ref resetParams() for examples.
     552    ///
     553    /// \return <tt>(*this)</tt>
     554    ///
     555    /// \see resetParams(), run()
     556    CapacityScaling& reset() {
    318557      // Resize vectors
    319558      _node_num = countNodes(_graph);
     
    379618     
    380619      // 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;
     620      resetParams();
    587621      return *this;
    588622    }
Note: See TracChangeset for help on using the changeset viewer.