COIN-OR::LEMON - Graph Library

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/capacity_scaling.h

    r887 r898  
    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    }
Note: See TracChangeset for help on using the changeset viewer.