COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [831:cc9e0c15d747:829:7762cab7f372] in lemon-main


Ignore:
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • lemon/capacity_scaling.h

    r831 r825  
    320320        "The cost type of CapacityScaling must be signed");
    321321
    322       // Reset data structures
     322      // Resize vectors
     323      _node_num = countNodes(_graph);
     324      _arc_num = countArcs(_graph);
     325      _res_arc_num = 2 * (_arc_num + _node_num);
     326      _root = _node_num;
     327      ++_node_num;
     328
     329      _first_out.resize(_node_num + 1);
     330      _forward.resize(_res_arc_num);
     331      _source.resize(_res_arc_num);
     332      _target.resize(_res_arc_num);
     333      _reverse.resize(_res_arc_num);
     334
     335      _lower.resize(_res_arc_num);
     336      _upper.resize(_res_arc_num);
     337      _cost.resize(_res_arc_num);
     338      _supply.resize(_node_num);
     339     
     340      _res_cap.resize(_res_arc_num);
     341      _pi.resize(_node_num);
     342      _excess.resize(_node_num);
     343      _pred.resize(_node_num);
     344
     345      // Copy the graph
     346      int i = 0, j = 0, k = 2 * _arc_num + _node_num - 1;
     347      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
     348        _node_id[n] = i;
     349      }
     350      i = 0;
     351      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
     352        _first_out[i] = j;
     353        for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
     354          _arc_idf[a] = j;
     355          _forward[j] = true;
     356          _source[j] = i;
     357          _target[j] = _node_id[_graph.runningNode(a)];
     358        }
     359        for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
     360          _arc_idb[a] = j;
     361          _forward[j] = false;
     362          _source[j] = i;
     363          _target[j] = _node_id[_graph.runningNode(a)];
     364        }
     365        _forward[j] = false;
     366        _source[j] = i;
     367        _target[j] = _root;
     368        _reverse[j] = k;
     369        _forward[k] = true;
     370        _source[k] = _root;
     371        _target[k] = i;
     372        _reverse[k] = j;
     373        ++j; ++k;
     374      }
     375      _first_out[i] = j;
     376      _first_out[_node_num] = k;
     377      for (ArcIt a(_graph); a != INVALID; ++a) {
     378        int fi = _arc_idf[a];
     379        int bi = _arc_idb[a];
     380        _reverse[fi] = bi;
     381        _reverse[bi] = fi;
     382      }
     383     
     384      // Reset parameters
    323385      reset();
    324386    }
    … …  
    455517    /// \endcode
    456518    ///
    457     /// This function can be called more than once. All the given parameters
    458     /// are kept for the next call, unless \ref resetParams() or \ref reset()
    459     /// is used, thus only the modified parameters have to be set again.
    460     /// If the underlying digraph was also modified after the construction
    461     /// of the class (or the last \ref reset() call), then the \ref reset()
    462     /// function must be called.
     519    /// This function can be called more than once. All the parameters
     520    /// that have been given are kept for the next call, unless
     521    /// \ref reset() is called, thus only the modified parameters
     522    /// have to be set again. See \ref reset() for examples.
     523    /// However, the underlying digraph must not be modified after this
     524    /// class have been constructed, since it copies and extends the graph.
    463525    ///
    464526    /// \param factor The capacity scaling factor. It must be larger than
    … …  
    477539    ///
    478540    /// \see ProblemType
    479     /// \see resetParams(), reset()
    480541    ProblemType run(int factor = 4) {
    481542      _factor = factor;
    … …  
    491552    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
    492553    ///
    493     /// It is useful for multiple \ref run() calls. Basically, all the given
    494     /// parameters are kept for the next \ref run() call, unless
    495     /// \ref resetParams() or \ref reset() is used.
    496     /// If the underlying digraph was also modified after the construction
    497     /// of the class or the last \ref reset() call, then the \ref reset()
    498     /// function must be used, otherwise \ref resetParams() is sufficient.
     554    /// It is useful for multiple run() calls. If this function is not
     555    /// used, all the parameters given before are kept for the next
     556    /// \ref run() call.
     557    /// However, the underlying digraph must not be modified after this
     558    /// class have been constructed, since it copies and extends the graph.
    499559    ///
    500560    /// For example,
    … …  
    506566    ///     .supplyMap(sup).run();
    507567    ///
    508     ///   // Run again with modified cost map (resetParams() is not called,
     568    ///   // Run again with modified cost map (reset() is not called,
    509569    ///   // so only the cost map have to be set again)
    510570    ///   cost[e] += 100;
    511571    ///   cs.costMap(cost).run();
    512572    ///
    513     ///   // Run again from scratch using resetParams()
     573    ///   // Run again from scratch using reset()
    514574    ///   // (the lower bounds will be set to zero on all arcs)
    515     ///   cs.resetParams();
     575    ///   cs.reset();
    516576    ///   cs.upperMap(capacity).costMap(cost)
    517577    ///     .supplyMap(sup).run();
    … …  
    519579    ///
    520580    /// \return <tt>(*this)</tt>
    521     ///
    522     /// \see reset(), run()
    523     CapacityScaling& resetParams() {
     581    CapacityScaling& reset() {
    524582      for (int i = 0; i != _node_num; ++i) {
    525583        _supply[i] = 0;
    … …  
    531589      }
    532590      _have_lower = false;
    533       return *this;
    534     }
    535 
    536     /// \brief Reset the internal data structures and all the parameters
    537     /// that have been given before.
    538     ///
    539     /// This function resets the internal data structures and all the
    540     /// paramaters that have been given before using functions \ref lowerMap(),
    541     /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
    542     ///
    543     /// It is useful for multiple \ref run() calls. Basically, all the given
    544     /// parameters are kept for the next \ref run() call, unless
    545     /// \ref resetParams() or \ref reset() is used.
    546     /// If the underlying digraph was also modified after the construction
    547     /// of the class or the last \ref reset() call, then the \ref reset()
    548     /// function must be used, otherwise \ref resetParams() is sufficient.
    549     ///
    550     /// See \ref resetParams() for examples.
    551     ///
    552     /// \return <tt>(*this)</tt>
    553     ///
    554     /// \see resetParams(), run()
    555     CapacityScaling& reset() {
    556       // Resize vectors
    557       _node_num = countNodes(_graph);
    558       _arc_num = countArcs(_graph);
    559       _res_arc_num = 2 * (_arc_num + _node_num);
    560       _root = _node_num;
    561       ++_node_num;
    562 
    563       _first_out.resize(_node_num + 1);
    564       _forward.resize(_res_arc_num);
    565       _source.resize(_res_arc_num);
    566       _target.resize(_res_arc_num);
    567       _reverse.resize(_res_arc_num);
    568 
    569       _lower.resize(_res_arc_num);
    570       _upper.resize(_res_arc_num);
    571       _cost.resize(_res_arc_num);
    572       _supply.resize(_node_num);
    573      
    574       _res_cap.resize(_res_arc_num);
    575       _pi.resize(_node_num);
    576       _excess.resize(_node_num);
    577       _pred.resize(_node_num);
    578 
    579       // Copy the graph
    580       int i = 0, j = 0, k = 2 * _arc_num + _node_num - 1;
    581       for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
    582         _node_id[n] = i;
    583       }
    584       i = 0;
    585       for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
    586         _first_out[i] = j;
    587         for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
    588           _arc_idf[a] = j;
    589           _forward[j] = true;
    590           _source[j] = i;
    591           _target[j] = _node_id[_graph.runningNode(a)];
    592         }
    593         for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
    594           _arc_idb[a] = j;
    595           _forward[j] = false;
    596           _source[j] = i;
    597           _target[j] = _node_id[_graph.runningNode(a)];
    598         }
    599         _forward[j] = false;
    600         _source[j] = i;
    601         _target[j] = _root;
    602         _reverse[j] = k;
    603         _forward[k] = true;
    604         _source[k] = _root;
    605         _target[k] = i;
    606         _reverse[k] = j;
    607         ++j; ++k;
    608       }
    609       _first_out[i] = j;
    610       _first_out[_node_num] = k;
    611       for (ArcIt a(_graph); a != INVALID; ++a) {
    612         int fi = _arc_idf[a];
    613         int bi = _arc_idb[a];
    614         _reverse[fi] = bi;
    615         _reverse[bi] = fi;
    616       }
    617      
    618       // Reset parameters
    619       resetParams();
    620591      return *this;
    621592    }

  • lemon/cost_scaling.h

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

  • lemon/cycle_canceling.h

    r830 r820  
    251251        "The cost type of CycleCanceling must be signed");
    252252
    253       // Reset data structures
     253      // Resize vectors
     254      _node_num = countNodes(_graph);
     255      _arc_num = countArcs(_graph);
     256      _res_node_num = _node_num + 1;
     257      _res_arc_num = 2 * (_arc_num + _node_num);
     258      _root = _node_num;
     259
     260      _first_out.resize(_res_node_num + 1);
     261      _forward.resize(_res_arc_num);
     262      _source.resize(_res_arc_num);
     263      _target.resize(_res_arc_num);
     264      _reverse.resize(_res_arc_num);
     265
     266      _lower.resize(_res_arc_num);
     267      _upper.resize(_res_arc_num);
     268      _cost.resize(_res_arc_num);
     269      _supply.resize(_res_node_num);
     270     
     271      _res_cap.resize(_res_arc_num);
     272      _pi.resize(_res_node_num);
     273
     274      _arc_vec.reserve(_res_arc_num);
     275      _cost_vec.reserve(_res_arc_num);
     276      _id_vec.reserve(_res_arc_num);
     277
     278      // Copy the graph
     279      int i = 0, j = 0, k = 2 * _arc_num + _node_num;
     280      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
     281        _node_id[n] = i;
     282      }
     283      i = 0;
     284      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
     285        _first_out[i] = j;
     286        for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
     287          _arc_idf[a] = j;
     288          _forward[j] = true;
     289          _source[j] = i;
     290          _target[j] = _node_id[_graph.runningNode(a)];
     291        }
     292        for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
     293          _arc_idb[a] = j;
     294          _forward[j] = false;
     295          _source[j] = i;
     296          _target[j] = _node_id[_graph.runningNode(a)];
     297        }
     298        _forward[j] = false;
     299        _source[j] = i;
     300        _target[j] = _root;
     301        _reverse[j] = k;
     302        _forward[k] = true;
     303        _source[k] = _root;
     304        _target[k] = i;
     305        _reverse[k] = j;
     306        ++j; ++k;
     307      }
     308      _first_out[i] = j;
     309      _first_out[_res_node_num] = k;
     310      for (ArcIt a(_graph); a != INVALID; ++a) {
     311        int fi = _arc_idf[a];
     312        int bi = _arc_idb[a];
     313        _reverse[fi] = bi;
     314        _reverse[bi] = fi;
     315      }
     316     
     317      // Reset parameters
    254318      reset();
    255319    }
    … …  
    386450    /// \endcode
    387451    ///
    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.
     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.
    394458    ///
    395459    /// \param method The cycle-canceling method that will be used.
    … …  
    407471    ///
    408472    /// \see ProblemType, Method
    409     /// \see resetParams(), reset()
    410473    ProblemType run(Method method = CANCEL_AND_TIGHTEN) {
    411474      ProblemType pt = init();
    … …  
    421484    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
    422485    ///
    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.
     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.
    429491    ///
    430492    /// For example,
    … …  
    436498    ///     .supplyMap(sup).run();
    437499    ///
    438     ///   // Run again with modified cost map (resetParams() is not called,
     500    ///   // Run again with modified cost map (reset() is not called,
    439501    ///   // so only the cost map have to be set again)
    440502    ///   cost[e] += 100;
    441503    ///   cc.costMap(cost).run();
    442504    ///
    443     ///   // Run again from scratch using resetParams()
     505    ///   // Run again from scratch using reset()
    444506    ///   // (the lower bounds will be set to zero on all arcs)
    445     ///   cc.resetParams();
     507    ///   cc.reset();
    446508    ///   cc.upperMap(capacity).costMap(cost)
    447509    ///     .supplyMap(sup).run();
    … …  
    449511    ///
    450512    /// \return <tt>(*this)</tt>
    451     ///
    452     /// \see reset(), run()
    453     CycleCanceling& resetParams() {
     513    CycleCanceling& reset() {
    454514      for (int i = 0; i != _res_node_num; ++i) {
    455515        _supply[i] = 0;
    … …  
    468528      }     
    469529      _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() {
    493       // Resize vectors
    494       _node_num = countNodes(_graph);
    495       _arc_num = countArcs(_graph);
    496       _res_node_num = _node_num + 1;
    497       _res_arc_num = 2 * (_arc_num + _node_num);
    498       _root = _node_num;
    499 
    500       _first_out.resize(_res_node_num + 1);
    501       _forward.resize(_res_arc_num);
    502       _source.resize(_res_arc_num);
    503       _target.resize(_res_arc_num);
    504       _reverse.resize(_res_arc_num);
    505 
    506       _lower.resize(_res_arc_num);
    507       _upper.resize(_res_arc_num);
    508       _cost.resize(_res_arc_num);
    509       _supply.resize(_res_node_num);
    510      
    511       _res_cap.resize(_res_arc_num);
    512       _pi.resize(_res_node_num);
    513 
    514       _arc_vec.reserve(_res_arc_num);
    515       _cost_vec.reserve(_res_arc_num);
    516       _id_vec.reserve(_res_arc_num);
    517 
    518       // Copy the graph
    519       int i = 0, j = 0, k = 2 * _arc_num + _node_num;
    520       for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
    521         _node_id[n] = i;
    522       }
    523       i = 0;
    524       for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
    525         _first_out[i] = j;
    526         for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
    527           _arc_idf[a] = j;
    528           _forward[j] = true;
    529           _source[j] = i;
    530           _target[j] = _node_id[_graph.runningNode(a)];
    531         }
    532         for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
    533           _arc_idb[a] = j;
    534           _forward[j] = false;
    535           _source[j] = i;
    536           _target[j] = _node_id[_graph.runningNode(a)];
    537         }
    538         _forward[j] = false;
    539         _source[j] = i;
    540         _target[j] = _root;
    541         _reverse[j] = k;
    542         _forward[k] = true;
    543         _source[k] = _root;
    544         _target[k] = i;
    545         _reverse[k] = j;
    546         ++j; ++k;
    547       }
    548       _first_out[i] = j;
    549       _first_out[_res_node_num] = k;
    550       for (ArcIt a(_graph); a != INVALID; ++a) {
    551         int fi = _arc_idf[a];
    552         int bi = _arc_idb[a];
    553         _reverse[fi] = bi;
    554         _reverse[bi] = fi;
    555       }
    556      
    557       // Reset parameters
    558       resetParams();
    559530      return *this;
    560531    }

  • lemon/network_simplex.h

    r830 r812  
    195195    IntVector _source;
    196196    IntVector _target;
    197     bool _arc_mixing;
    198197
    199198    // Node and arc data
    … …  
    635634    NetworkSimplex(const GR& graph, bool arc_mixing = false) :
    636635      _graph(graph), _node_id(graph), _arc_id(graph),
    637       _arc_mixing(arc_mixing),
    638636      MAX(std::numeric_limits<Value>::max()),
    639637      INF(std::numeric_limits<Value>::has_infinity ?
    … …  
    646644        "The cost type of NetworkSimplex must be signed");
    647645       
    648       // Reset data structures
     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
    649698      reset();
    650699    }
    … …  
    794843    /// \endcode
    795844    ///
    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.
     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.
    802851    ///
    803852    /// \param pivot_rule The pivot rule that will be used during the
    … …  
    813862    ///
    814863    /// \see ProblemType, PivotRule
    815     /// \see resetParams(), reset()
    816864    ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {
    817865      if (!init()) return INFEASIBLE;
    … …  
    825873    /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType().
    826874    ///
    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.
     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.
    833880    ///
    834881    /// For example,
    … …  
    840887    ///     .supplyMap(sup).run();
    841888    ///
    842     ///   // Run again with modified cost map (resetParams() is not called,
     889    ///   // Run again with modified cost map (reset() is not called,
    843890    ///   // so only the cost map have to be set again)
    844891    ///   cost[e] += 100;
    845892    ///   ns.costMap(cost).run();
    846893    ///
    847     ///   // Run again from scratch using resetParams()
     894    ///   // Run again from scratch using reset()
    848895    ///   // (the lower bounds will be set to zero on all arcs)
    849     ///   ns.resetParams();
     896    ///   ns.reset();
    850897    ///   ns.upperMap(capacity).costMap(cost)
    851898    ///     .supplyMap(sup).run();
    … …  
    853900    ///
    854901    /// \return <tt>(*this)</tt>
    855     ///
    856     /// \see reset(), run()
    857     NetworkSimplex& resetParams() {
     902    NetworkSimplex& reset() {
    858903      for (int i = 0; i != _node_num; ++i) {
    859904        _supply[i] = 0;
    … …  
    869914    }
    870915
    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    
    948916    /// @}
    949917

  • test/min_cost_flow_test.cc

    r830 r819  
    158158      const MCF& const_mcf = mcf;
    159159
    160       b = mcf.reset().resetParams()
     160      b = mcf.reset()
    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.resetParams().supplyMap(s1);
     349  mcf1.reset().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.resetParams().upperMap(u).costMap(c).supplyMap(s5);
     366  mcf1.reset().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.resetParams().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s);
     383  mcf2.reset().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.