COIN-OR::LEMON - Graph Library

Changeset 911:2914b6f0fde0 in lemon for lemon/cycle_canceling.h


Ignore:
Timestamp:
02/26/10 14:00:20 (10 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
909:2c35bef44dd1 (diff), 910:f3bc4e9b5f3a (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge #340

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/cycle_canceling.h

    r898 r911  
    145145   
    146146    typedef std::vector<int> IntVector;
    147     typedef std::vector<char> CharVector;
    148147    typedef std::vector<double> DoubleVector;
    149148    typedef std::vector<Value> ValueVector;
    150149    typedef std::vector<Cost> CostVector;
     150    typedef std::vector<char> BoolVector;
     151    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
    151152
    152153  private:
     
    199200    IntArcMap _arc_idb;
    200201    IntVector _first_out;
    201     CharVector _forward;
     202    BoolVector _forward;
    202203    IntVector _source;
    203204    IntVector _target;
     
    963964      DoubleVector pi(_res_node_num, 0.0);
    964965      IntVector level(_res_node_num);
    965       CharVector reached(_res_node_num);
    966       CharVector processed(_res_node_num);
     966      BoolVector reached(_res_node_num);
     967      BoolVector processed(_res_node_num);
    967968      IntVector pred_node(_res_node_num);
    968969      IntVector pred_arc(_res_node_num);
  • lemon/cycle_canceling.h

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