COIN-OR::LEMON - Graph Library

Changeset 651:8c3112a66878 in lemon for lemon


Ignore:
Timestamp:
03/24/09 00:18:25 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Use XTI implementation instead of ATI in NetworkSimplex? (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/network_simplex.h

    r650 r651  
    155155
    156156    // Data for storing the spanning tree structure
    157     IntVector _depth;
    158157    IntVector _parent;
    159158    IntVector _pred;
    160159    IntVector _thread;
     160    IntVector _rev_thread;
     161    IntVector _succ_num;
     162    IntVector _last_succ;
     163    IntVector _dirty_revs;
    161164    BoolVector _forward;
    162165    IntVector _state;
     
    851854      _pi.resize(all_node_num, 0);
    852855
    853       _depth.resize(all_node_num);
    854856      _parent.resize(all_node_num);
    855857      _pred.resize(all_node_num);
    856858      _forward.resize(all_node_num);
    857859      _thread.resize(all_node_num);
     860      _rev_thread.resize(all_node_num);
     861      _succ_num.resize(all_node_num);
     862      _last_succ.resize(all_node_num);
    858863      _state.resize(all_arc_num, STATE_LOWER);
    859864
     
    882887      // Set data for the artificial root node
    883888      _root = _node_num;
    884       _depth[_root] = 0;
    885889      _parent[_root] = -1;
    886890      _pred[_root] = -1;
    887891      _thread[_root] = 0;
     892      _rev_thread[0] = _root;
     893      _succ_num[_root] = all_node_num;
     894      _last_succ[_root] = _root - 1;
    888895      _supply[_root] = 0;
    889896      _pi[_root] = 0;
     
    923930      for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
    924931        _thread[u] = u + 1;
    925         _depth[u] = 1;
     932        _rev_thread[u + 1] = u;
     933        _succ_num[u] = 1;
     934        _last_succ[u] = u;
    926935        _parent[u] = _root;
    927936        _pred[u] = e;
     
    947956      int u = _source[in_arc];
    948957      int v = _target[in_arc];
    949       while (_depth[u] > _depth[v]) u = _parent[u];
    950       while (_depth[v] > _depth[u]) v = _parent[v];
    951958      while (u != v) {
    952         u = _parent[u];
    953         v = _parent[v];
     959        if (_succ_num[u] < _succ_num[v]) {
     960          u = _parent[u];
     961        } else {
     962          v = _parent[v];
     963        }
    954964      }
    955965      join = u;
     
    10271037    }
    10281038
    1029     // Update _thread and _parent vectors
    1030     void updateThreadParent() {
    1031       int u;
     1039    // Update the tree structure
     1040    void updateTreeStructure() {
     1041      int u, w;
     1042      int old_rev_thread = _rev_thread[u_out];
     1043      int old_succ_num = _succ_num[u_out];
     1044      int old_last_succ = _last_succ[u_out];
    10321045      v_out = _parent[u_out];
    10331046
    1034       // Handle the case when join and v_out coincide
    1035       bool par_first = false;
    1036       if (join == v_out) {
    1037         for (u = join; u != u_in && u != v_in; u = _thread[u]) ;
    1038         if (u == v_in) {
    1039           par_first = true;
    1040           while (_thread[u] != u_out) u = _thread[u];
    1041           first = u;
    1042         }
    1043       }
    1044 
    1045       // Find the last successor of u_in (u) and the node after it (right)
    1046       // according to the thread index
    1047       for (u = u_in; _depth[_thread[u]] > _depth[u_in]; u = _thread[u]) ;
    1048       right = _thread[u];
    1049       if (_thread[v_in] == u_out) {
    1050         for (last = u; _depth[last] > _depth[u_out]; last = _thread[last]) ;
    1051         if (last == u_out) last = _thread[last];
    1052       }
    1053       else last = _thread[v_in];
    1054 
    1055       // Update stem nodes
     1047      u = _last_succ[u_in];  // the last successor of u_in
     1048      right = _thread[u];    // the node after it
     1049
     1050      // Handle the case when old_rev_thread equals to v_in
     1051      // (it also means that join and v_out coincide)
     1052      if (old_rev_thread == v_in) {
     1053        last = _thread[_last_succ[u_out]];
     1054      } else {
     1055        last = _thread[v_in];
     1056      }
     1057
     1058      // Update _thread and _parent along the stem nodes (i.e. the nodes
     1059      // between u_in and u_out, whose parent have to be changed)
    10561060      _thread[v_in] = stem = u_in;
     1061      _dirty_revs.clear();
     1062      _dirty_revs.push_back(v_in);
    10571063      par_stem = v_in;
    10581064      while (stem != u_out) {
    1059         _thread[u] = new_stem = _parent[stem];
    1060 
    1061         // Find the node just before the stem node (u) according to
    1062         // the original thread index
    1063         for (u = new_stem; _thread[u] != stem; u = _thread[u]) ;
    1064         _thread[u] = right;
    1065 
    1066         // Change the parent node of stem and shift stem and par_stem nodes
     1065        // Insert the next stem node into the thread list
     1066        new_stem = _parent[stem];
     1067        _thread[u] = new_stem;
     1068        _dirty_revs.push_back(u);
     1069
     1070        // Remove the subtree of stem from the thread list
     1071        w = _rev_thread[stem];
     1072        _thread[w] = right;
     1073        _rev_thread[right] = w;
     1074
     1075        // Change the parent node and shift stem nodes
    10671076        _parent[stem] = par_stem;
    10681077        par_stem = stem;
    10691078        stem = new_stem;
    10701079
    1071         // Find the last successor of stem (u) and the node after it (right)
    1072         // according to the thread index
    1073         for (u = stem; _depth[_thread[u]] > _depth[stem]; u = _thread[u]) ;
     1080        // Update u and right
     1081        u = _last_succ[stem] == _last_succ[par_stem] ?
     1082          _rev_thread[par_stem] : _last_succ[stem];
    10741083        right = _thread[u];
    10751084      }
    10761085      _parent[u_out] = par_stem;
    10771086      _thread[u] = last;
    1078 
    1079       if (join == v_out && par_first) {
    1080         if (first != v_in) _thread[first] = right;
    1081       } else {
    1082         for (u = v_out; _thread[u] != u_out; u = _thread[u]) ;
    1083         _thread[u] = right;
    1084       }
    1085     }
    1086 
    1087     // Update _pred and _forward vectors
    1088     void updatePredArc() {
    1089       int u = u_out, v;
     1087      _rev_thread[last] = u;
     1088      _last_succ[u_out] = u;
     1089
     1090      // Remove the subtree of u_out from the thread list except for
     1091      // the case when old_rev_thread equals to v_in
     1092      // (it also means that join and v_out coincide)
     1093      if (old_rev_thread != v_in) {
     1094        _thread[old_rev_thread] = right;
     1095        _rev_thread[right] = old_rev_thread;
     1096      }
     1097
     1098      // Update _rev_thread using the new _thread values
     1099      for (int i = 0; i < int(_dirty_revs.size()); ++i) {
     1100        u = _dirty_revs[i];
     1101        _rev_thread[_thread[u]] = u;
     1102      }
     1103
     1104      // Update _pred, _forward, _last_succ and _succ_num for the
     1105      // stem nodes from u_out to u_in
     1106      int tmp_sc = 0, tmp_ls = _last_succ[u_out];
     1107      u = u_out;
    10901108      while (u != u_in) {
    1091         v = _parent[u];
    1092         _pred[u] = _pred[v];
    1093         _forward[u] = !_forward[v];
    1094         u = v;
     1109        w = _parent[u];
     1110        _pred[u] = _pred[w];
     1111        _forward[u] = !_forward[w];
     1112        tmp_sc += _succ_num[u] - _succ_num[w];
     1113        _succ_num[u] = tmp_sc;
     1114        _last_succ[w] = tmp_ls;
     1115        u = w;
    10951116      }
    10961117      _pred[u_in] = in_arc;
    10971118      _forward[u_in] = (u_in == _source[in_arc]);
    1098     }
    1099 
    1100     // Update _depth and _potential vectors
    1101     void updateDepthPotential() {
    1102       _depth[u_in] = _depth[v_in] + 1;
     1119      _succ_num[u_in] = old_succ_num;
     1120
     1121      // Set limits for updating _last_succ form v_in and v_out
     1122      // towards the root
     1123      int up_limit_in = -1;
     1124      int up_limit_out = -1;
     1125      if (_last_succ[join] == v_in) {
     1126        up_limit_out = join;
     1127      } else {
     1128        up_limit_in = join;
     1129      }
     1130
     1131      // Update _last_succ from v_in towards the root
     1132      for (u = v_in; u != up_limit_in && _last_succ[u] == v_in;
     1133           u = _parent[u]) {
     1134        _last_succ[u] = _last_succ[u_out];
     1135      }
     1136      // Update _last_succ from v_out towards the root
     1137      if (join != old_rev_thread && v_in != old_rev_thread) {
     1138        for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
     1139             u = _parent[u]) {
     1140          _last_succ[u] = old_rev_thread;
     1141        }
     1142      } else {
     1143        for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
     1144             u = _parent[u]) {
     1145          _last_succ[u] = _last_succ[u_out];
     1146        }
     1147      }
     1148
     1149      // Update _succ_num from v_in to join
     1150      for (u = v_in; u != join; u = _parent[u]) {
     1151        _succ_num[u] += old_succ_num;
     1152      }
     1153      // Update _succ_num from v_out to join
     1154      for (u = v_out; u != join; u = _parent[u]) {
     1155        _succ_num[u] -= old_succ_num;
     1156      }
     1157    }
     1158
     1159    // Update potentials
     1160    void updatePotential() {
    11031161      Cost sigma = _forward[u_in] ?
    11041162        _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] :
    11051163        _pi[v_in] - _pi[u_in] + _cost[_pred[u_in]];
    1106       _pi[u_in] += sigma;
    1107       for(int u = _thread[u_in]; _parent[u] != -1; u = _thread[u]) {
    1108         _depth[u] = _depth[_parent[u]] + 1;
    1109         if (_depth[u] <= _depth[u_in]) break;
    1110         _pi[u] += sigma;
     1164      if (_succ_num[u_in] > _node_num / 2) {
     1165        // Update in the upper subtree (which contains the root)
     1166        int before = _rev_thread[u_in];
     1167        int after = _thread[_last_succ[u_in]];
     1168        _thread[before] = after;
     1169        _pi[_root] -= sigma;
     1170        for (int u = _thread[_root]; u != _root; u = _thread[u]) {
     1171          _pi[u] -= sigma;
     1172        }
     1173        _thread[before] = u_in;
     1174      } else {
     1175        // Update in the lower subtree (which has been moved)
     1176        int end = _thread[_last_succ[u_in]];
     1177        for (int u = u_in; u != end; u = _thread[u]) {
     1178          _pi[u] += sigma;
     1179        }
    11111180      }
    11121181    }
     
    11401209        changeFlow(change);
    11411210        if (change) {
    1142           updateThreadParent();
    1143           updatePredArc();
    1144           updateDepthPotential();
     1211          updateTreeStructure();
     1212          updatePotential();
    11451213        }
    11461214      }
Note: See TracChangeset for help on using the changeset viewer.