COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
02/20/10 18:39:03 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

New heuristics for MCF algorithms (#340)
and some implementation improvements.

  • A useful heuristic is added to NetworkSimplex? to make the initial pivots faster.
  • A powerful global update heuristic is added to CostScaling? and the implementation is reworked with various improvements.
  • Better relabeling in CostScaling? to improve numerical stability and make the code faster.
  • A small improvement is made in CapacityScaling? for better delta computation.
  • Add notes to the classes about the usage of vector<char> instead of vector<bool> for efficiency reasons.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/capacity_scaling.h

    r887 r910  
    135135
    136136    typedef std::vector<int> IntVector;
    137     typedef std::vector<char> BoolVector;
    138137    typedef std::vector<Value> ValueVector;
    139138    typedef std::vector<Cost> CostVector;
     139    typedef std::vector<char> BoolVector;
     140    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
    140141
    141142  private:
     
    765766      if (_factor > 1) {
    766767        // With scaling
    767         Value max_sup = 0, max_dem = 0;
    768         for (int i = 0; i != _node_num; ++i) {
     768        Value max_sup = 0, max_dem = 0, max_cap = 0;
     769        for (int i = 0; i != _root; ++i) {
    769770          Value ex = _excess[i];
    770771          if ( ex > max_sup) max_sup =  ex;
    771772          if (-ex > max_dem) max_dem = -ex;
    772         }
    773         Value max_cap = 0;
    774         for (int j = 0; j != _res_arc_num; ++j) {
    775           if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
     773          int last_out = _first_out[i+1] - 1;
     774          for (int j = _first_out[i]; j != last_out; ++j) {
     775            if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
     776          }
    776777        }
    777778        max_sup = std::min(std::min(max_sup, max_dem), max_cap);
Note: See TracChangeset for help on using the changeset viewer.