COIN-OR::LEMON - Graph Library

Changeset 1004:1e87c18cf65e in lemon-1.2 for lemon


Ignore:
Timestamp:
10/07/15 18:56:56 (8 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.
Phase:
public
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.