COIN-OR::LEMON - Graph Library

Changeset 895:dca9eed2c375 in lemon-main


Ignore:
Timestamp:
08/22/10 23:54:10 (14 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Improve the tree update process and a pivot rule (#391)
and make some parts of the code clearer using better names

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/network_simplex.h

    r889 r895  
    167167    typedef std::vector<Value> ValueVector;
    168168    typedef std::vector<Cost> CostVector;
    169     typedef std::vector<char> BoolVector;
    170     // Note: vector<char> is used instead of vector<bool> for efficiency reasons
     169    typedef std::vector<signed char> CharVector;
     170    // Note: vector<signed char> is used instead of vector<ArcState> and
     171    // vector<ArcDirection> for efficiency reasons
    171172
    172173    // State constants for arcs
     
    177178    };
    178179
    179     typedef std::vector<signed char> StateVector;
    180     // Note: vector<signed char> is used instead of vector<ArcState> for
    181     // efficiency reasons
     180    // Direction constants for tree arcs
     181    enum ArcDirection {
     182      DIR_DOWN = -1,
     183      DIR_UP   =  1
     184    };
    182185
    183186  private:
     
    218221    IntVector _succ_num;
    219222    IntVector _last_succ;
     223    CharVector _pred_dir;
     224    CharVector _state;
    220225    IntVector _dirty_revs;
    221     BoolVector _forward;
    222     StateVector _state;
    223226    int _root;
    224227
    225228    // Temporary data used in the current pivot iteration
    226229    int in_arc, join, u_in, v_in, u_out, v_out;
    227     int first, second, right, last;
    228     int stem, par_stem, new_stem;
    229230    Value delta;
    230231
     
    251252      const IntVector  &_target;
    252253      const CostVector &_cost;
    253       const StateVector &_state;
     254      const CharVector &_state;
    254255      const CostVector &_pi;
    255256      int &_in_arc;
     
    303304      const IntVector  &_target;
    304305      const CostVector &_cost;
    305       const StateVector &_state;
     306      const CharVector &_state;
    306307      const CostVector &_pi;
    307308      int &_in_arc;
     
    342343      const IntVector  &_target;
    343344      const CostVector &_cost;
    344       const StateVector &_state;
     345      const CharVector &_state;
    345346      const CostVector &_pi;
    346347      int &_in_arc;
     
    415416      const IntVector  &_target;
    416417      const CostVector &_cost;
    417       const StateVector &_state;
     418      const CharVector &_state;
    418419      const CostVector &_pi;
    419420      int &_in_arc;
     
    518519      const IntVector  &_target;
    519520      const CostVector &_cost;
    520       const StateVector &_state;
     521      const CharVector &_state;
    521522      const CostVector &_pi;
    522523      int &_in_arc;
     
    571572        // Check the current candidate list
    572573        int e;
     574        Cost c;
    573575        for (int i = 0; i != _curr_length; ++i) {
    574576          e = _candidates[i];
    575           _cand_cost[e] = _state[e] *
    576             (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    577           if (_cand_cost[e] >= 0) {
     577          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     578          if (c < 0) {
     579            _cand_cost[e] = c;
     580          } else {
    578581            _candidates[i--] = _candidates[--_curr_length];
    579582          }
     
    585588
    586589        for (e = _next_arc; e != _search_arc_num; ++e) {
    587           _cand_cost[e] = _state[e] *
    588             (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    589           if (_cand_cost[e] < 0) {
     590          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     591          if (c < 0) {
     592            _cand_cost[e] = c;
    590593            _candidates[_curr_length++] = e;
    591594          }
     
    914917      _parent.resize(all_node_num);
    915918      _pred.resize(all_node_num);
    916       _forward.resize(all_node_num);
     919      _pred_dir.resize(all_node_num);
    917920      _thread.resize(all_node_num);
    918921      _rev_thread.resize(all_node_num);
     
    11171120          _state[e] = STATE_TREE;
    11181121          if (_supply[u] >= 0) {
    1119             _forward[u] = true;
     1122            _pred_dir[u] = DIR_UP;
    11201123            _pi[u] = 0;
    11211124            _source[e] = u;
     
    11241127            _cost[e] = 0;
    11251128          } else {
    1126             _forward[u] = false;
     1129            _pred_dir[u] = DIR_DOWN;
    11271130            _pi[u] = ART_COST;
    11281131            _source[e] = _root;
     
    11441147          _last_succ[u] = u;
    11451148          if (_supply[u] >= 0) {
    1146             _forward[u] = true;
     1149            _pred_dir[u] = DIR_UP;
    11471150            _pi[u] = 0;
    11481151            _pred[u] = e;
     
    11541157            _state[e] = STATE_TREE;
    11551158          } else {
    1156             _forward[u] = false;
     1159            _pred_dir[u] = DIR_DOWN;
    11571160            _pi[u] = ART_COST;
    11581161            _pred[u] = f;
     
    11851188          _last_succ[u] = u;
    11861189          if (_supply[u] <= 0) {
    1187             _forward[u] = false;
     1190            _pred_dir[u] = DIR_DOWN;
    11881191            _pi[u] = 0;
    11891192            _pred[u] = e;
     
    11951198            _state[e] = STATE_TREE;
    11961199          } else {
    1197             _forward[u] = true;
     1200            _pred_dir[u] = DIR_UP;
    11981201            _pi[u] = -ART_COST;
    11991202            _pred[u] = f;
     
    12381241      // Initialize first and second nodes according to the direction
    12391242      // of the cycle
     1243      int first, second;
    12401244      if (_state[in_arc] == STATE_LOWER) {
    12411245        first  = _source[in_arc];
     
    12471251      delta = _cap[in_arc];
    12481252      int result = 0;
    1249       Value d;
     1253      Value c, d;
    12501254      int e;
    12511255
    1252       // Search the cycle along the path form the first node to the root
     1256      // Search the cycle form the first node to the join node
    12531257      for (int u = first; u != join; u = _parent[u]) {
    12541258        e = _pred[u];
    1255         d = _forward[u] ?
    1256           _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]);
     1259        d = _flow[e];
     1260        if (_pred_dir[u] == DIR_DOWN) {
     1261          c = _cap[e];
     1262          d = c >= MAX ? INF : c - d;
     1263        }
    12571264        if (d < delta) {
    12581265          delta = d;
     
    12611268        }
    12621269      }
    1263       // Search the cycle along the path form the second node to the root
     1270
     1271      // Search the cycle form the second node to the join node
    12641272      for (int u = second; u != join; u = _parent[u]) {
    12651273        e = _pred[u];
    1266         d = _forward[u] ?
    1267           (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e];
     1274        d = _flow[e];
     1275        if (_pred_dir[u] == DIR_UP) {
     1276          c = _cap[e];
     1277          d = c >= MAX ? INF : c - d;
     1278        }
    12681279        if (d <= delta) {
    12691280          delta = d;
     
    12901301        _flow[in_arc] += val;
    12911302        for (int u = _source[in_arc]; u != join; u = _parent[u]) {
    1292           _flow[_pred[u]] += _forward[u] ? -val : val;
     1303          _flow[_pred[u]] -= _pred_dir[u] * val;
    12931304        }
    12941305        for (int u = _target[in_arc]; u != join; u = _parent[u]) {
    1295           _flow[_pred[u]] += _forward[u] ? val : -val;
     1306          _flow[_pred[u]] += _pred_dir[u] * val;
    12961307        }
    12971308      }
     
    13081319    // Update the tree structure
    13091320    void updateTreeStructure() {
    1310       int u, w;
    13111321      int old_rev_thread = _rev_thread[u_out];
    13121322      int old_succ_num = _succ_num[u_out];
     
    13141324      v_out = _parent[u_out];
    13151325
    1316       u = _last_succ[u_in];  // the last successor of u_in
    1317       right = _thread[u];    // the node after it
    1318 
    1319       // Handle the case when old_rev_thread equals to v_in
    1320       // (it also means that join and v_out coincide)
    1321       if (old_rev_thread == v_in) {
    1322         last = _thread[_last_succ[u_out]];
     1326      // Check if u_in and u_out coincide
     1327      if (u_in == u_out) {
     1328        // Update _parent, _pred, _pred_dir
     1329        _parent[u_in] = v_in;
     1330        _pred[u_in] = in_arc;
     1331        _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN;
     1332
     1333        // Update _thread and _rev_thread
     1334        if (_thread[v_in] != u_out) {
     1335          int after = _thread[old_last_succ];
     1336          _thread[old_rev_thread] = after;
     1337          _rev_thread[after] = old_rev_thread;
     1338          after = _thread[v_in];
     1339          _thread[v_in] = u_out;
     1340          _rev_thread[u_out] = v_in;
     1341          _thread[old_last_succ] = after;
     1342          _rev_thread[after] = old_last_succ;
     1343        }
    13231344      } else {
    1324         last = _thread[v_in];
    1325       }
    1326 
    1327       // Update _thread and _parent along the stem nodes (i.e. the nodes
    1328       // between u_in and u_out, whose parent have to be changed)
    1329       _thread[v_in] = stem = u_in;
    1330       _dirty_revs.clear();
    1331       _dirty_revs.push_back(v_in);
    1332       par_stem = v_in;
    1333       while (stem != u_out) {
    1334         // Insert the next stem node into the thread list
    1335         new_stem = _parent[stem];
    1336         _thread[u] = new_stem;
    1337         _dirty_revs.push_back(u);
    1338 
    1339         // Remove the subtree of stem from the thread list
    1340         w = _rev_thread[stem];
    1341         _thread[w] = right;
    1342         _rev_thread[right] = w;
    1343 
    1344         // Change the parent node and shift stem nodes
    1345         _parent[stem] = par_stem;
    1346         par_stem = stem;
    1347         stem = new_stem;
    1348 
    1349         // Update u and right
    1350         u = _last_succ[stem] == _last_succ[par_stem] ?
    1351           _rev_thread[par_stem] : _last_succ[stem];
    1352         right = _thread[u];
    1353       }
    1354       _parent[u_out] = par_stem;
    1355       _thread[u] = last;
    1356       _rev_thread[last] = u;
    1357       _last_succ[u_out] = u;
    1358 
    1359       // Remove the subtree of u_out from the thread list except for
    1360       // the case when old_rev_thread equals to v_in
    1361       // (it also means that join and v_out coincide)
    1362       if (old_rev_thread != v_in) {
    1363         _thread[old_rev_thread] = right;
    1364         _rev_thread[right] = old_rev_thread;
    1365       }
    1366 
    1367       // Update _rev_thread using the new _thread values
    1368       for (int i = 0; i != int(_dirty_revs.size()); ++i) {
    1369         u = _dirty_revs[i];
    1370         _rev_thread[_thread[u]] = u;
    1371       }
    1372 
    1373       // Update _pred, _forward, _last_succ and _succ_num for the
    1374       // stem nodes from u_out to u_in
    1375       int tmp_sc = 0, tmp_ls = _last_succ[u_out];
    1376       u = u_out;
    1377       while (u != u_in) {
    1378         w = _parent[u];
    1379         _pred[u] = _pred[w];
    1380         _forward[u] = !_forward[w];
    1381         tmp_sc += _succ_num[u] - _succ_num[w];
    1382         _succ_num[u] = tmp_sc;
    1383         _last_succ[w] = tmp_ls;
    1384         u = w;
    1385       }
    1386       _pred[u_in] = in_arc;
    1387       _forward[u_in] = (u_in == _source[in_arc]);
    1388       _succ_num[u_in] = old_succ_num;
    1389 
    1390       // Set limits for updating _last_succ form v_in and v_out
    1391       // towards the root
    1392       int up_limit_in = -1;
    1393       int up_limit_out = -1;
    1394       if (_last_succ[join] == v_in) {
    1395         up_limit_out = join;
    1396       } else {
    1397         up_limit_in = join;
     1345        // Handle the case when old_rev_thread equals to v_in
     1346        // (it also means that join and v_out coincide)
     1347        int thread_continue = old_rev_thread == v_in ?
     1348          _thread[old_last_succ] : _thread[v_in];
     1349
     1350        // Update _thread and _parent along the stem nodes (i.e. the nodes
     1351        // between u_in and u_out, whose parent have to be changed)
     1352        int stem = u_in;              // the current stem node
     1353        int par_stem = v_in;          // the new parent of stem
     1354        int next_stem;                // the next stem node
     1355        int last = _last_succ[u_in];  // the last successor of stem
     1356        int before, after = _thread[last];
     1357        _thread[v_in] = u_in;
     1358        _dirty_revs.clear();
     1359        _dirty_revs.push_back(v_in);
     1360        while (stem != u_out) {
     1361          // Insert the next stem node into the thread list
     1362          next_stem = _parent[stem];
     1363          _thread[last] = next_stem;
     1364          _dirty_revs.push_back(last);
     1365
     1366          // Remove the subtree of stem from the thread list
     1367          before = _rev_thread[stem];
     1368          _thread[before] = after;
     1369          _rev_thread[after] = before;
     1370
     1371          // Change the parent node and shift stem nodes
     1372          _parent[stem] = par_stem;
     1373          par_stem = stem;
     1374          stem = next_stem;
     1375
     1376          // Update last and after
     1377          last = _last_succ[stem] == _last_succ[par_stem] ?
     1378            _rev_thread[par_stem] : _last_succ[stem];
     1379          after = _thread[last];
     1380        }
     1381        _parent[u_out] = par_stem;
     1382        _thread[last] = thread_continue;
     1383        _rev_thread[thread_continue] = last;
     1384        _last_succ[u_out] = last;
     1385
     1386        // Remove the subtree of u_out from the thread list except for
     1387        // the case when old_rev_thread equals to v_in
     1388        if (old_rev_thread != v_in) {
     1389          _thread[old_rev_thread] = after;
     1390          _rev_thread[after] = old_rev_thread;
     1391        }
     1392
     1393        // Update _rev_thread using the new _thread values
     1394        for (int i = 0; i != int(_dirty_revs.size()); ++i) {
     1395          int u = _dirty_revs[i];
     1396          _rev_thread[_thread[u]] = u;
     1397        }
     1398
     1399        // Update _pred, _pred_dir, _last_succ and _succ_num for the
     1400        // stem nodes from u_out to u_in
     1401        int tmp_sc = 0, tmp_ls = _last_succ[u_out];
     1402        for (int u = u_out, p = _parent[u]; u != u_in; u = p, p = _parent[u]) {
     1403          _pred[u] = _pred[p];
     1404          _pred_dir[u] = -_pred_dir[p];
     1405          tmp_sc += _succ_num[u] - _succ_num[p];
     1406          _succ_num[u] = tmp_sc;
     1407          _last_succ[p] = tmp_ls;
     1408        }
     1409        _pred[u_in] = in_arc;
     1410        _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN;
     1411        _succ_num[u_in] = old_succ_num;
    13981412      }
    13991413
    14001414      // Update _last_succ from v_in towards the root
    1401       for (u = v_in; u != up_limit_in && _last_succ[u] == v_in;
    1402            u = _parent[u]) {
    1403         _last_succ[u] = _last_succ[u_out];
    1404       }
     1415      int up_limit_out = _last_succ[join] == v_in ? join : -1;
     1416      int last_succ_out = _last_succ[u_out];
     1417      for (int u = v_in; u != -1 && _last_succ[u] == v_in; u = _parent[u]) {
     1418        _last_succ[u] = last_succ_out;
     1419      }
     1420
    14051421      // Update _last_succ from v_out towards the root
    14061422      if (join != old_rev_thread && v_in != old_rev_thread) {
    1407         for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
     1423        for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
    14081424             u = _parent[u]) {
    14091425          _last_succ[u] = old_rev_thread;
    14101426        }
    1411       } else {
    1412         for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
     1427      }
     1428      else if (last_succ_out != old_last_succ) {
     1429        for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
    14131430             u = _parent[u]) {
    1414           _last_succ[u] = _last_succ[u_out];
     1431          _last_succ[u] = last_succ_out;
    14151432        }
    14161433      }
    14171434
    14181435      // Update _succ_num from v_in to join
    1419       for (u = v_in; u != join; u = _parent[u]) {
     1436      for (int u = v_in; u != join; u = _parent[u]) {
    14201437        _succ_num[u] += old_succ_num;
    14211438      }
    14221439      // Update _succ_num from v_out to join
    1423       for (u = v_out; u != join; u = _parent[u]) {
     1440      for (int u = v_out; u != join; u = _parent[u]) {
    14241441        _succ_num[u] -= old_succ_num;
    14251442      }
    14261443    }
    14271444
    1428     // Update potentials
     1445    // Update potentials in the subtree that has been moved
    14291446    void updatePotential() {
    1430       Cost sigma = _forward[u_in] ?
    1431         _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] :
    1432         _pi[v_in] - _pi[u_in] + _cost[_pred[u_in]];
    1433       // Update potentials in the subtree, which has been moved
     1447      Cost sigma = _pi[v_in] - _pi[u_in] -
     1448                   _pred_dir[u_in] * _cost[in_arc];
    14341449      int end = _thread[_last_succ[u_in]];
    14351450      for (int u = u_in; u != end; u = _thread[u]) {
Note: See TracChangeset for help on using the changeset viewer.