COIN-OR::LEMON - Graph Library

Changeset 910:f3bc4e9b5f3a in lemon for lemon/cycle_canceling.h


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/cycle_canceling.h

    r886 r910  
    145145   
    146146    typedef std::vector<int> IntVector;
    147     typedef std::vector<char> CharVector;
    148147    typedef std::vector<double> DoubleVector;
    149148    typedef std::vector<Value> ValueVector;
    150149    typedef std::vector<Cost> CostVector;
     150    typedef std::vector<char> BoolVector;
     151    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
    151152
    152153  private:
     
    199200    IntArcMap _arc_idb;
    200201    IntVector _first_out;
    201     CharVector _forward;
     202    BoolVector _forward;
    202203    IntVector _source;
    203204    IntVector _target;
     
    934935      DoubleVector pi(_res_node_num, 0.0);
    935936      IntVector level(_res_node_num);
    936       CharVector reached(_res_node_num);
    937       CharVector processed(_res_node_num);
     937      BoolVector reached(_res_node_num);
     938      BoolVector processed(_res_node_num);
    938939      IntVector pred_node(_res_node_num);
    939940      IntVector pred_arc(_res_node_num);
Note: See TracChangeset for help on using the changeset viewer.