COIN-OR::LEMON - Graph Library

Changeset 899:cc9e0c15d747 in lemon


Ignore:
Timestamp:
02/12/10 22:24:26 (14 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.
Phase:
public
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.