Changeset 651:8c3112a66878 in lemon
- Timestamp:
- 03/24/09 00:18:25 (16 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/network_simplex.h
r650 r651 155 155 156 156 // Data for storing the spanning tree structure 157 IntVector _depth;158 157 IntVector _parent; 159 158 IntVector _pred; 160 159 IntVector _thread; 160 IntVector _rev_thread; 161 IntVector _succ_num; 162 IntVector _last_succ; 163 IntVector _dirty_revs; 161 164 BoolVector _forward; 162 165 IntVector _state; … … 851 854 _pi.resize(all_node_num, 0); 852 855 853 _depth.resize(all_node_num);854 856 _parent.resize(all_node_num); 855 857 _pred.resize(all_node_num); 856 858 _forward.resize(all_node_num); 857 859 _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); 858 863 _state.resize(all_arc_num, STATE_LOWER); 859 864 … … 882 887 // Set data for the artificial root node 883 888 _root = _node_num; 884 _depth[_root] = 0;885 889 _parent[_root] = -1; 886 890 _pred[_root] = -1; 887 891 _thread[_root] = 0; 892 _rev_thread[0] = _root; 893 _succ_num[_root] = all_node_num; 894 _last_succ[_root] = _root - 1; 888 895 _supply[_root] = 0; 889 896 _pi[_root] = 0; … … 923 930 for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) { 924 931 _thread[u] = u + 1; 925 _depth[u] = 1; 932 _rev_thread[u + 1] = u; 933 _succ_num[u] = 1; 934 _last_succ[u] = u; 926 935 _parent[u] = _root; 927 936 _pred[u] = e; … … 947 956 int u = _source[in_arc]; 948 957 int v = _target[in_arc]; 949 while (_depth[u] > _depth[v]) u = _parent[u];950 while (_depth[v] > _depth[u]) v = _parent[v];951 958 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 } 954 964 } 955 965 join = u; … … 1027 1037 } 1028 1038 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]; 1032 1045 v_out = _parent[u_out]; 1033 1046 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) 1056 1060 _thread[v_in] = stem = u_in; 1061 _dirty_revs.clear(); 1062 _dirty_revs.push_back(v_in); 1057 1063 par_stem = v_in; 1058 1064 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 1067 1076 _parent[stem] = par_stem; 1068 1077 par_stem = stem; 1069 1078 stem = new_stem; 1070 1079 1071 // Find the last successor of stem (u) and the node after it (right)1072 // according to the thread index1073 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]; 1074 1083 right = _thread[u]; 1075 1084 } 1076 1085 _parent[u_out] = par_stem; 1077 1086 _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; 1090 1108 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; 1095 1116 } 1096 1117 _pred[u_in] = in_arc; 1097 1118 _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() { 1103 1161 Cost sigma = _forward[u_in] ? 1104 1162 _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] : 1105 1163 _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 } 1111 1180 } 1112 1181 } … … 1140 1209 changeFlow(change); 1141 1210 if (change) { 1142 updateThreadParent(); 1143 updatePredArc(); 1144 updateDepthPotential(); 1211 updateTreeStructure(); 1212 updatePotential(); 1145 1213 } 1146 1214 }
Note: See TracChangeset
for help on using the changeset viewer.