141 void init() { |
141 void init() { |
142 createStructures(); |
142 createStructures(); |
143 |
143 |
144 _root = NodeIt(_graph); |
144 _root = NodeIt(_graph); |
145 for (NodeIt n(_graph); n != INVALID; ++n) { |
145 for (NodeIt n(_graph); n != INVALID; ++n) { |
146 _pred->set(n, _root); |
146 (*_pred)[n] = _root; |
147 _order->set(n, -1); |
147 (*_order)[n] = -1; |
148 } |
148 } |
149 _pred->set(_root, INVALID); |
149 (*_pred)[_root] = INVALID; |
150 _weight->set(_root, std::numeric_limits<Value>::max()); |
150 (*_weight)[_root] = std::numeric_limits<Value>::max(); |
151 } |
151 } |
152 |
152 |
153 |
153 |
154 // Start the algorithm |
154 // Start the algorithm |
155 void start() { |
155 void start() { |
162 fa.source(n); |
162 fa.source(n); |
163 fa.target(pn); |
163 fa.target(pn); |
164 |
164 |
165 fa.runMinCut(); |
165 fa.runMinCut(); |
166 |
166 |
167 _weight->set(n, fa.flowValue()); |
167 (*_weight)[n] = fa.flowValue(); |
168 |
168 |
169 for (NodeIt nn(_graph); nn != INVALID; ++nn) { |
169 for (NodeIt nn(_graph); nn != INVALID; ++nn) { |
170 if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) { |
170 if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) { |
171 _pred->set(nn, n); |
171 (*_pred)[nn] = n; |
172 } |
172 } |
173 } |
173 } |
174 if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) { |
174 if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) { |
175 _pred->set(n, (*_pred)[pn]); |
175 (*_pred)[n] = (*_pred)[pn]; |
176 _pred->set(pn, n); |
176 (*_pred)[pn] = n; |
177 _weight->set(n, (*_weight)[pn]); |
177 (*_weight)[n] = (*_weight)[pn]; |
178 _weight->set(pn, fa.flowValue()); |
178 (*_weight)[pn] = fa.flowValue(); |
179 } |
179 } |
180 } |
180 } |
181 |
181 |
182 _order->set(_root, 0); |
182 (*_order)[_root] = 0; |
183 int index = 1; |
183 int index = 1; |
184 |
184 |
185 for (NodeIt n(_graph); n != INVALID; ++n) { |
185 for (NodeIt n(_graph); n != INVALID; ++n) { |
186 std::vector<Node> st; |
186 std::vector<Node> st; |
187 Node nn = n; |
187 Node nn = n; |
188 while ((*_order)[nn] == -1) { |
188 while ((*_order)[nn] == -1) { |
189 st.push_back(nn); |
189 st.push_back(nn); |
190 nn = (*_pred)[nn]; |
190 nn = (*_pred)[nn]; |
191 } |
191 } |
192 while (!st.empty()) { |
192 while (!st.empty()) { |
193 _order->set(st.back(), index++); |
193 (*_order)[st.back()] = index++; |
194 st.pop_back(); |
194 st.pop_back(); |
195 } |
195 } |
196 } |
196 } |
197 } |
197 } |
198 |
198 |
307 sn = (*_pred)[sn]; |
307 sn = (*_pred)[sn]; |
308 } |
308 } |
309 } |
309 } |
310 |
310 |
311 typename Graph::template NodeMap<bool> reached(_graph, false); |
311 typename Graph::template NodeMap<bool> reached(_graph, false); |
312 reached.set(_root, true); |
312 reached[_root] = true; |
313 cutMap.set(_root, !s_root); |
313 cutMap.set(_root, !s_root); |
314 reached.set(rn, true); |
314 reached[rn] = true; |
315 cutMap.set(rn, s_root); |
315 cutMap.set(rn, s_root); |
316 |
316 |
317 std::vector<Node> st; |
317 std::vector<Node> st; |
318 for (NodeIt n(_graph); n != INVALID; ++n) { |
318 for (NodeIt n(_graph); n != INVALID; ++n) { |
319 st.clear(); |
319 st.clear(); |