COIN-OR::LEMON - Graph Library

Changeset 899:cc9e0c15d747 in lemon


Ignore:
Timestamp:
02/12/10 22:24:26 (9 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
902:d2bc45e8f6f2, 915:c2ff0a365245
Parents:
898:75c97c3786d6 (diff), 897:7762cab7f372 (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.
Message:

Merge

Location:
lemon
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/capacity_scaling.h

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

    r898 r899  
    7878  /// \tparam GR The digraph type the algorithm runs on. 
    7979  /// \tparam V The number type used for flow amounts, capacity bounds 
    80   /// and supply values in the algorithm. By default it is \c int. 
     80  /// and supply values in the algorithm. By default, it is \c int. 
    8181  /// \tparam C The number type used for costs and potentials in the 
    82   /// algorithm. By default it is the same as \c V. 
     82  /// algorithm. By default, it is the same as \c V. 
     83  /// \tparam TR The traits class that defines various types used by the 
     84  /// algorithm. By default, it is \ref CapacityScalingDefaultTraits 
     85  /// "CapacityScalingDefaultTraits<GR, V, C>". 
     86  /// In most cases, this parameter should not be set directly, 
     87  /// consider to use the named template parameters instead. 
    8388  /// 
    8489  /// \warning Both number types must be signed and all input data must 
  • lemon/cost_scaling.h

    r891 r899  
    337337      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, 
    338338        "The cost type of CostScaling must be signed"); 
    339  
     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() { 
    340575      // Resize vectors 
    341576      _node_num = countNodes(_graph); 
     
    405640       
    406641      // Reset parameters 
    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; 
     642      resetParams(); 
    621643      return *this; 
    622644    } 
  • lemon/cost_scaling.h

    r898 r899  
    105105  /// \tparam GR The digraph type the algorithm runs on. 
    106106  /// \tparam V The number type used for flow amounts, capacity bounds 
    107   /// and supply values in the algorithm. By default it is \c int. 
     107  /// and supply values in the algorithm. By default, it is \c int. 
    108108  /// \tparam C The number type used for costs and potentials in the 
    109   /// algorithm. By default it is the same as \c V. 
     109  /// algorithm. By default, it is the same as \c V. 
     110  /// \tparam TR The traits class that defines various types used by the 
     111  /// algorithm. By default, it is \ref CostScalingDefaultTraits 
     112  /// "CostScalingDefaultTraits<GR, V, C>". 
     113  /// In most cases, this parameter should not be set directly, 
     114  /// consider to use the named template parameters instead. 
    110115  /// 
    111116  /// \warning Both number types must be signed and all input data must 
     
    137142    /// 
    138143    /// The large cost type used for internal computations. 
    139     /// Using the \ref CostScalingDefaultTraits "default traits class", 
    140     /// it is \c long \c long if the \c Cost type is integer, 
     144    /// By default, it is \c long \c long if the \c Cost type is integer, 
    141145    /// otherwise it is \c double. 
    142146    typedef typename TR::LargeCost LargeCost; 
Note: See TracChangeset for help on using the changeset viewer.