COIN-OR::LEMON - Graph Library

Changeset 1004:1e87c18cf65e in lemon-1.2


Ignore:
Timestamp:
10/07/15 18:56:56 (2 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
1.2
Parents:
1003:4124fe8ef8de (diff), 1002:43647f48e971 (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.
Tags:
tip
Message:

Merge bugfix #600 to branch 1.2

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/capacity_scaling.h

    r1002 r1004  
    1 /* -*- C++ -*- 
     1/* -*- mode: C++; indent-tabs-mode: nil; -*- 
    22 * 
    3  * This file is a part of LEMON, a generic C++ optimization library 
     3 * This file is a part of LEMON, a generic C++ optimization library. 
    44 * 
    5  * Copyright (C) 2003-2008 
     5 * Copyright (C) 2003-2010 
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES). 
     
    7979  /// \tparam GR The digraph type the algorithm runs on. 
    8080  /// \tparam V The number type used for flow amounts, capacity bounds 
    81   /// and supply values in the algorithm. By default it is \c int. 
     81  /// and supply values in the algorithm. By default, it is \c int. 
    8282  /// \tparam C The number type used for costs and potentials in the 
    83   /// algorithm. By default it is the same as \c V. 
     83  /// algorithm. By default, it is the same as \c V. 
     84  /// \tparam TR The traits class that defines various types used by the 
     85  /// algorithm. By default, it is \ref CapacityScalingDefaultTraits 
     86  /// "CapacityScalingDefaultTraits<GR, V, C>". 
     87  /// In most cases, this parameter should not be set directly, 
     88  /// consider to use the named template parameters instead. 
    8489  /// 
    8590  /// \warning Both number types must be signed and all input data must 
     
    130135      UNBOUNDED 
    131136    }; 
    132    
     137 
    133138  private: 
    134139 
     
    136141 
    137142    typedef std::vector<int> IntVector; 
    138     typedef std::vector<char> BoolVector; 
    139143    typedef std::vector<Value> ValueVector; 
    140144    typedef std::vector<Cost> CostVector; 
     145    typedef std::vector<char> BoolVector; 
     146    // Note: vector<char> is used instead of vector<bool> for efficiency reasons 
    141147 
    142148  private: 
     
    180186 
    181187  public: 
    182    
     188 
    183189    /// \brief Constant for infinite upper bounds (capacities). 
    184190    /// 
     
    207213      CostVector &_pi; 
    208214      IntVector &_pred; 
    209        
     215 
    210216      IntVector _proc_nodes; 
    211217      CostVector _dist; 
    212        
     218 
    213219    public: 
    214220 
     
    297303    /// @} 
    298304 
     305  protected: 
     306 
     307    CapacityScaling() {} 
     308 
    299309  public: 
    300310 
     
    316326        "The cost type of CapacityScaling must be signed"); 
    317327 
     328      // Reset data structures 
     329      reset(); 
     330    } 
     331 
     332    /// \name Parameters 
     333    /// The parameters of the algorithm can be specified using these 
     334    /// functions. 
     335 
     336    /// @{ 
     337 
     338    /// \brief Set the lower bounds on the arcs. 
     339    /// 
     340    /// This function sets the lower bounds on the arcs. 
     341    /// If it is not used before calling \ref run(), the lower bounds 
     342    /// will be set to zero on all arcs. 
     343    /// 
     344    /// \param map An arc map storing the lower bounds. 
     345    /// Its \c Value type must be convertible to the \c Value type 
     346    /// of the algorithm. 
     347    /// 
     348    /// \return <tt>(*this)</tt> 
     349    template <typename LowerMap> 
     350    CapacityScaling& lowerMap(const LowerMap& map) { 
     351      _have_lower = true; 
     352      for (ArcIt a(_graph); a != INVALID; ++a) { 
     353        _lower[_arc_idf[a]] = map[a]; 
     354        _lower[_arc_idb[a]] = map[a]; 
     355      } 
     356      return *this; 
     357    } 
     358 
     359    /// \brief Set the upper bounds (capacities) on the arcs. 
     360    /// 
     361    /// This function sets the upper bounds (capacities) on the arcs. 
     362    /// If it is not used before calling \ref run(), the upper bounds 
     363    /// will be set to \ref INF on all arcs (i.e. the flow value will be 
     364    /// unbounded from above). 
     365    /// 
     366    /// \param map An arc map storing the upper bounds. 
     367    /// Its \c Value type must be convertible to the \c Value type 
     368    /// of the algorithm. 
     369    /// 
     370    /// \return <tt>(*this)</tt> 
     371    template<typename UpperMap> 
     372    CapacityScaling& upperMap(const UpperMap& map) { 
     373      for (ArcIt a(_graph); a != INVALID; ++a) { 
     374        _upper[_arc_idf[a]] = map[a]; 
     375      } 
     376      return *this; 
     377    } 
     378 
     379    /// \brief Set the costs of the arcs. 
     380    /// 
     381    /// This function sets the costs of the arcs. 
     382    /// If it is not used before calling \ref run(), the costs 
     383    /// will be set to \c 1 on all arcs. 
     384    /// 
     385    /// \param map An arc map storing the costs. 
     386    /// Its \c Value type must be convertible to the \c Cost type 
     387    /// of the algorithm. 
     388    /// 
     389    /// \return <tt>(*this)</tt> 
     390    template<typename CostMap> 
     391    CapacityScaling& costMap(const CostMap& map) { 
     392      for (ArcIt a(_graph); a != INVALID; ++a) { 
     393        _cost[_arc_idf[a]] =  map[a]; 
     394        _cost[_arc_idb[a]] = -map[a]; 
     395      } 
     396      return *this; 
     397    } 
     398 
     399    /// \brief Set the supply values of the nodes. 
     400    /// 
     401    /// This function sets the supply values of the nodes. 
     402    /// If neither this function nor \ref stSupply() is used before 
     403    /// calling \ref run(), the supply of each node will be set to zero. 
     404    /// 
     405    /// \param map A node map storing the supply values. 
     406    /// Its \c Value type must be convertible to the \c Value type 
     407    /// of the algorithm. 
     408    /// 
     409    /// \return <tt>(*this)</tt> 
     410    template<typename SupplyMap> 
     411    CapacityScaling& supplyMap(const SupplyMap& map) { 
     412      for (NodeIt n(_graph); n != INVALID; ++n) { 
     413        _supply[_node_id[n]] = map[n]; 
     414      } 
     415      return *this; 
     416    } 
     417 
     418    /// \brief Set single source and target nodes and a supply value. 
     419    /// 
     420    /// This function sets a single source node and a single target node 
     421    /// and the required flow value. 
     422    /// If neither this function nor \ref supplyMap() is used before 
     423    /// calling \ref run(), the supply of each node will be set to zero. 
     424    /// 
     425    /// Using this function has the same effect as using \ref supplyMap() 
     426    /// with such a map in which \c k is assigned to \c s, \c -k is 
     427    /// assigned to \c t and all other nodes have zero supply value. 
     428    /// 
     429    /// \param s The source node. 
     430    /// \param t The target node. 
     431    /// \param k The required amount of flow from node \c s to node \c t 
     432    /// (i.e. the supply of \c s and the demand of \c t). 
     433    /// 
     434    /// \return <tt>(*this)</tt> 
     435    CapacityScaling& stSupply(const Node& s, const Node& t, Value k) { 
     436      for (int i = 0; i != _node_num; ++i) { 
     437        _supply[i] = 0; 
     438      } 
     439      _supply[_node_id[s]] =  k; 
     440      _supply[_node_id[t]] = -k; 
     441      return *this; 
     442    } 
     443 
     444    /// @} 
     445 
     446    /// \name Execution control 
     447    /// The algorithm can be executed using \ref run(). 
     448 
     449    /// @{ 
     450 
     451    /// \brief Run the algorithm. 
     452    /// 
     453    /// This function runs the algorithm. 
     454    /// The paramters can be specified using functions \ref lowerMap(), 
     455    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). 
     456    /// For example, 
     457    /// \code 
     458    ///   CapacityScaling<ListDigraph> cs(graph); 
     459    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost) 
     460    ///     .supplyMap(sup).run(); 
     461    /// \endcode 
     462    /// 
     463    /// This function can be called more than once. All the given parameters 
     464    /// are kept for the next call, unless \ref resetParams() or \ref reset() 
     465    /// is used, thus only the modified parameters have to be set again. 
     466    /// If the underlying digraph was also modified after the construction 
     467    /// of the class (or the last \ref reset() call), then the \ref reset() 
     468    /// function must be called. 
     469    /// 
     470    /// \param factor The capacity scaling factor. It must be larger than 
     471    /// one to use scaling. If it is less or equal to one, then scaling 
     472    /// will be disabled. 
     473    /// 
     474    /// \return \c INFEASIBLE if no feasible flow exists, 
     475    /// \n \c OPTIMAL if the problem has optimal solution 
     476    /// (i.e. it is feasible and bounded), and the algorithm has found 
     477    /// optimal flow and node potentials (primal and dual solutions), 
     478    /// \n \c UNBOUNDED if the digraph contains an arc of negative cost 
     479    /// and infinite upper bound. It means that the objective function 
     480    /// is unbounded on that arc, however, note that it could actually be 
     481    /// bounded over the feasible flows, but this algroithm cannot handle 
     482    /// these cases. 
     483    /// 
     484    /// \see ProblemType 
     485    /// \see resetParams(), reset() 
     486    ProblemType run(int factor = 4) { 
     487      _factor = factor; 
     488      ProblemType pt = init(); 
     489      if (pt != OPTIMAL) return pt; 
     490      return start(); 
     491    } 
     492 
     493    /// \brief Reset all the parameters that have been given before. 
     494    /// 
     495    /// This function resets all the paramaters that have been given 
     496    /// before using functions \ref lowerMap(), \ref upperMap(), 
     497    /// \ref costMap(), \ref supplyMap(), \ref stSupply(). 
     498    /// 
     499    /// It is useful for multiple \ref run() calls. Basically, all the given 
     500    /// parameters are kept for the next \ref run() call, unless 
     501    /// \ref resetParams() or \ref reset() is used. 
     502    /// If the underlying digraph was also modified after the construction 
     503    /// of the class or the last \ref reset() call, then the \ref reset() 
     504    /// function must be used, otherwise \ref resetParams() is sufficient. 
     505    /// 
     506    /// For example, 
     507    /// \code 
     508    ///   CapacityScaling<ListDigraph> cs(graph); 
     509    /// 
     510    ///   // First run 
     511    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost) 
     512    ///     .supplyMap(sup).run(); 
     513    /// 
     514    ///   // Run again with modified cost map (resetParams() is not called, 
     515    ///   // so only the cost map have to be set again) 
     516    ///   cost[e] += 100; 
     517    ///   cs.costMap(cost).run(); 
     518    /// 
     519    ///   // Run again from scratch using resetParams() 
     520    ///   // (the lower bounds will be set to zero on all arcs) 
     521    ///   cs.resetParams(); 
     522    ///   cs.upperMap(capacity).costMap(cost) 
     523    ///     .supplyMap(sup).run(); 
     524    /// \endcode 
     525    /// 
     526    /// \return <tt>(*this)</tt> 
     527    /// 
     528    /// \see reset(), run() 
     529    CapacityScaling& resetParams() { 
     530      for (int i = 0; i != _node_num; ++i) { 
     531        _supply[i] = 0; 
     532      } 
     533      for (int j = 0; j != _res_arc_num; ++j) { 
     534        _lower[j] = 0; 
     535        _upper[j] = INF; 
     536        _cost[j] = _forward[j] ? 1 : -1; 
     537      } 
     538      _have_lower = false; 
     539      return *this; 
     540    } 
     541 
     542    /// \brief Reset the internal data structures and all the parameters 
     543    /// that have been given before. 
     544    /// 
     545    /// This function resets the internal data structures and all the 
     546    /// paramaters that have been given before using functions \ref lowerMap(), 
     547    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). 
     548    /// 
     549    /// It is useful for multiple \ref run() calls. Basically, all the given 
     550    /// parameters are kept for the next \ref run() call, unless 
     551    /// \ref resetParams() or \ref reset() is used. 
     552    /// If the underlying digraph was also modified after the construction 
     553    /// of the class or the last \ref reset() call, then the \ref reset() 
     554    /// function must be used, otherwise \ref resetParams() is sufficient. 
     555    /// 
     556    /// See \ref resetParams() for examples. 
     557    /// 
     558    /// \return <tt>(*this)</tt> 
     559    /// 
     560    /// \see resetParams(), run() 
     561    CapacityScaling& reset() { 
    318562      // Resize vectors 
    319563      _node_num = countNodes(_graph); 
     
    333577      _cost.resize(_res_arc_num); 
    334578      _supply.resize(_node_num); 
    335        
     579 
    336580      _res_cap.resize(_res_arc_num); 
    337581      _pi.resize(_node_num); 
     
    377621        _reverse[bi] = fi; 
    378622      } 
    379        
     623 
    380624      // Reset parameters 
    381       reset(); 
    382     } 
    383  
    384     /// \name Parameters 
    385     /// The parameters of the algorithm can be specified using these 
    386     /// functions. 
    387  
    388     /// @{ 
    389  
    390     /// \brief Set the lower bounds on the arcs. 
    391     /// 
    392     /// This function sets the lower bounds on the arcs. 
    393     /// If it is not used before calling \ref run(), the lower bounds 
    394     /// will be set to zero on all arcs. 
    395     /// 
    396     /// \param map An arc map storing the lower bounds. 
    397     /// Its \c Value type must be convertible to the \c Value type 
    398     /// of the algorithm. 
    399     /// 
    400     /// \return <tt>(*this)</tt> 
    401     template <typename LowerMap> 
    402     CapacityScaling& lowerMap(const LowerMap& map) { 
    403       _have_lower = true; 
    404       for (ArcIt a(_graph); a != INVALID; ++a) { 
    405         _lower[_arc_idf[a]] = map[a]; 
    406         _lower[_arc_idb[a]] = map[a]; 
    407       } 
    408       return *this; 
    409     } 
    410  
    411     /// \brief Set the upper bounds (capacities) on the arcs. 
    412     /// 
    413     /// This function sets the upper bounds (capacities) on the arcs. 
    414     /// If it is not used before calling \ref run(), the upper bounds 
    415     /// will be set to \ref INF on all arcs (i.e. the flow value will be 
    416     /// unbounded from above). 
    417     /// 
    418     /// \param map An arc map storing the upper bounds. 
    419     /// Its \c Value type must be convertible to the \c Value type 
    420     /// of the algorithm. 
    421     /// 
    422     /// \return <tt>(*this)</tt> 
    423     template<typename UpperMap> 
    424     CapacityScaling& upperMap(const UpperMap& map) { 
    425       for (ArcIt a(_graph); a != INVALID; ++a) { 
    426         _upper[_arc_idf[a]] = map[a]; 
    427       } 
    428       return *this; 
    429     } 
    430  
    431     /// \brief Set the costs of the arcs. 
    432     /// 
    433     /// This function sets the costs of the arcs. 
    434     /// If it is not used before calling \ref run(), the costs 
    435     /// will be set to \c 1 on all arcs. 
    436     /// 
    437     /// \param map An arc map storing the costs. 
    438     /// Its \c Value type must be convertible to the \c Cost type 
    439     /// of the algorithm. 
    440     /// 
    441     /// \return <tt>(*this)</tt> 
    442     template<typename CostMap> 
    443     CapacityScaling& costMap(const CostMap& map) { 
    444       for (ArcIt a(_graph); a != INVALID; ++a) { 
    445         _cost[_arc_idf[a]] =  map[a]; 
    446         _cost[_arc_idb[a]] = -map[a]; 
    447       } 
    448       return *this; 
    449     } 
    450  
    451     /// \brief Set the supply values of the nodes. 
    452     /// 
    453     /// This function sets the supply values of the nodes. 
    454     /// If neither this function nor \ref stSupply() is used before 
    455     /// calling \ref run(), the supply of each node will be set to zero. 
    456     /// 
    457     /// \param map A node map storing the supply values. 
    458     /// Its \c Value type must be convertible to the \c Value type 
    459     /// of the algorithm. 
    460     /// 
    461     /// \return <tt>(*this)</tt> 
    462     template<typename SupplyMap> 
    463     CapacityScaling& supplyMap(const SupplyMap& map) { 
    464       for (NodeIt n(_graph); n != INVALID; ++n) { 
    465         _supply[_node_id[n]] = map[n]; 
    466       } 
    467       return *this; 
    468     } 
    469  
    470     /// \brief Set single source and target nodes and a supply value. 
    471     /// 
    472     /// This function sets a single source node and a single target node 
    473     /// and the required flow value. 
    474     /// If neither this function nor \ref supplyMap() is used before 
    475     /// calling \ref run(), the supply of each node will be set to zero. 
    476     /// 
    477     /// Using this function has the same effect as using \ref supplyMap() 
    478     /// with such a map in which \c k is assigned to \c s, \c -k is 
    479     /// assigned to \c t and all other nodes have zero supply value. 
    480     /// 
    481     /// \param s The source node. 
    482     /// \param t The target node. 
    483     /// \param k The required amount of flow from node \c s to node \c t 
    484     /// (i.e. the supply of \c s and the demand of \c t). 
    485     /// 
    486     /// \return <tt>(*this)</tt> 
    487     CapacityScaling& stSupply(const Node& s, const Node& t, Value k) { 
    488       for (int i = 0; i != _node_num; ++i) { 
    489         _supply[i] = 0; 
    490       } 
    491       _supply[_node_id[s]] =  k; 
    492       _supply[_node_id[t]] = -k; 
    493       return *this; 
    494     } 
    495      
    496     /// @} 
    497  
    498     /// \name Execution control 
    499     /// The algorithm can be executed using \ref run(). 
    500  
    501     /// @{ 
    502  
    503     /// \brief Run the algorithm. 
    504     /// 
    505     /// This function runs the algorithm. 
    506     /// The paramters can be specified using functions \ref lowerMap(), 
    507     /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). 
    508     /// For example, 
    509     /// \code 
    510     ///   CapacityScaling<ListDigraph> cs(graph); 
    511     ///   cs.lowerMap(lower).upperMap(upper).costMap(cost) 
    512     ///     .supplyMap(sup).run(); 
    513     /// \endcode 
    514     /// 
    515     /// This function can be called more than once. All the parameters 
    516     /// that have been given are kept for the next call, unless 
    517     /// \ref reset() is called, thus only the modified parameters 
    518     /// have to be set again. See \ref reset() for examples. 
    519     /// However, the underlying digraph must not be modified after this 
    520     /// class have been constructed, since it copies and extends the graph. 
    521     /// 
    522     /// \param factor The capacity scaling factor. It must be larger than 
    523     /// one to use scaling. If it is less or equal to one, then scaling 
    524     /// will be disabled. 
    525     /// 
    526     /// \return \c INFEASIBLE if no feasible flow exists, 
    527     /// \n \c OPTIMAL if the problem has optimal solution 
    528     /// (i.e. it is feasible and bounded), and the algorithm has found 
    529     /// optimal flow and node potentials (primal and dual solutions), 
    530     /// \n \c UNBOUNDED if the digraph contains an arc of negative cost 
    531     /// and infinite upper bound. It means that the objective function 
    532     /// is unbounded on that arc, however, note that it could actually be 
    533     /// bounded over the feasible flows, but this algroithm cannot handle 
    534     /// these cases. 
    535     /// 
    536     /// \see ProblemType 
    537     ProblemType run(int factor = 4) { 
    538       _factor = factor; 
    539       ProblemType pt = init(); 
    540       if (pt != OPTIMAL) return pt; 
    541       return start(); 
    542     } 
    543  
    544     /// \brief Reset all the parameters that have been given before. 
    545     /// 
    546     /// This function resets all the paramaters that have been given 
    547     /// before using functions \ref lowerMap(), \ref upperMap(), 
    548     /// \ref costMap(), \ref supplyMap(), \ref stSupply(). 
    549     /// 
    550     /// It is useful for multiple run() calls. If this function is not 
    551     /// used, all the parameters given before are kept for the next 
    552     /// \ref run() call. 
    553     /// However, the underlying digraph must not be modified after this 
    554     /// class have been constructed, since it copies and extends the graph. 
    555     /// 
    556     /// For example, 
    557     /// \code 
    558     ///   CapacityScaling<ListDigraph> cs(graph); 
    559     /// 
    560     ///   // First run 
    561     ///   cs.lowerMap(lower).upperMap(upper).costMap(cost) 
    562     ///     .supplyMap(sup).run(); 
    563     /// 
    564     ///   // Run again with modified cost map (reset() is not called, 
    565     ///   // so only the cost map have to be set again) 
    566     ///   cost[e] += 100; 
    567     ///   cs.costMap(cost).run(); 
    568     /// 
    569     ///   // Run again from scratch using reset() 
    570     ///   // (the lower bounds will be set to zero on all arcs) 
    571     ///   cs.reset(); 
    572     ///   cs.upperMap(capacity).costMap(cost) 
    573     ///     .supplyMap(sup).run(); 
    574     /// \endcode 
    575     /// 
    576     /// \return <tt>(*this)</tt> 
    577     CapacityScaling& reset() { 
    578       for (int i = 0; i != _node_num; ++i) { 
    579         _supply[i] = 0; 
    580       } 
    581       for (int j = 0; j != _res_arc_num; ++j) { 
    582         _lower[j] = 0; 
    583         _upper[j] = INF; 
    584         _cost[j] = _forward[j] ? 1 : -1; 
    585       } 
    586       _have_lower = false; 
     625      resetParams(); 
    587626      return *this; 
    588627    } 
     
    691730      } 
    692731      if (_sum_supply > 0) return INFEASIBLE; 
    693        
     732 
    694733      // Initialize vectors 
    695734      for (int i = 0; i != _root; ++i) { 
     
    739778        } 
    740779      } 
    741        
     780 
    742781      // Handle GEQ supply type 
    743782      if (_sum_supply < 0) { 
     
    766805      if (_factor > 1) { 
    767806        // With scaling 
    768         Value max_sup = 0, max_dem = 0; 
    769         for (int i = 0; i != _node_num; ++i) { 
     807        Value max_sup = 0, max_dem = 0, max_cap = 0; 
     808        for (int i = 0; i != _root; ++i) { 
    770809          Value ex = _excess[i]; 
    771810          if ( ex > max_sup) max_sup =  ex; 
    772811          if (-ex > max_dem) max_dem = -ex; 
    773         } 
    774         Value max_cap = 0; 
    775         for (int j = 0; j != _res_arc_num; ++j) { 
    776           if (_res_cap[j] > max_cap) max_cap = _res_cap[j]; 
     812          int last_out = _first_out[i+1] - 1; 
     813          for (int j = _first_out[i]; j != last_out; ++j) { 
     814            if (_res_cap[j] > max_cap) max_cap = _res_cap[j]; 
     815          } 
    777816        } 
    778817        max_sup = std::min(std::min(max_sup, max_dem), max_cap); 
     
    807846        for (int i = 0; i != _node_num; ++i) { 
    808847          _pi[i] -= pr; 
    809         }         
    810       } 
    811        
     848        } 
     849      } 
     850 
    812851      return pt; 
    813852    } 
  • lemon/capacity_scaling.h

    r877 r1004  
    2828#include <limits> 
    2929#include <lemon/core.h> 
     30#include <lemon/maps.h> 
    3031#include <lemon/bin_heap.h> 
    3132 
Note: See TracChangeset for help on using the changeset viewer.