equal
deleted
inserted
replaced
78 |
78 |
79 /*Reverse_bfs from t, to find the starting level.*/ |
79 /*Reverse_bfs from t, to find the starting level.*/ |
80 |
80 |
81 reverse_bfs<list_graph> bfs(G, t); |
81 reverse_bfs<list_graph> bfs(G, t); |
82 bfs.run(); |
82 bfs.run(); |
83 for(each_node_iterator v=G.first_node(); v.is_valid(); ++v) |
83 for(each_node_iterator v=G.first_node(); v.valid(); ++v) |
84 { |
84 { |
85 int dist=bfs.dist(v); |
85 int dist=bfs.dist(v); |
86 level.put(v, dist); |
86 level.put(v, dist); |
87 ++numb[dist]; |
87 ++numb[dist]; |
88 } |
88 } |
91 level.put(s,n); |
91 level.put(s,n); |
92 |
92 |
93 |
93 |
94 /* Starting flow. It is everywhere 0 at the moment. */ |
94 /* Starting flow. It is everywhere 0 at the moment. */ |
95 |
95 |
96 for(out_edge_iterator i=G.first_out_edge(s); i.is_valid(); ++i) |
96 for(out_edge_iterator i=G.first_out_edge(s); i.valid(); ++i) |
97 { |
97 { |
98 node_iterator w=G.head(i); |
98 node_iterator w=G.head(i); |
99 flow.put(i, capacity.get(i)); |
99 flow.put(i, capacity.get(i)); |
100 stack[bfs.dist(w)].push(w); |
100 stack[bfs.dist(w)].push(w); |
101 excess.put(w, capacity.get(i)); |
101 excess.put(w, capacity.get(i)); |
124 node_iterator w=stack[b].top(); //w is the highest label active node. |
124 node_iterator w=stack[b].top(); //w is the highest label active node. |
125 stack[b].pop(); //We delete w from the stack. |
125 stack[b].pop(); //We delete w from the stack. |
126 |
126 |
127 int newlevel=2*n-2; //In newlevel we maintain the next level of w. |
127 int newlevel=2*n-2; //In newlevel we maintain the next level of w. |
128 |
128 |
129 for(out_edge_iterator e=G.first_out_edge(w); e.is_valid(); ++e) { |
129 for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) { |
130 node_iterator v=G.head(e); |
130 node_iterator v=G.head(e); |
131 /*e is the edge wv.*/ |
131 /*e is the edge wv.*/ |
132 |
132 |
133 if (flow.get(e)<capacity.get(e)) { |
133 if (flow.get(e)<capacity.get(e)) { |
134 /*e is an edge of the residual graph */ |
134 /*e is an edge of the residual graph */ |
165 |
165 |
166 else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);} |
166 else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);} |
167 |
167 |
168 } //if (flow.get(e)<capacity.get(e)) |
168 } //if (flow.get(e)<capacity.get(e)) |
169 |
169 |
170 } //for(out_edge_iterator e=G.first_out_edge(w); e.is_valid(); ++e) |
170 } //for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) |
171 |
171 |
172 |
172 |
173 |
173 |
174 for(in_edge_iterator e=G.first_in_edge(w); e.is_valid(); ++e) { |
174 for(in_edge_iterator e=G.first_in_edge(w); e.valid(); ++e) { |
175 node_iterator v=G.tail(e); |
175 node_iterator v=G.tail(e); |
176 /*e is the edge vw.*/ |
176 /*e is the edge vw.*/ |
177 |
177 |
178 if (excess.get(w)==0) break; |
178 if (excess.get(w)==0) break; |
179 /*It may happen, that w became inactive in the first 'for' cycle.*/ |
179 /*It may happen, that w became inactive in the first 'for' cycle.*/ |
241 stack[newlevel].push(w); |
241 stack[newlevel].push(w); |
242 b=newlevel; |
242 b=newlevel; |
243 } else { |
243 } else { |
244 /*If the level of w gets empty.*/ |
244 /*If the level of w gets empty.*/ |
245 |
245 |
246 for (each_node_iterator v=G.first_node() ; v.is_valid() ; ++v) { |
246 for (each_node_iterator v=G.first_node() ; v.valid() ; ++v) { |
247 if (level.get(v) >= l ) { |
247 if (level.get(v) >= l ) { |
248 level.put(v,n); |
248 level.put(v,n); |
249 } |
249 } |
250 } |
250 } |
251 |
251 |
275 |
275 |
276 while(e) { |
276 while(e) { |
277 if(numb[e]) ++e; |
277 if(numb[e]) ++e; |
278 else break; |
278 else break; |
279 } |
279 } |
280 for (each_node_iterator v=G.first_node(); v.is_valid(); ++v) { |
280 for (each_node_iterator v=G.first_node(); v.valid(); ++v) { |
281 if (level.get(v) > e) mincutvector.put(v, true); |
281 if (level.get(v) > e) mincutvector.put(v, true); |
282 } |
282 } |
283 |
283 |
284 |
284 |
285 } // void run() |
285 } // void run() |