COIN-OR::LEMON - Graph Library

Changeset 830:75c97c3786d6 in lemon-1.2


Ignore:
Timestamp:
02/10/10 19:05:20 (14 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.

Files:
5 edited

Legend:

Unmodified
Added
Removed
  • lemon/capacity_scaling.h

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

    r820 r830  
    251251        "The cost type of CycleCanceling must be signed");
    252252
     253      // Reset data structures
     254      reset();
     255    }
     256
     257    /// \name Parameters
     258    /// The parameters of the algorithm can be specified using these
     259    /// functions.
     260
     261    /// @{
     262
     263    /// \brief Set the lower bounds on the arcs.
     264    ///
     265    /// This function sets the lower bounds on the arcs.
     266    /// If it is not used before calling \ref run(), the lower bounds
     267    /// will be set to zero on all arcs.
     268    ///
     269    /// \param map An arc map storing the lower bounds.
     270    /// Its \c Value type must be convertible to the \c Value type
     271    /// of the algorithm.
     272    ///
     273    /// \return <tt>(*this)</tt>
     274    template <typename LowerMap>
     275    CycleCanceling& lowerMap(const LowerMap& map) {
     276      _have_lower = true;
     277      for (ArcIt a(_graph); a != INVALID; ++a) {
     278        _lower[_arc_idf[a]] = map[a];
     279        _lower[_arc_idb[a]] = map[a];
     280      }
     281      return *this;
     282    }
     283
     284    /// \brief Set the upper bounds (capacities) on the arcs.
     285    ///
     286    /// This function sets the upper bounds (capacities) on the arcs.
     287    /// If it is not used before calling \ref run(), the upper bounds
     288    /// will be set to \ref INF on all arcs (i.e. the flow value will be
     289    /// unbounded from above).
     290    ///
     291    /// \param map An arc map storing the upper bounds.
     292    /// Its \c Value type must be convertible to the \c Value type
     293    /// of the algorithm.
     294    ///
     295    /// \return <tt>(*this)</tt>
     296    template<typename UpperMap>
     297    CycleCanceling& upperMap(const UpperMap& map) {
     298      for (ArcIt a(_graph); a != INVALID; ++a) {
     299        _upper[_arc_idf[a]] = map[a];
     300      }
     301      return *this;
     302    }
     303
     304    /// \brief Set the costs of the arcs.
     305    ///
     306    /// This function sets the costs of the arcs.
     307    /// If it is not used before calling \ref run(), the costs
     308    /// will be set to \c 1 on all arcs.
     309    ///
     310    /// \param map An arc map storing the costs.
     311    /// Its \c Value type must be convertible to the \c Cost type
     312    /// of the algorithm.
     313    ///
     314    /// \return <tt>(*this)</tt>
     315    template<typename CostMap>
     316    CycleCanceling& costMap(const CostMap& map) {
     317      for (ArcIt a(_graph); a != INVALID; ++a) {
     318        _cost[_arc_idf[a]] =  map[a];
     319        _cost[_arc_idb[a]] = -map[a];
     320      }
     321      return *this;
     322    }
     323
     324    /// \brief Set the supply values of the nodes.
     325    ///
     326    /// This function sets the supply values of the nodes.
     327    /// If neither this function nor \ref stSupply() is used before
     328    /// calling \ref run(), the supply of each node will be set to zero.
     329    ///
     330    /// \param map A node map storing the supply values.
     331    /// Its \c Value type must be convertible to the \c Value type
     332    /// of the algorithm.
     333    ///
     334    /// \return <tt>(*this)</tt>
     335    template<typename SupplyMap>
     336    CycleCanceling& supplyMap(const SupplyMap& map) {
     337      for (NodeIt n(_graph); n != INVALID; ++n) {
     338        _supply[_node_id[n]] = map[n];
     339      }
     340      return *this;
     341    }
     342
     343    /// \brief Set single source and target nodes and a supply value.
     344    ///
     345    /// This function sets a single source node and a single target node
     346    /// and the required flow value.
     347    /// If neither this function nor \ref supplyMap() is used before
     348    /// calling \ref run(), the supply of each node will be set to zero.
     349    ///
     350    /// Using this function has the same effect as using \ref supplyMap()
     351    /// with such a map in which \c k is assigned to \c s, \c -k is
     352    /// assigned to \c t and all other nodes have zero supply value.
     353    ///
     354    /// \param s The source node.
     355    /// \param t The target node.
     356    /// \param k The required amount of flow from node \c s to node \c t
     357    /// (i.e. the supply of \c s and the demand of \c t).
     358    ///
     359    /// \return <tt>(*this)</tt>
     360    CycleCanceling& stSupply(const Node& s, const Node& t, Value k) {
     361      for (int i = 0; i != _res_node_num; ++i) {
     362        _supply[i] = 0;
     363      }
     364      _supply[_node_id[s]] =  k;
     365      _supply[_node_id[t]] = -k;
     366      return *this;
     367    }
     368   
     369    /// @}
     370
     371    /// \name Execution control
     372    /// The algorithm can be executed using \ref run().
     373
     374    /// @{
     375
     376    /// \brief Run the algorithm.
     377    ///
     378    /// This function runs the algorithm.
     379    /// The paramters can be specified using functions \ref lowerMap(),
     380    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
     381    /// For example,
     382    /// \code
     383    ///   CycleCanceling<ListDigraph> cc(graph);
     384    ///   cc.lowerMap(lower).upperMap(upper).costMap(cost)
     385    ///     .supplyMap(sup).run();
     386    /// \endcode
     387    ///
     388    /// This function can be called more than once. All the given parameters
     389    /// are kept for the next call, unless \ref resetParams() or \ref reset()
     390    /// is used, thus only the modified parameters have to be set again.
     391    /// If the underlying digraph was also modified after the construction
     392    /// of the class (or the last \ref reset() call), then the \ref reset()
     393    /// function must be called.
     394    ///
     395    /// \param method The cycle-canceling method that will be used.
     396    /// For more information, see \ref Method.
     397    ///
     398    /// \return \c INFEASIBLE if no feasible flow exists,
     399    /// \n \c OPTIMAL if the problem has optimal solution
     400    /// (i.e. it is feasible and bounded), and the algorithm has found
     401    /// optimal flow and node potentials (primal and dual solutions),
     402    /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
     403    /// and infinite upper bound. It means that the objective function
     404    /// is unbounded on that arc, however, note that it could actually be
     405    /// bounded over the feasible flows, but this algroithm cannot handle
     406    /// these cases.
     407    ///
     408    /// \see ProblemType, Method
     409    /// \see resetParams(), reset()
     410    ProblemType run(Method method = CANCEL_AND_TIGHTEN) {
     411      ProblemType pt = init();
     412      if (pt != OPTIMAL) return pt;
     413      start(method);
     414      return OPTIMAL;
     415    }
     416
     417    /// \brief Reset all the parameters that have been given before.
     418    ///
     419    /// This function resets all the paramaters that have been given
     420    /// before using functions \ref lowerMap(), \ref upperMap(),
     421    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
     422    ///
     423    /// It is useful for multiple \ref run() calls. Basically, all the given
     424    /// parameters are kept for the next \ref run() call, unless
     425    /// \ref resetParams() or \ref reset() is used.
     426    /// If the underlying digraph was also modified after the construction
     427    /// of the class or the last \ref reset() call, then the \ref reset()
     428    /// function must be used, otherwise \ref resetParams() is sufficient.
     429    ///
     430    /// For example,
     431    /// \code
     432    ///   CycleCanceling<ListDigraph> cs(graph);
     433    ///
     434    ///   // First run
     435    ///   cc.lowerMap(lower).upperMap(upper).costMap(cost)
     436    ///     .supplyMap(sup).run();
     437    ///
     438    ///   // Run again with modified cost map (resetParams() is not called,
     439    ///   // so only the cost map have to be set again)
     440    ///   cost[e] += 100;
     441    ///   cc.costMap(cost).run();
     442    ///
     443    ///   // Run again from scratch using resetParams()
     444    ///   // (the lower bounds will be set to zero on all arcs)
     445    ///   cc.resetParams();
     446    ///   cc.upperMap(capacity).costMap(cost)
     447    ///     .supplyMap(sup).run();
     448    /// \endcode
     449    ///
     450    /// \return <tt>(*this)</tt>
     451    ///
     452    /// \see reset(), run()
     453    CycleCanceling& resetParams() {
     454      for (int i = 0; i != _res_node_num; ++i) {
     455        _supply[i] = 0;
     456      }
     457      int limit = _first_out[_root];
     458      for (int j = 0; j != limit; ++j) {
     459        _lower[j] = 0;
     460        _upper[j] = INF;
     461        _cost[j] = _forward[j] ? 1 : -1;
     462      }
     463      for (int j = limit; j != _res_arc_num; ++j) {
     464        _lower[j] = 0;
     465        _upper[j] = INF;
     466        _cost[j] = 0;
     467        _cost[_reverse[j]] = 0;
     468      }     
     469      _have_lower = false;
     470      return *this;
     471    }
     472
     473    /// \brief Reset the internal data structures and all the parameters
     474    /// that have been given before.
     475    ///
     476    /// This function resets the internal data structures and all the
     477    /// paramaters that have been given before using functions \ref lowerMap(),
     478    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
     479    ///
     480    /// It is useful for multiple \ref run() calls. Basically, all the given
     481    /// parameters are kept for the next \ref run() call, unless
     482    /// \ref resetParams() or \ref reset() is used.
     483    /// If the underlying digraph was also modified after the construction
     484    /// of the class or the last \ref reset() call, then the \ref reset()
     485    /// function must be used, otherwise \ref resetParams() is sufficient.
     486    ///
     487    /// See \ref resetParams() for examples.
     488    ///
     489    /// \return <tt>(*this)</tt>
     490    ///
     491    /// \see resetParams(), run()
     492    CycleCanceling& reset() {
    253493      // Resize vectors
    254494      _node_num = countNodes(_graph);
     
    316556     
    317557      // Reset parameters
    318       reset();
    319     }
    320 
    321     /// \name Parameters
    322     /// The parameters of the algorithm can be specified using these
    323     /// functions.
    324 
    325     /// @{
    326 
    327     /// \brief Set the lower bounds on the arcs.
    328     ///
    329     /// This function sets the lower bounds on the arcs.
    330     /// If it is not used before calling \ref run(), the lower bounds
    331     /// will be set to zero on all arcs.
    332     ///
    333     /// \param map An arc map storing the lower bounds.
    334     /// Its \c Value type must be convertible to the \c Value type
    335     /// of the algorithm.
    336     ///
    337     /// \return <tt>(*this)</tt>
    338     template <typename LowerMap>
    339     CycleCanceling& lowerMap(const LowerMap& map) {
    340       _have_lower = true;
    341       for (ArcIt a(_graph); a != INVALID; ++a) {
    342         _lower[_arc_idf[a]] = map[a];
    343         _lower[_arc_idb[a]] = map[a];
    344       }
    345       return *this;
    346     }
    347 
    348     /// \brief Set the upper bounds (capacities) on the arcs.
    349     ///
    350     /// This function sets the upper bounds (capacities) on the arcs.
    351     /// If it is not used before calling \ref run(), the upper bounds
    352     /// will be set to \ref INF on all arcs (i.e. the flow value will be
    353     /// unbounded from above).
    354     ///
    355     /// \param map An arc map storing the upper bounds.
    356     /// Its \c Value type must be convertible to the \c Value type
    357     /// of the algorithm.
    358     ///
    359     /// \return <tt>(*this)</tt>
    360     template<typename UpperMap>
    361     CycleCanceling& upperMap(const UpperMap& map) {
    362       for (ArcIt a(_graph); a != INVALID; ++a) {
    363         _upper[_arc_idf[a]] = map[a];
    364       }
    365       return *this;
    366     }
    367 
    368     /// \brief Set the costs of the arcs.
    369     ///
    370     /// This function sets the costs of the arcs.
    371     /// If it is not used before calling \ref run(), the costs
    372     /// will be set to \c 1 on all arcs.
    373     ///
    374     /// \param map An arc map storing the costs.
    375     /// Its \c Value type must be convertible to the \c Cost type
    376     /// of the algorithm.
    377     ///
    378     /// \return <tt>(*this)</tt>
    379     template<typename CostMap>
    380     CycleCanceling& costMap(const CostMap& map) {
    381       for (ArcIt a(_graph); a != INVALID; ++a) {
    382         _cost[_arc_idf[a]] =  map[a];
    383         _cost[_arc_idb[a]] = -map[a];
    384       }
    385       return *this;
    386     }
    387 
    388     /// \brief Set the supply values of the nodes.
    389     ///
    390     /// This function sets the supply values of the nodes.
    391     /// If neither this function nor \ref stSupply() is used before
    392     /// calling \ref run(), the supply of each node will be set to zero.
    393     ///
    394     /// \param map A node map storing the supply values.
    395     /// Its \c Value type must be convertible to the \c Value type
    396     /// of the algorithm.
    397     ///
    398     /// \return <tt>(*this)</tt>
    399     template<typename SupplyMap>
    400     CycleCanceling& supplyMap(const SupplyMap& map) {
    401       for (NodeIt n(_graph); n != INVALID; ++n) {
    402         _supply[_node_id[n]] = map[n];
    403       }
    404       return *this;
    405     }
    406 
    407     /// \brief Set single source and target nodes and a supply value.
    408     ///
    409     /// This function sets a single source node and a single target node
    410     /// and the required flow value.
    411     /// If neither this function nor \ref supplyMap() is used before
    412     /// calling \ref run(), the supply of each node will be set to zero.
    413     ///
    414     /// Using this function has the same effect as using \ref supplyMap()
    415     /// with such a map in which \c k is assigned to \c s, \c -k is
    416     /// assigned to \c t and all other nodes have zero supply value.
    417     ///
    418     /// \param s The source node.
    419     /// \param t The target node.
    420     /// \param k The required amount of flow from node \c s to node \c t
    421     /// (i.e. the supply of \c s and the demand of \c t).
    422     ///
    423     /// \return <tt>(*this)</tt>
    424     CycleCanceling& stSupply(const Node& s, const Node& t, Value k) {
    425       for (int i = 0; i != _res_node_num; ++i) {
    426         _supply[i] = 0;
    427       }
    428       _supply[_node_id[s]] =  k;
    429       _supply[_node_id[t]] = -k;
    430       return *this;
    431     }
    432    
    433     /// @}
    434 
    435     /// \name Execution control
    436     /// The algorithm can be executed using \ref run().
    437 
    438     /// @{
    439 
    440     /// \brief Run the algorithm.
    441     ///
    442     /// This function runs the algorithm.
    443     /// The paramters can be specified using functions \ref lowerMap(),
    444     /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
    445     /// For example,
    446     /// \code
    447     ///   CycleCanceling<ListDigraph> cc(graph);
    448     ///   cc.lowerMap(lower).upperMap(upper).costMap(cost)
    449     ///     .supplyMap(sup).run();
    450     /// \endcode
    451     ///
    452     /// This function can be called more than once. All the parameters
    453     /// that have been given are kept for the next call, unless
    454     /// \ref reset() is called, thus only the modified parameters
    455     /// have to be set again. See \ref reset() for examples.
    456     /// However, the underlying digraph must not be modified after this
    457     /// class have been constructed, since it copies and extends the graph.
    458     ///
    459     /// \param method The cycle-canceling method that will be used.
    460     /// For more information, see \ref Method.
    461     ///
    462     /// \return \c INFEASIBLE if no feasible flow exists,
    463     /// \n \c OPTIMAL if the problem has optimal solution
    464     /// (i.e. it is feasible and bounded), and the algorithm has found
    465     /// optimal flow and node potentials (primal and dual solutions),
    466     /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
    467     /// and infinite upper bound. It means that the objective function
    468     /// is unbounded on that arc, however, note that it could actually be
    469     /// bounded over the feasible flows, but this algroithm cannot handle
    470     /// these cases.
    471     ///
    472     /// \see ProblemType, Method
    473     ProblemType run(Method method = CANCEL_AND_TIGHTEN) {
    474       ProblemType pt = init();
    475       if (pt != OPTIMAL) return pt;
    476       start(method);
    477       return OPTIMAL;
    478     }
    479 
    480     /// \brief Reset all the parameters that have been given before.
    481     ///
    482     /// This function resets all the paramaters that have been given
    483     /// before using functions \ref lowerMap(), \ref upperMap(),
    484     /// \ref costMap(), \ref supplyMap(), \ref stSupply().
    485     ///
    486     /// It is useful for multiple run() calls. If this function is not
    487     /// used, all the parameters given before are kept for the next
    488     /// \ref run() call.
    489     /// However, the underlying digraph must not be modified after this
    490     /// class have been constructed, since it copies and extends the graph.
    491     ///
    492     /// For example,
    493     /// \code
    494     ///   CycleCanceling<ListDigraph> cs(graph);
    495     ///
    496     ///   // First run
    497     ///   cc.lowerMap(lower).upperMap(upper).costMap(cost)
    498     ///     .supplyMap(sup).run();
    499     ///
    500     ///   // Run again with modified cost map (reset() is not called,
    501     ///   // so only the cost map have to be set again)
    502     ///   cost[e] += 100;
    503     ///   cc.costMap(cost).run();
    504     ///
    505     ///   // Run again from scratch using reset()
    506     ///   // (the lower bounds will be set to zero on all arcs)
    507     ///   cc.reset();
    508     ///   cc.upperMap(capacity).costMap(cost)
    509     ///     .supplyMap(sup).run();
    510     /// \endcode
    511     ///
    512     /// \return <tt>(*this)</tt>
    513     CycleCanceling& reset() {
    514       for (int i = 0; i != _res_node_num; ++i) {
    515         _supply[i] = 0;
    516       }
    517       int limit = _first_out[_root];
    518       for (int j = 0; j != limit; ++j) {
    519         _lower[j] = 0;
    520         _upper[j] = INF;
    521         _cost[j] = _forward[j] ? 1 : -1;
    522       }
    523       for (int j = limit; j != _res_arc_num; ++j) {
    524         _lower[j] = 0;
    525         _upper[j] = INF;
    526         _cost[j] = 0;
    527         _cost[_reverse[j]] = 0;
    528       }     
    529       _have_lower = false;
     558      resetParams();
    530559      return *this;
    531560    }
  • lemon/network_simplex.h

    r812 r830  
    195195    IntVector _source;
    196196    IntVector _target;
     197    bool _arc_mixing;
    197198
    198199    // Node and arc data
     
    634635    NetworkSimplex(const GR& graph, bool arc_mixing = false) :
    635636      _graph(graph), _node_id(graph), _arc_id(graph),
     637      _arc_mixing(arc_mixing),
    636638      MAX(std::numeric_limits<Value>::max()),
    637639      INF(std::numeric_limits<Value>::has_infinity ?
     
    644646        "The cost type of NetworkSimplex must be signed");
    645647       
    646       // Resize vectors
    647       _node_num = countNodes(_graph);
    648       _arc_num = countArcs(_graph);
    649       int all_node_num = _node_num + 1;
    650       int max_arc_num = _arc_num + 2 * _node_num;
    651 
    652       _source.resize(max_arc_num);
    653       _target.resize(max_arc_num);
    654 
    655       _lower.resize(_arc_num);
    656       _upper.resize(_arc_num);
    657       _cap.resize(max_arc_num);
    658       _cost.resize(max_arc_num);
    659       _supply.resize(all_node_num);
    660       _flow.resize(max_arc_num);
    661       _pi.resize(all_node_num);
    662 
    663       _parent.resize(all_node_num);
    664       _pred.resize(all_node_num);
    665       _forward.resize(all_node_num);
    666       _thread.resize(all_node_num);
    667       _rev_thread.resize(all_node_num);
    668       _succ_num.resize(all_node_num);
    669       _last_succ.resize(all_node_num);
    670       _state.resize(max_arc_num);
    671 
    672       // Copy the graph
    673       int i = 0;
    674       for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
    675         _node_id[n] = i;
    676       }
    677       if (arc_mixing) {
    678         // Store the arcs in a mixed order
    679         int k = std::max(int(std::sqrt(double(_arc_num))), 10);
    680         int i = 0, j = 0;
    681         for (ArcIt a(_graph); a != INVALID; ++a) {
    682           _arc_id[a] = i;
    683           _source[i] = _node_id[_graph.source(a)];
    684           _target[i] = _node_id[_graph.target(a)];
    685           if ((i += k) >= _arc_num) i = ++j;
    686         }
    687       } else {
    688         // Store the arcs in the original order
    689         int i = 0;
    690         for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
    691           _arc_id[a] = i;
    692           _source[i] = _node_id[_graph.source(a)];
    693           _target[i] = _node_id[_graph.target(a)];
    694         }
    695       }
    696      
    697       // Reset parameters
     648      // Reset data structures
    698649      reset();
    699650    }
     
    843794    /// \endcode
    844795    ///
    845     /// This function can be called more than once. All the parameters
    846     /// that have been given are kept for the next call, unless
    847     /// \ref reset() is called, thus only the modified parameters
    848     /// have to be set again. See \ref reset() for examples.
    849     /// However, the underlying digraph must not be modified after this
    850     /// class have been constructed, since it copies and extends the graph.
     796    /// This function can be called more than once. All the given parameters
     797    /// are kept for the next call, unless \ref resetParams() or \ref reset()
     798    /// is used, thus only the modified parameters have to be set again.
     799    /// If the underlying digraph was also modified after the construction
     800    /// of the class (or the last \ref reset() call), then the \ref reset()
     801    /// function must be called.
    851802    ///
    852803    /// \param pivot_rule The pivot rule that will be used during the
     
    862813    ///
    863814    /// \see ProblemType, PivotRule
     815    /// \see resetParams(), reset()
    864816    ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {
    865817      if (!init()) return INFEASIBLE;
     
    873825    /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType().
    874826    ///
    875     /// It is useful for multiple run() calls. If this function is not
    876     /// used, all the parameters given before are kept for the next
    877     /// \ref run() call.
    878     /// However, the underlying digraph must not be modified after this
    879     /// class have been constructed, since it copies and extends the graph.
     827    /// It is useful for multiple \ref run() calls. Basically, all the given
     828    /// parameters are kept for the next \ref run() call, unless
     829    /// \ref resetParams() or \ref reset() is used.
     830    /// If the underlying digraph was also modified after the construction
     831    /// of the class or the last \ref reset() call, then the \ref reset()
     832    /// function must be used, otherwise \ref resetParams() is sufficient.
    880833    ///
    881834    /// For example,
     
    887840    ///     .supplyMap(sup).run();
    888841    ///
    889     ///   // Run again with modified cost map (reset() is not called,
     842    ///   // Run again with modified cost map (resetParams() is not called,
    890843    ///   // so only the cost map have to be set again)
    891844    ///   cost[e] += 100;
    892845    ///   ns.costMap(cost).run();
    893846    ///
    894     ///   // Run again from scratch using reset()
     847    ///   // Run again from scratch using resetParams()
    895848    ///   // (the lower bounds will be set to zero on all arcs)
    896     ///   ns.reset();
     849    ///   ns.resetParams();
    897850    ///   ns.upperMap(capacity).costMap(cost)
    898851    ///     .supplyMap(sup).run();
     
    900853    ///
    901854    /// \return <tt>(*this)</tt>
    902     NetworkSimplex& reset() {
     855    ///
     856    /// \see reset(), run()
     857    NetworkSimplex& resetParams() {
    903858      for (int i = 0; i != _node_num; ++i) {
    904859        _supply[i] = 0;
     
    914869    }
    915870
     871    /// \brief Reset the internal data structures and all the parameters
     872    /// that have been given before.
     873    ///
     874    /// This function resets the internal data structures and all the
     875    /// paramaters that have been given before using functions \ref lowerMap(),
     876    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(),
     877    /// \ref supplyType().
     878    ///
     879    /// It is useful for multiple \ref run() calls. Basically, all the given
     880    /// parameters are kept for the next \ref run() call, unless
     881    /// \ref resetParams() or \ref reset() is used.
     882    /// If the underlying digraph was also modified after the construction
     883    /// of the class or the last \ref reset() call, then the \ref reset()
     884    /// function must be used, otherwise \ref resetParams() is sufficient.
     885    ///
     886    /// See \ref resetParams() for examples.
     887    ///
     888    /// \return <tt>(*this)</tt>
     889    ///
     890    /// \see resetParams(), run()
     891    NetworkSimplex& reset() {
     892      // Resize vectors
     893      _node_num = countNodes(_graph);
     894      _arc_num = countArcs(_graph);
     895      int all_node_num = _node_num + 1;
     896      int max_arc_num = _arc_num + 2 * _node_num;
     897
     898      _source.resize(max_arc_num);
     899      _target.resize(max_arc_num);
     900
     901      _lower.resize(_arc_num);
     902      _upper.resize(_arc_num);
     903      _cap.resize(max_arc_num);
     904      _cost.resize(max_arc_num);
     905      _supply.resize(all_node_num);
     906      _flow.resize(max_arc_num);
     907      _pi.resize(all_node_num);
     908
     909      _parent.resize(all_node_num);
     910      _pred.resize(all_node_num);
     911      _forward.resize(all_node_num);
     912      _thread.resize(all_node_num);
     913      _rev_thread.resize(all_node_num);
     914      _succ_num.resize(all_node_num);
     915      _last_succ.resize(all_node_num);
     916      _state.resize(max_arc_num);
     917
     918      // Copy the graph
     919      int i = 0;
     920      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
     921        _node_id[n] = i;
     922      }
     923      if (_arc_mixing) {
     924        // Store the arcs in a mixed order
     925        int k = std::max(int(std::sqrt(double(_arc_num))), 10);
     926        int i = 0, j = 0;
     927        for (ArcIt a(_graph); a != INVALID; ++a) {
     928          _arc_id[a] = i;
     929          _source[i] = _node_id[_graph.source(a)];
     930          _target[i] = _node_id[_graph.target(a)];
     931          if ((i += k) >= _arc_num) i = ++j;
     932        }
     933      } else {
     934        // Store the arcs in the original order
     935        int i = 0;
     936        for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
     937          _arc_id[a] = i;
     938          _source[i] = _node_id[_graph.source(a)];
     939          _target[i] = _node_id[_graph.target(a)];
     940        }
     941      }
     942     
     943      // Reset parameters
     944      resetParams();
     945      return *this;
     946    }
     947   
    916948    /// @}
    917949
  • test/min_cost_flow_test.cc

    r819 r830  
    158158      const MCF& const_mcf = mcf;
    159159
    160       b = mcf.reset()
     160      b = mcf.reset().resetParams()
    161161             .lowerMap(me.lower)
    162162             .upperMap(me.upper)
     
    347347  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s2,
    348348           mcf1.OPTIMAL, true,     8010, test_str + "-4");
    349   mcf1.reset().supplyMap(s1);
     349  mcf1.resetParams().supplyMap(s1);
    350350  checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s1,
    351351           mcf1.OPTIMAL, true,       74, test_str + "-5");
     
    364364
    365365  // Tests for the GEQ form
    366   mcf1.reset().upperMap(u).costMap(c).supplyMap(s5);
     366  mcf1.resetParams().upperMap(u).costMap(c).supplyMap(s5);
    367367  checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s5,
    368368           mcf1.OPTIMAL, true,     3530, test_str + "-10", GEQ);
     
    381381  checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u2, neg1_c, neg1_s,
    382382           mcf2.OPTIMAL, true,   -40000, test_str + "-14");
    383   mcf2.reset().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s);
     383  mcf2.resetParams().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s);
    384384  checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l2, neg1_u1, neg1_c, neg1_s,
    385385           mcf2.UNBOUNDED, false,     0, test_str + "-15");
Note: See TracChangeset for help on using the changeset viewer.