COIN-OR::LEMON - Graph Library

Changeset 1046:6ea176638264 in lemon for lemon/cost_scaling.h


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

Fix and improve refine methods in CostScaling? (#417)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/cost_scaling.h

    r1045 r1046  
    11041104      // Paramters for heuristics
    11051105      const int EARLY_TERM_EPSILON_LIMIT = 1000;
    1106       const double GLOBAL_UPDATE_FACTOR = 3.0;
    1107 
    1108       const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
     1106      const double GLOBAL_UPDATE_FACTOR = 1.0;
     1107      const int global_update_skip = static_cast<int>(GLOBAL_UPDATE_FACTOR *
    11091108        (_res_node_num + _sup_node_num * _sup_node_num));
    1110       int next_update_limit = global_update_freq;
    1111 
     1109      int next_global_update_limit = global_update_skip;
     1110
     1111      // Perform cost scaling phases
     1112      IntVector path;
     1113      BoolVector path_arc(_res_arc_num, false);
    11121114      int relabel_cnt = 0;
    1113 
    1114       // Perform cost scaling phases
    1115       std::vector<int> path;
    11161115      for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
    11171116                                        1 : _epsilon / _alpha )
     
    11361135
    11371136          // Find an augmenting path from the start node
    1138           path.clear();
    11391137          int tip = start;
    1140           while (_excess[tip] >= 0 && int(path.size()) < max_length) {
     1138          while (int(path.size()) < max_length && _excess[tip] >= 0) {
    11411139            int u;
    1142             LargeCost min_red_cost, rc, pi_tip = _pi[tip];
     1140            LargeCost rc, min_red_cost = std::numeric_limits<LargeCost>::max();
     1141            LargeCost pi_tip = _pi[tip];
    11431142            int last_out = _first_out[tip+1];
    11441143            for (int a = _next_out[tip]; a != last_out; ++a) {
    1145               u = _target[a];
    1146               if (_res_cap[a] > 0 && _cost[a] + pi_tip - _pi[u] < 0) {
    1147                 path.push_back(a);
    1148                 _next_out[tip] = a;
    1149                 tip = u;
    1150                 goto next_step;
     1144              if (_res_cap[a] > 0) {
     1145                u = _target[a];
     1146                rc = _cost[a] + pi_tip - _pi[u];
     1147                if (rc < 0) {
     1148                  path.push_back(a);
     1149                  _next_out[tip] = a;
     1150                  if (path_arc[a]) {
     1151                    goto augment;   // a cycle is found, stop path search
     1152                  }
     1153                  tip = u;
     1154                  path_arc[a] = true;
     1155                  goto next_step;
     1156                }
     1157                else if (rc < min_red_cost) {
     1158                  min_red_cost = rc;
     1159                }
    11511160              }
    11521161            }
    11531162
    11541163            // Relabel tip node
    1155             min_red_cost = std::numeric_limits<LargeCost>::max();
    11561164            if (tip != start) {
    11571165              int ra = _reverse[path.back()];
    1158               min_red_cost = _cost[ra] + pi_tip - _pi[_target[ra]];
     1166              min_red_cost =
     1167                std::min(min_red_cost, _cost[ra] + pi_tip - _pi[_target[ra]]);
    11591168            }
     1169            last_out = _next_out[tip];
    11601170            for (int a = _first_out[tip]; a != last_out; ++a) {
    1161               rc = _cost[a] + pi_tip - _pi[_target[a]];
    1162               if (_res_cap[a] > 0 && rc < min_red_cost) {
    1163                 min_red_cost = rc;
     1171              if (_res_cap[a] > 0) {
     1172                rc = _cost[a] + pi_tip - _pi[_target[a]];
     1173                if (rc < min_red_cost) {
     1174                  min_red_cost = rc;
     1175                }
    11641176              }
    11651177            }
     
    11701182            // Step back
    11711183            if (tip != start) {
    1172               tip = _source[path.back()];
     1184              int pa = path.back();
     1185              path_arc[pa] = false;
     1186              tip = _source[pa];
    11731187              path.pop_back();
    11741188            }
     
    11781192
    11791193          // Augment along the found path (as much flow as possible)
     1194        augment:
    11801195          Value delta;
    11811196          int pa, u, v = start;
     
    11841199            u = v;
    11851200            v = _target[pa];
     1201            path_arc[pa] = false;
    11861202            delta = std::min(_res_cap[pa], _excess[u]);
    11871203            _res_cap[pa] -= delta;
     
    11891205            _excess[u] -= delta;
    11901206            _excess[v] += delta;
    1191             if (_excess[v] > 0 && _excess[v] <= delta)
     1207            if (_excess[v] > 0 && _excess[v] <= delta) {
    11921208              _active_nodes.push_back(v);
     1209            }
    11931210          }
     1211          path.clear();
    11941212
    11951213          // Global update heuristic
    1196           if (relabel_cnt >= next_update_limit) {
     1214          if (relabel_cnt >= next_global_update_limit) {
    11971215            globalUpdate();
    1198             next_update_limit += global_update_freq;
     1216            next_global_update_limit += global_update_skip;
    11991217          }
    12001218        }
    1201       }
     1219
     1220      }
     1221
    12021222    }
    12031223
     
    12081228      const double GLOBAL_UPDATE_FACTOR = 2.0;
    12091229
    1210       const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
     1230      const int global_update_skip = static_cast<int>(GLOBAL_UPDATE_FACTOR *
    12111231        (_res_node_num + _sup_node_num * _sup_node_num));
    1212       int next_update_limit = global_update_freq;
    1213 
    1214       int relabel_cnt = 0;
     1232      int next_global_update_limit = global_update_skip;
    12151233
    12161234      // Perform cost scaling phases
    12171235      BoolVector hyper(_res_node_num, false);
    12181236      LargeCostVector hyper_cost(_res_node_num);
     1237      int relabel_cnt = 0;
    12191238      for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
    12201239                                        1 : _epsilon / _alpha )
     
    12941313               std::numeric_limits<LargeCost>::max();
    12951314            for (int a = _first_out[n]; a != last_out; ++a) {
    1296               rc = _cost[a] + pi_n - _pi[_target[a]];
    1297               if (_res_cap[a] > 0 && rc < min_red_cost) {
    1298                 min_red_cost = rc;
     1315              if (_res_cap[a] > 0) {
     1316                rc = _cost[a] + pi_n - _pi[_target[a]];
     1317                if (rc < min_red_cost) {
     1318                  min_red_cost = rc;
     1319                }
    12991320              }
    13001321            }
     
    13141335
    13151336          // Global update heuristic
    1316           if (relabel_cnt >= next_update_limit) {
     1337          if (relabel_cnt >= next_global_update_limit) {
    13171338            globalUpdate();
    13181339            for (int u = 0; u != _res_node_num; ++u)
    13191340              hyper[u] = false;
    1320             next_update_limit += global_update_freq;
     1341            next_global_update_limit += global_update_skip;
    13211342          }
    13221343        }
Note: See TracChangeset for help on using the changeset viewer.