COIN-OR::LEMON - Graph Library

Changeset 1048:1226290a9b7d in lemon


Ignore:
Timestamp:
03/15/11 19:52:31 (8 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Faster computation of the dual solution in CostScaling? (#417)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/cost_scaling.h

    r1047 r1048  
    238238    };
    239239
    240     typedef StaticVectorMap<StaticDigraph::Node, LargeCost> LargeCostNodeMap;
    241240    typedef StaticVectorMap<StaticDigraph::Arc, LargeCost> LargeCostArcMap;
    242241
     
    289288    int _max_rank;
    290289
    291     // Data for a StaticDigraph structure
    292     typedef std::pair<int, int> IntPair;
    293     StaticDigraph _sgr;
    294     std::vector<IntPair> _arc_vec;
    295     std::vector<LargeCost> _cost_vec;
    296     LargeCostArcMap _cost_map;
    297     LargeCostNodeMap _pi_map;
    298 
    299290  public:
    300291
     
    343334    CostScaling(const GR& graph) :
    344335      _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph),
    345       _cost_map(_cost_vec), _pi_map(_pi),
    346336      INF(std::numeric_limits<Value>::has_infinity ?
    347337          std::numeric_limits<Value>::infinity() :
     
    619609      _excess.resize(_res_node_num);
    620610      _next_out.resize(_res_node_num);
    621 
    622       _arc_vec.reserve(_res_arc_num);
    623       _cost_vec.reserve(_res_arc_num);
    624611
    625612      // Copy the graph
     
    924911      }
    925912
    926       // Compute node potentials for the original costs
    927       _arc_vec.clear();
    928       _cost_vec.clear();
    929       for (int j = 0; j != _res_arc_num; ++j) {
    930         if (_res_cap[j] > 0) {
    931           _arc_vec.push_back(IntPair(_source[j], _target[j]));
    932           _cost_vec.push_back(_scost[j]);
    933         }
    934       }
    935       _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
    936 
    937       typename BellmanFord<StaticDigraph, LargeCostArcMap>
    938         ::template SetDistMap<LargeCostNodeMap>::Create bf(_sgr, _cost_map);
    939       bf.distMap(_pi_map);
    940       bf.init(0);
    941       bf.start();
     913      // Compute node potentials (dual solution)
     914      for (int i = 0; i != _res_node_num; ++i) {
     915        _pi[i] = static_cast<Cost>(_pi[i] / (_res_node_num * _alpha));
     916      }
     917      bool optimal = true;
     918      for (int i = 0; optimal && i != _res_node_num; ++i) {
     919        LargeCost pi_i = _pi[i];
     920        int last_out = _first_out[i+1];
     921        for (int j = _first_out[i]; j != last_out; ++j) {
     922          if (_res_cap[j] > 0 && _scost[j] + pi_i - _pi[_target[j]] < 0) {
     923            optimal = false;
     924            break;
     925          }
     926        }
     927      }
     928
     929      if (!optimal) {
     930        // Compute node potentials for the original costs with BellmanFord
     931        // (if it is necessary)
     932        typedef std::pair<int, int> IntPair;
     933        StaticDigraph sgr;
     934        std::vector<IntPair> arc_vec;
     935        std::vector<LargeCost> cost_vec;
     936        LargeCostArcMap cost_map(cost_vec);
     937
     938        arc_vec.clear();
     939        cost_vec.clear();
     940        for (int j = 0; j != _res_arc_num; ++j) {
     941          if (_res_cap[j] > 0) {
     942            int u = _source[j], v = _target[j];
     943            arc_vec.push_back(IntPair(u, v));
     944            cost_vec.push_back(_scost[j] + _pi[u] - _pi[v]);
     945          }
     946        }
     947        sgr.build(_res_node_num, arc_vec.begin(), arc_vec.end());
     948
     949        typename BellmanFord<StaticDigraph, LargeCostArcMap>::Create
     950          bf(sgr, cost_map);
     951        bf.init(0);
     952        bf.start();
     953
     954        for (int i = 0; i != _res_node_num; ++i) {
     955          _pi[i] += bf.dist(sgr.node(i));
     956        }
     957      }
     958
     959      // Shift potentials to meet the requirements of the GEQ type
     960      // optimality conditions
     961      LargeCost max_pot = _pi[_root];
     962      for (int i = 0; i != _res_node_num; ++i) {
     963        if (_pi[i] > max_pot) max_pot = _pi[i];
     964      }
     965      if (max_pot != 0) {
     966        for (int i = 0; i != _res_node_num; ++i) {
     967          _pi[i] -= max_pot;
     968        }
     969      }
    942970
    943971      // Handle non-zero lower bounds
Note: See TracChangeset for help on using the changeset viewer.