COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 1104:a78e5b779b69 in lemon-main


Ignore:
Timestamp:
10/17/13 15:08:41 (11 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
1101:15e233f588da (diff), 1103:c0c2f5c87aa6 (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 #478

Location:
lemon
Files:
8 edited

Legend:

Unmodified
Added
Removed

  • lemon/capacity_scaling.h

    r1092 r1104  
    164164
    165165    // Parameters of the problem
    166     bool _have_lower;
     166    bool _has_lower;
    167167    Value _sum_supply;
    168168
    … …  
    357357    template <typename LowerMap>
    358358    CapacityScaling& lowerMap(const LowerMap& map) {
    359       _have_lower = true;
     359      _has_lower = true;
    360360      for (ArcIt a(_graph); a != INVALID; ++a) {
    361361        _lower[_arc_idf[a]] = map[a];
    362         _lower[_arc_idb[a]] = map[a];
    363362      }
    364363      return *this;
    … …  
    544543        _cost[j] = _forward[j] ? 1 : -1;
    545544      }
    546       _have_lower = false;
     545      _has_lower = false;
    547546      return *this;
    548547    }
    … …  
    755754      const Value MAX = std::numeric_limits<Value>::max();
    756755      int last_out;
    757       if (_have_lower) {
     756      if (_has_lower) {
    758757        for (int i = 0; i != _root; ++i) {
    759758          last_out = _first_out[i+1];
    … …  
    840839    }
    841840
    842     // Check if the upper bound is greater or equal to the lower bound
    843     // on each arc.
     841    // Check if the upper bound is greater than or equal to the lower bound
     842    // on each forward arc.
    844843    bool checkBoundMaps() {
    845844      for (int j = 0; j != _res_arc_num; ++j) {
    846         if (_upper[j] < _lower[j]) return false;
     845        if (_forward[j] && _upper[j] < _lower[j]) return false;
    847846      }
    848847      return true;
    … …  
    858857
    859858      // Handle non-zero lower bounds
    860       if (_have_lower) {
     859      if (_has_lower) {
    861860        int limit = _first_out[_root];
    862861        for (int j = 0; j != limit; ++j) {
    863           if (!_forward[j]) _res_cap[j] += _lower[j];
     862          if (_forward[j]) _res_cap[_reverse[j]] += _lower[j];
    864863        }
    865864      }

  • lemon/capacity_scaling.h

    r1103 r1104  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    6767  /// \ref CapacityScaling implements the capacity scaling version
    6868  /// of the successive shortest path algorithm for finding a
    69   /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
    70   /// \ref edmondskarp72theoretical. It is an efficient dual
    71   /// solution method.
     69  /// \ref min_cost_flow "minimum cost flow" \cite amo93networkflows,
     70  /// \cite edmondskarp72theoretical. It is an efficient dual
     71  /// solution method, which runs in polynomial time
     72  /// \f$O(m\log U (n+m)\log n)\f$, where <i>U</i> denotes the maximum
     73  /// of node supply and arc capacity values.
    7274  ///
    7375  /// This algorithm is typically slower than \ref CostScaling and
    … …  
    117119    typedef typename TR::Heap Heap;
    118120
    119     /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm
     121    /// \brief The \ref lemon::CapacityScalingDefaultTraits "traits class"
     122    /// of the algorithm
    120123    typedef TR Traits;
    121124
    … …  
    643646    ///
    644647    /// This function returns the total cost of the found flow.
    645     /// Its complexity is O(e).
     648    /// Its complexity is O(m).
    646649    ///
    647650    /// \note The return type of the function can be specified as a
    … …  
    835838      return OPTIMAL;
    836839    }
    837    
     840
    838841    // Check if the upper bound is greater than or equal to the lower bound
    839842    // on each forward arc.

  • lemon/cost_scaling.h

    r1093 r1104  
    257257
    258258    // Parameters of the problem
    259     bool _have_lower;
     259    bool _has_lower;
    260260    Value _sum_supply;
    261261    int _sup_node_num;
    … …  
    373373    template <typename LowerMap>
    374374    CostScaling& lowerMap(const LowerMap& map) {
    375       _have_lower = true;
     375      _has_lower = true;
    376376      for (ArcIt a(_graph); a != INVALID; ++a) {
    377377        _lower[_arc_idf[a]] = map[a];
    378         _lower[_arc_idb[a]] = map[a];
    379378      }
    380379      return *this;
    … …  
    569568        _scost[_reverse[j]] = 0;
    570569      }
    571       _have_lower = false;
     570      _has_lower = false;
    572571      return *this;
    573572    }
    … …  
    781780      const Value MAX = std::numeric_limits<Value>::max();
    782781      int last_out;
    783       if (_have_lower) {
     782      if (_has_lower) {
    784783        for (int i = 0; i != _root; ++i) {
    785784          last_out = _first_out[i+1];
    … …  
    838837        sup[n] = _supply[_node_id[n]];
    839838      }
    840       if (_have_lower) {
     839      if (_has_lower) {
    841840        for (ArcIt a(_graph); a != INVALID; ++a) {
    842841          int j = _arc_idf[a];
    … …  
    908907    }
    909908
    910     // Check if the upper bound is greater or equal to the lower bound
    911     // on each arc.
     909    // Check if the upper bound is greater than or equal to the lower bound
     910    // on each forward arc.
    912911    bool checkBoundMaps() {
    913912      for (int j = 0; j != _res_arc_num; ++j) {
    914         if (_upper[j] < _lower[j]) return false;
     913        if (_forward[j] && _upper[j] < _lower[j]) return false;
    915914      }
    916915      return true;
    … …  
    992991
    993992      // Handle non-zero lower bounds
    994       if (_have_lower) {
     993      if (_has_lower) {
    995994        int limit = _first_out[_root];
    996995        for (int j = 0; j != limit; ++j) {
    997           if (!_forward[j]) _res_cap[j] += _lower[j];
     996          if (_forward[j]) _res_cap[_reverse[j]] += _lower[j];
    998997        }
    999998      }

  • lemon/cost_scaling.h

    r1103 r1104  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    9292  /// \ref CostScaling implements a cost scaling algorithm that performs
    9393  /// push/augment and relabel operations for finding a \ref min_cost_flow
    94   /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,
    95   /// \ref goldberg97efficient, \ref bunnagel98efficient.
     94  /// "minimum cost flow" \cite amo93networkflows,
     95  /// \cite goldberg90approximation,
     96  /// \cite goldberg97efficient, \cite bunnagel98efficient.
    9697  /// It is a highly efficient primal-dual solution method, which
    9798  /// can be viewed as the generalization of the \ref Preflow
    9899  /// "preflow push-relabel" algorithm for the maximum flow problem.
     100  /// It is a polynomial algorithm, its running time complexity is
     101  /// \f$O(n^2m\log(nK))\f$, where <i>K</i> denotes the maximum arc cost.
    99102  ///
    100103  /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
    … …  
    151154    typedef typename TR::LargeCost LargeCost;
    152155
    153     /// The \ref CostScalingDefaultTraits "traits class" of the algorithm
     156    /// \brief The \ref lemon::CostScalingDefaultTraits "traits class"
     157    /// of the algorithm
    154158    typedef TR Traits;
    155159
    … …  
    211215    typedef std::vector<LargeCost> LargeCostVector;
    212216    typedef std::vector<char> BoolVector;
    213     // Note: vector<char> is used instead of vector<bool> for efficiency reasons
     217    // Note: vector<char> is used instead of vector<bool>
     218    // for efficiency reasons
    214219
    215220  private:
    … …  
    667672    ///
    668673    /// This function returns the total cost of the found flow.
    669     /// Its complexity is O(e).
     674    /// Its complexity is O(m).
    670675    ///
    671676    /// \note The return type of the function can be specified as a
    … …  
    901906      return OPTIMAL;
    902907    }
    903    
     908
    904909    // Check if the upper bound is greater than or equal to the lower bound
    905910    // on each forward arc.
    … …  
    12821287          _buckets[r] = _bucket_next[u];
    12831288
    1284           // Search the incomming arcs of u
     1289          // Search the incoming arcs of u
    12851290          LargeCost pi_u = _pi[u];
    12861291          int last_out = _first_out[u+1];

  • lemon/cycle_canceling.h

    r1092 r1104  
    196196
    197197    // Parameters of the problem
    198     bool _have_lower;
     198    bool _has_lower;
    199199    Value _sum_supply;
    200200
    … …  
    279279    template <typename LowerMap>
    280280    CycleCanceling& lowerMap(const LowerMap& map) {
    281       _have_lower = true;
     281      _has_lower = true;
    282282      for (ArcIt a(_graph); a != INVALID; ++a) {
    283283        _lower[_arc_idf[a]] = map[a];
    284         _lower[_arc_idb[a]] = map[a];
    285284      }
    286285      return *this;
    … …  
    472471        _cost[_reverse[j]] = 0;
    473472      }
    474       _have_lower = false;
     473      _has_lower = false;
    475474      return *this;
    476475    }
    … …  
    685684      const Value MAX = std::numeric_limits<Value>::max();
    686685      int last_out;
    687       if (_have_lower) {
     686      if (_has_lower) {
    688687        for (int i = 0; i != _root; ++i) {
    689688          last_out = _first_out[i+1];
    … …  
    728727        sup[n] = _supply[_node_id[n]];
    729728      }
    730       if (_have_lower) {
     729      if (_has_lower) {
    731730        for (ArcIt a(_graph); a != INVALID; ++a) {
    732731          int j = _arc_idf[a];
    … …  
    785784    }
    786785
    787     // Check if the upper bound is greater or equal to the lower bound
    788     // on each arc.
     786    // Check if the upper bound is greater than or equal to the lower bound
     787    // on each forward arc.
    789788    bool checkBoundMaps() {
    790789      for (int j = 0; j != _res_arc_num; ++j) {
    791         if (_upper[j] < _lower[j]) return false;
     790        if (_forward[j] && _upper[j] < _lower[j]) return false;
    792791      }
    793792      return true;
    … …  
    836835
    837836      // Handle non-zero lower bounds
    838       if (_have_lower) {
     837      if (_has_lower) {
    839838        int limit = _first_out[_root];
    840839        for (int j = 0; j != limit; ++j) {
    841           if (!_forward[j]) _res_cap[j] += _lower[j];
     840          if (_forward[j]) _res_cap[_reverse[j]] += _lower[j];
    842841        }
    843842      }

  • lemon/cycle_canceling.h

    r1103 r1104  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    4848  /// \ref CycleCanceling implements three different cycle-canceling
    4949  /// algorithms for finding a \ref min_cost_flow "minimum cost flow"
    50   /// \ref amo93networkflows, \ref klein67primal,
    51   /// \ref goldberg89cyclecanceling.
     50  /// \cite amo93networkflows, \cite klein67primal,
     51  /// \cite goldberg89cyclecanceling.
    5252  /// The most efficent one is the \ref CANCEL_AND_TIGHTEN
    5353  /// "Cancel-and-Tighten" algorithm, thus it is the default method.
    54   /// It runs in strongly polynomial time, but in practice, it is typically
    55   /// orders of magnitude slower than the scaling algorithms and
    56   /// \ref NetworkSimplex.
     54  /// It runs in strongly polynomial time \f$O(n^2 m^2 \log n)\f$,
     55  /// but in practice, it is typically orders of magnitude slower than
     56  /// the scaling algorithms and \ref NetworkSimplex.
    5757  /// (For more information, see \ref min_cost_flow_algs "the module page".)
    5858  ///
    … …  
    132132      /// The "Minimum Mean Cycle-Canceling" algorithm, which is a
    133133      /// well-known strongly polynomial method
    134       /// \ref goldberg89cyclecanceling. It improves along a
     134      /// \cite goldberg89cyclecanceling. It improves along a
    135135      /// \ref min_mean_cycle "minimum mean cycle" in each iteration.
    136       /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)).
     136      /// Its running time complexity is \f$O(n^2 m^3 \log n)\f$.
    137137      MINIMUM_MEAN_CYCLE_CANCELING,
    138138      /// The "Cancel-and-Tighten" algorithm, which can be viewed as an
    139139      /// improved version of the previous method
    140       /// \ref goldberg89cyclecanceling.
     140      /// \cite goldberg89cyclecanceling.
    141141      /// It is faster both in theory and in practice, its running time
    142       /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)).
     142      /// complexity is \f$O(n^2 m^2 \log n)\f$.
    143143      CANCEL_AND_TIGHTEN
    144144    };
    … …  
    576576    ///
    577577    /// This function returns the total cost of the found flow.
    578     /// Its complexity is O(e).
     578    /// Its complexity is O(m).
    579579    ///
    580580    /// \note The return type of the function can be specified as a
    … …  
    783783      return OPTIMAL;
    784784    }
    785    
     785
    786786    // Check if the upper bound is greater than or equal to the lower bound
    787787    // on each forward arc.
    … …  
    960960      buildResidualNetwork();
    961961      while (true) {
    962        
     962
    963963        typename HwMmc::TerminationCause hw_tc =
    964964            hw_mmc.findCycleMean(hw_iter_limit);
    … …  
    976976          hw_mmc.findCycle();
    977977        }
    978        
     978
    979979        // Compute delta value
    980980        Value delta = INF;

  • lemon/network_simplex.h

    r1092 r1104  
    199199
    200200    // Parameters of the problem
    201     bool _have_lower;
     201    bool _has_lower;
    202202    SupplyType _stype;
    203203    Value _sum_supply;
    … …  
    683683    template <typename LowerMap>
    684684    NetworkSimplex& lowerMap(const LowerMap& map) {
    685       _have_lower = true;
     685      _has_lower = true;
    686686      for (ArcIt a(_graph); a != INVALID; ++a) {
    687687        _lower[_arc_id[a]] = map[a];
    … …  
    880880        _cost[i] = 1;
    881881      }
    882       _have_lower = false;
     882      _has_lower = false;
    883883      _stype = GEQ;
    884884      return *this;
    … …  
    10731073
    10741074      // Remove non-zero lower bounds
    1075       if (_have_lower) {
     1075      if (_has_lower) {
    10761076        for (int i = 0; i != _arc_num; ++i) {
    10771077          Value c = _lower[i];
    … …  
    12361236    }
    12371237
    1238     // Check if the upper bound is greater or equal to the lower bound
     1238    // Check if the upper bound is greater than or equal to the lower bound
    12391239    // on each arc.
    12401240    bool checkBoundMaps() {
    … …  
    16131613
    16141614      // Transform the solution and the supply map to the original form
    1615       if (_have_lower) {
     1615      if (_has_lower) {
    16161616        for (int i = 0; i != _arc_num; ++i) {
    16171617          Value c = _lower[i];

  • lemon/network_simplex.h

    r1103 r1104  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    4242  /// \ref NetworkSimplex implements the primal Network Simplex algorithm
    4343  /// for finding a \ref min_cost_flow "minimum cost flow"
    44   /// \ref amo93networkflows, \ref dantzig63linearprog,
    45   /// \ref kellyoneill91netsimplex.
     44  /// \cite amo93networkflows, \cite dantzig63linearprog,
     45  /// \cite kellyoneill91netsimplex.
    4646  /// This algorithm is a highly efficient specialized version of the
    4747  /// linear programming simplex method directly for the minimum cost
    … …  
    974974    ///
    975975    /// This function returns the total cost of the found flow.
    976     /// Its complexity is O(e).
     976    /// Its complexity is O(m).
    977977    ///
    978978    /// \note The return type of the function can be specified as a
    … …  
    12351235      return true;
    12361236    }
    1237    
     1237
    12381238    // Check if the upper bound is greater than or equal to the lower bound
    12391239    // on each arc.
    … …  
    15171517          }
    15181518        } else {
    1519           // Find the min. cost incomming arc for each demand node
     1519          // Find the min. cost incoming arc for each demand node
    15201520          for (int i = 0; i != int(demand_nodes.size()); ++i) {
    15211521            Node v = demand_nodes[i];
Note: See TracChangeset for help on using the changeset viewer.