COIN-OR::LEMON - Graph Library

Changeset 831:cc9e0c15d747 in lemon-1.2 for lemon/capacity_scaling.h


Ignore:
Timestamp:
02/12/10 22:24:26 (10 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
833:d2bc45e8f6f2, 842:c2ff0a365245
Parents:
830:75c97c3786d6 (diff), 829: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

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/capacity_scaling.h

    r825 r831  
    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

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