COIN-OR::LEMON - Graph Library

Changeset 898:75c97c3786d6 in lemon for lemon/cycle_canceling.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/cycle_canceling.h

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