1024 } else { |
1034 } else { |
1025 _state[in_arc] = -_state[in_arc]; |
1035 _state[in_arc] = -_state[in_arc]; |
1026 } |
1036 } |
1027 } |
1037 } |
1028 |
1038 |
1029 // Update _thread and _parent vectors |
1039 // Update the tree structure |
1030 void updateThreadParent() { |
1040 void updateTreeStructure() { |
1031 int u; |
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]; |
1032 v_out = _parent[u_out]; |
1045 v_out = _parent[u_out]; |
1033 |
1046 |
1034 // Handle the case when join and v_out coincide |
1047 u = _last_succ[u_in]; // the last successor of u_in |
1035 bool par_first = false; |
1048 right = _thread[u]; // the node after it |
1036 if (join == v_out) { |
1049 |
1037 for (u = join; u != u_in && u != v_in; u = _thread[u]) ; |
1050 // Handle the case when old_rev_thread equals to v_in |
1038 if (u == v_in) { |
1051 // (it also means that join and v_out coincide) |
1039 par_first = true; |
1052 if (old_rev_thread == v_in) { |
1040 while (_thread[u] != u_out) u = _thread[u]; |
1053 last = _thread[_last_succ[u_out]]; |
1041 first = u; |
1054 } else { |
1042 } |
1055 last = _thread[v_in]; |
1043 } |
1056 } |
1044 |
1057 |
1045 // Find the last successor of u_in (u) and the node after it (right) |
1058 // Update _thread and _parent along the stem nodes (i.e. the nodes |
1046 // according to the thread index |
1059 // between u_in and u_out, whose parent have to be changed) |
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 |
|
1056 _thread[v_in] = stem = u_in; |
1060 _thread[v_in] = stem = u_in; |
|
1061 _dirty_revs.clear(); |
|
1062 _dirty_revs.push_back(v_in); |
1057 par_stem = v_in; |
1063 par_stem = v_in; |
1058 while (stem != u_out) { |
1064 while (stem != u_out) { |
1059 _thread[u] = new_stem = _parent[stem]; |
1065 // Insert the next stem node into the thread list |
1060 |
1066 new_stem = _parent[stem]; |
1061 // Find the node just before the stem node (u) according to |
1067 _thread[u] = new_stem; |
1062 // the original thread index |
1068 _dirty_revs.push_back(u); |
1063 for (u = new_stem; _thread[u] != stem; u = _thread[u]) ; |
1069 |
1064 _thread[u] = right; |
1070 // Remove the subtree of stem from the thread list |
1065 |
1071 w = _rev_thread[stem]; |
1066 // Change the parent node of stem and shift stem and par_stem nodes |
1072 _thread[w] = right; |
|
1073 _rev_thread[right] = w; |
|
1074 |
|
1075 // Change the parent node and shift stem nodes |
1067 _parent[stem] = par_stem; |
1076 _parent[stem] = par_stem; |
1068 par_stem = stem; |
1077 par_stem = stem; |
1069 stem = new_stem; |
1078 stem = new_stem; |
1070 |
1079 |
1071 // Find the last successor of stem (u) and the node after it (right) |
1080 // Update u and right |
1072 // according to the thread index |
1081 u = _last_succ[stem] == _last_succ[par_stem] ? |
1073 for (u = stem; _depth[_thread[u]] > _depth[stem]; u = _thread[u]) ; |
1082 _rev_thread[par_stem] : _last_succ[stem]; |
1074 right = _thread[u]; |
1083 right = _thread[u]; |
1075 } |
1084 } |
1076 _parent[u_out] = par_stem; |
1085 _parent[u_out] = par_stem; |
1077 _thread[u] = last; |
1086 _thread[u] = last; |
1078 |
1087 _rev_thread[last] = u; |
1079 if (join == v_out && par_first) { |
1088 _last_succ[u_out] = u; |
1080 if (first != v_in) _thread[first] = right; |
1089 |
1081 } else { |
1090 // Remove the subtree of u_out from the thread list except for |
1082 for (u = v_out; _thread[u] != u_out; u = _thread[u]) ; |
1091 // the case when old_rev_thread equals to v_in |
1083 _thread[u] = right; |
1092 // (it also means that join and v_out coincide) |
1084 } |
1093 if (old_rev_thread != v_in) { |
1085 } |
1094 _thread[old_rev_thread] = right; |
1086 |
1095 _rev_thread[right] = old_rev_thread; |
1087 // Update _pred and _forward vectors |
1096 } |
1088 void updatePredArc() { |
1097 |
1089 int u = u_out, v; |
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; |
1090 while (u != u_in) { |
1108 while (u != u_in) { |
1091 v = _parent[u]; |
1109 w = _parent[u]; |
1092 _pred[u] = _pred[v]; |
1110 _pred[u] = _pred[w]; |
1093 _forward[u] = !_forward[v]; |
1111 _forward[u] = !_forward[w]; |
1094 u = v; |
1112 tmp_sc += _succ_num[u] - _succ_num[w]; |
|
1113 _succ_num[u] = tmp_sc; |
|
1114 _last_succ[w] = tmp_ls; |
|
1115 u = w; |
1095 } |
1116 } |
1096 _pred[u_in] = in_arc; |
1117 _pred[u_in] = in_arc; |
1097 _forward[u_in] = (u_in == _source[in_arc]); |
1118 _forward[u_in] = (u_in == _source[in_arc]); |
1098 } |
1119 _succ_num[u_in] = old_succ_num; |
1099 |
1120 |
1100 // Update _depth and _potential vectors |
1121 // Set limits for updating _last_succ form v_in and v_out |
1101 void updateDepthPotential() { |
1122 // towards the root |
1102 _depth[u_in] = _depth[v_in] + 1; |
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() { |
1103 Cost sigma = _forward[u_in] ? |
1161 Cost sigma = _forward[u_in] ? |
1104 _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] : |
1162 _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] : |
1105 _pi[v_in] - _pi[u_in] + _cost[_pred[u_in]]; |
1163 _pi[v_in] - _pi[u_in] + _cost[_pred[u_in]]; |
1106 _pi[u_in] += sigma; |
1164 if (_succ_num[u_in] > _node_num / 2) { |
1107 for(int u = _thread[u_in]; _parent[u] != -1; u = _thread[u]) { |
1165 // Update in the upper subtree (which contains the root) |
1108 _depth[u] = _depth[_parent[u]] + 1; |
1166 int before = _rev_thread[u_in]; |
1109 if (_depth[u] <= _depth[u_in]) break; |
1167 int after = _thread[_last_succ[u_in]]; |
1110 _pi[u] += sigma; |
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 } |
1111 } |
1180 } |
1112 } |
1181 } |
1113 |
1182 |
1114 // Execute the algorithm |
1183 // Execute the algorithm |
1115 bool start(PivotRuleEnum pivot_rule) { |
1184 bool start(PivotRuleEnum pivot_rule) { |