COIN-OR::LEMON - Graph Library

Changeset 830:75c97c3786d6 in lemon-1.2 for lemon/cost_scaling.h


Ignore:
Timestamp:
02/10/10 19:05:20 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Handle graph changes in the MCF algorithms (#327)

The reset() functions are renamed to resetParams() and the new reset()
functions handle the graph chnages, as well.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/cost_scaling.h

    r821 r830  
    333333      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
    334334        "The cost type of CostScaling must be signed");
    335 
     335     
     336      // Reset data structures
     337      reset();
     338    }
     339
     340    /// \name Parameters
     341    /// The parameters of the algorithm can be specified using these
     342    /// functions.
     343
     344    /// @{
     345
     346    /// \brief Set the lower bounds on the arcs.
     347    ///
     348    /// This function sets the lower bounds on the arcs.
     349    /// If it is not used before calling \ref run(), the lower bounds
     350    /// will be set to zero on all arcs.
     351    ///
     352    /// \param map An arc map storing the lower bounds.
     353    /// Its \c Value type must be convertible to the \c Value type
     354    /// of the algorithm.
     355    ///
     356    /// \return <tt>(*this)</tt>
     357    template <typename LowerMap>
     358    CostScaling& lowerMap(const LowerMap& map) {
     359      _have_lower = true;
     360      for (ArcIt a(_graph); a != INVALID; ++a) {
     361        _lower[_arc_idf[a]] = map[a];
     362        _lower[_arc_idb[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    CostScaling& 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    CostScaling& costMap(const CostMap& map) {
     400      for (ArcIt a(_graph); a != INVALID; ++a) {
     401        _scost[_arc_idf[a]] =  map[a];
     402        _scost[_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    CostScaling& 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 such 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    CostScaling& stSupply(const Node& s, const Node& t, Value k) {
     444      for (int i = 0; i != _res_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    ///   CostScaling<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 method The internal method that will be used in the
     479    /// algorithm. For more information, see \ref Method.
     480    /// \param factor The cost scaling factor. It must be larger than one.
     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, Method
     493    /// \see resetParams(), reset()
     494    ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
     495      _alpha = factor;
     496      ProblemType pt = init();
     497      if (pt != OPTIMAL) return pt;
     498      start(method);
     499      return OPTIMAL;
     500    }
     501
     502    /// \brief Reset all the parameters that have been given before.
     503    ///
     504    /// This function resets all the paramaters that have been given
     505    /// before using functions \ref lowerMap(), \ref upperMap(),
     506    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
     507    ///
     508    /// It is useful for multiple \ref run() calls. Basically, all the given
     509    /// parameters are kept for the next \ref run() call, unless
     510    /// \ref resetParams() or \ref reset() is used.
     511    /// If the underlying digraph was also modified after the construction
     512    /// of the class or the last \ref reset() call, then the \ref reset()
     513    /// function must be used, otherwise \ref resetParams() is sufficient.
     514    ///
     515    /// For example,
     516    /// \code
     517    ///   CostScaling<ListDigraph> cs(graph);
     518    ///
     519    ///   // First run
     520    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
     521    ///     .supplyMap(sup).run();
     522    ///
     523    ///   // Run again with modified cost map (resetParams() is not called,
     524    ///   // so only the cost map have to be set again)
     525    ///   cost[e] += 100;
     526    ///   cs.costMap(cost).run();
     527    ///
     528    ///   // Run again from scratch using resetParams()
     529    ///   // (the lower bounds will be set to zero on all arcs)
     530    ///   cs.resetParams();
     531    ///   cs.upperMap(capacity).costMap(cost)
     532    ///     .supplyMap(sup).run();
     533    /// \endcode
     534    ///
     535    /// \return <tt>(*this)</tt>
     536    ///
     537    /// \see reset(), run()
     538    CostScaling& resetParams() {
     539      for (int i = 0; i != _res_node_num; ++i) {
     540        _supply[i] = 0;
     541      }
     542      int limit = _first_out[_root];
     543      for (int j = 0; j != limit; ++j) {
     544        _lower[j] = 0;
     545        _upper[j] = INF;
     546        _scost[j] = _forward[j] ? 1 : -1;
     547      }
     548      for (int j = limit; j != _res_arc_num; ++j) {
     549        _lower[j] = 0;
     550        _upper[j] = INF;
     551        _scost[j] = 0;
     552        _scost[_reverse[j]] = 0;
     553      }     
     554      _have_lower = false;
     555      return *this;
     556    }
     557
     558    /// \brief Reset all the parameters that have been given before.
     559    ///
     560    /// This function resets all the paramaters that have been given
     561    /// before using functions \ref lowerMap(), \ref upperMap(),
     562    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
     563    ///
     564    /// It is useful for multiple run() calls. If this function is not
     565    /// used, all the parameters given before are kept for the next
     566    /// \ref run() call.
     567    /// However, the underlying digraph must not be modified after this
     568    /// class have been constructed, since it copies and extends the graph.
     569    /// \return <tt>(*this)</tt>
     570    CostScaling& reset() {
    336571      // Resize vectors
    337572      _node_num = countNodes(_graph);
     
    401636     
    402637      // Reset parameters
    403       reset();
    404     }
    405 
    406     /// \name Parameters
    407     /// The parameters of the algorithm can be specified using these
    408     /// functions.
    409 
    410     /// @{
    411 
    412     /// \brief Set the lower bounds on the arcs.
    413     ///
    414     /// This function sets the lower bounds on the arcs.
    415     /// If it is not used before calling \ref run(), the lower bounds
    416     /// will be set to zero on all arcs.
    417     ///
    418     /// \param map An arc map storing the lower 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 LowerMap>
    424     CostScaling& lowerMap(const LowerMap& map) {
    425       _have_lower = true;
    426       for (ArcIt a(_graph); a != INVALID; ++a) {
    427         _lower[_arc_idf[a]] = map[a];
    428         _lower[_arc_idb[a]] = map[a];
    429       }
    430       return *this;
    431     }
    432 
    433     /// \brief Set the upper bounds (capacities) on the arcs.
    434     ///
    435     /// This function sets the upper bounds (capacities) on the arcs.
    436     /// If it is not used before calling \ref run(), the upper bounds
    437     /// will be set to \ref INF on all arcs (i.e. the flow value will be
    438     /// unbounded from above).
    439     ///
    440     /// \param map An arc map storing the upper bounds.
    441     /// Its \c Value type must be convertible to the \c Value type
    442     /// of the algorithm.
    443     ///
    444     /// \return <tt>(*this)</tt>
    445     template<typename UpperMap>
    446     CostScaling& upperMap(const UpperMap& map) {
    447       for (ArcIt a(_graph); a != INVALID; ++a) {
    448         _upper[_arc_idf[a]] = map[a];
    449       }
    450       return *this;
    451     }
    452 
    453     /// \brief Set the costs of the arcs.
    454     ///
    455     /// This function sets the costs of the arcs.
    456     /// If it is not used before calling \ref run(), the costs
    457     /// will be set to \c 1 on all arcs.
    458     ///
    459     /// \param map An arc map storing the costs.
    460     /// Its \c Value type must be convertible to the \c Cost type
    461     /// of the algorithm.
    462     ///
    463     /// \return <tt>(*this)</tt>
    464     template<typename CostMap>
    465     CostScaling& costMap(const CostMap& map) {
    466       for (ArcIt a(_graph); a != INVALID; ++a) {
    467         _scost[_arc_idf[a]] =  map[a];
    468         _scost[_arc_idb[a]] = -map[a];
    469       }
    470       return *this;
    471     }
    472 
    473     /// \brief Set the supply values of the nodes.
    474     ///
    475     /// This function sets the supply values of the nodes.
    476     /// If neither this function nor \ref stSupply() is used before
    477     /// calling \ref run(), the supply of each node will be set to zero.
    478     ///
    479     /// \param map A node map storing the supply values.
    480     /// Its \c Value type must be convertible to the \c Value type
    481     /// of the algorithm.
    482     ///
    483     /// \return <tt>(*this)</tt>
    484     template<typename SupplyMap>
    485     CostScaling& supplyMap(const SupplyMap& map) {
    486       for (NodeIt n(_graph); n != INVALID; ++n) {
    487         _supply[_node_id[n]] = map[n];
    488       }
    489       return *this;
    490     }
    491 
    492     /// \brief Set single source and target nodes and a supply value.
    493     ///
    494     /// This function sets a single source node and a single target node
    495     /// and the required flow value.
    496     /// If neither this function nor \ref supplyMap() is used before
    497     /// calling \ref run(), the supply of each node will be set to zero.
    498     ///
    499     /// Using this function has the same effect as using \ref supplyMap()
    500     /// with such a map in which \c k is assigned to \c s, \c -k is
    501     /// assigned to \c t and all other nodes have zero supply value.
    502     ///
    503     /// \param s The source node.
    504     /// \param t The target node.
    505     /// \param k The required amount of flow from node \c s to node \c t
    506     /// (i.e. the supply of \c s and the demand of \c t).
    507     ///
    508     /// \return <tt>(*this)</tt>
    509     CostScaling& stSupply(const Node& s, const Node& t, Value k) {
    510       for (int i = 0; i != _res_node_num; ++i) {
    511         _supply[i] = 0;
    512       }
    513       _supply[_node_id[s]] =  k;
    514       _supply[_node_id[t]] = -k;
    515       return *this;
    516     }
    517    
    518     /// @}
    519 
    520     /// \name Execution control
    521     /// The algorithm can be executed using \ref run().
    522 
    523     /// @{
    524 
    525     /// \brief Run the algorithm.
    526     ///
    527     /// This function runs the algorithm.
    528     /// The paramters can be specified using functions \ref lowerMap(),
    529     /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
    530     /// For example,
    531     /// \code
    532     ///   CostScaling<ListDigraph> cs(graph);
    533     ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
    534     ///     .supplyMap(sup).run();
    535     /// \endcode
    536     ///
    537     /// This function can be called more than once. All the parameters
    538     /// that have been given are kept for the next call, unless
    539     /// \ref reset() is called, thus only the modified parameters
    540     /// have to be set again. See \ref reset() for examples.
    541     /// However, the underlying digraph must not be modified after this
    542     /// class have been constructed, since it copies and extends the graph.
    543     ///
    544     /// \param method The internal method that will be used in the
    545     /// algorithm. For more information, see \ref Method.
    546     /// \param factor The cost scaling factor. It must be larger than one.
    547     ///
    548     /// \return \c INFEASIBLE if no feasible flow exists,
    549     /// \n \c OPTIMAL if the problem has optimal solution
    550     /// (i.e. it is feasible and bounded), and the algorithm has found
    551     /// optimal flow and node potentials (primal and dual solutions),
    552     /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
    553     /// and infinite upper bound. It means that the objective function
    554     /// is unbounded on that arc, however, note that it could actually be
    555     /// bounded over the feasible flows, but this algroithm cannot handle
    556     /// these cases.
    557     ///
    558     /// \see ProblemType, Method
    559     ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
    560       _alpha = factor;
    561       ProblemType pt = init();
    562       if (pt != OPTIMAL) return pt;
    563       start(method);
    564       return OPTIMAL;
    565     }
    566 
    567     /// \brief Reset all the parameters that have been given before.
    568     ///
    569     /// This function resets all the paramaters that have been given
    570     /// before using functions \ref lowerMap(), \ref upperMap(),
    571     /// \ref costMap(), \ref supplyMap(), \ref stSupply().
    572     ///
    573     /// It is useful for multiple run() calls. If this function is not
    574     /// used, all the parameters given before are kept for the next
    575     /// \ref run() call.
    576     /// However, the underlying digraph must not be modified after this
    577     /// class have been constructed, since it copies and extends the graph.
    578     ///
    579     /// For example,
    580     /// \code
    581     ///   CostScaling<ListDigraph> cs(graph);
    582     ///
    583     ///   // First run
    584     ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
    585     ///     .supplyMap(sup).run();
    586     ///
    587     ///   // Run again with modified cost map (reset() is not called,
    588     ///   // so only the cost map have to be set again)
    589     ///   cost[e] += 100;
    590     ///   cs.costMap(cost).run();
    591     ///
    592     ///   // Run again from scratch using reset()
    593     ///   // (the lower bounds will be set to zero on all arcs)
    594     ///   cs.reset();
    595     ///   cs.upperMap(capacity).costMap(cost)
    596     ///     .supplyMap(sup).run();
    597     /// \endcode
    598     ///
    599     /// \return <tt>(*this)</tt>
    600     CostScaling& reset() {
    601       for (int i = 0; i != _res_node_num; ++i) {
    602         _supply[i] = 0;
    603       }
    604       int limit = _first_out[_root];
    605       for (int j = 0; j != limit; ++j) {
    606         _lower[j] = 0;
    607         _upper[j] = INF;
    608         _scost[j] = _forward[j] ? 1 : -1;
    609       }
    610       for (int j = limit; j != _res_arc_num; ++j) {
    611         _lower[j] = 0;
    612         _upper[j] = INF;
    613         _scost[j] = 0;
    614         _scost[_reverse[j]] = 0;
    615       }     
    616       _have_lower = false;
     638      resetParams();
    617639      return *this;
    618640    }
Note: See TracChangeset for help on using the changeset viewer.