equal
deleted
inserted
replaced
81 |
81 |
82 /*Reverse_bfs from t, to find the starting level.*/ |
82 /*Reverse_bfs from t, to find the starting level.*/ |
83 |
83 |
84 reverse_bfs<list_graph> bfs(G, t); |
84 reverse_bfs<list_graph> bfs(G, t); |
85 bfs.run(); |
85 bfs.run(); |
86 for(each_node_iterator v=G.first_node(); v.is_valid(); ++v) { |
86 for(each_node_iterator v=G.first_node(); v.valid(); ++v) { |
87 level.put(v, bfs.dist(v)); |
87 level.put(v, bfs.dist(v)); |
88 //std::cout << "the level of " << v << " is " << bfs.dist(v); |
88 //std::cout << "the level of " << v << " is " << bfs.dist(v); |
89 } |
89 } |
90 |
90 |
91 /*The level of s is fixed to n*/ |
91 /*The level of s is fixed to n*/ |
95 |
95 |
96 |
96 |
97 |
97 |
98 /* Starting flow. It is everywhere 0 at the moment. */ |
98 /* Starting flow. It is everywhere 0 at the moment. */ |
99 |
99 |
100 for(out_edge_iterator i=G.first_out_edge(s); i.is_valid(); ++i) |
100 for(out_edge_iterator i=G.first_out_edge(s); i.valid(); ++i) |
101 { |
101 { |
102 node_iterator w=G.head(i); |
102 node_iterator w=G.head(i); |
103 flow.put(i, capacity.get(i)); |
103 flow.put(i, capacity.get(i)); |
104 stack[bfs.dist(w)].push(w); |
104 stack[bfs.dist(w)].push(w); |
105 excess.put(w, capacity.get(i)); |
105 excess.put(w, capacity.get(i)); |
127 node_iterator w=stack[b].top(); //w is the highest label active node. |
127 node_iterator w=stack[b].top(); //w is the highest label active node. |
128 stack[b].pop(); //We delete w from the stack. |
128 stack[b].pop(); //We delete w from the stack. |
129 |
129 |
130 int newlevel=2*n-2; //In newlevel we maintain the next level of w. |
130 int newlevel=2*n-2; //In newlevel we maintain the next level of w. |
131 |
131 |
132 for(out_edge_iterator e=G.first_out_edge(w); e.is_valid(); ++e) { |
132 for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) { |
133 node_iterator v=G.head(e); |
133 node_iterator v=G.head(e); |
134 /*e is the edge wv.*/ |
134 /*e is the edge wv.*/ |
135 |
135 |
136 if (flow.get(e)<capacity.get(e)) { |
136 if (flow.get(e)<capacity.get(e)) { |
137 /*e is an edge of the residual graph */ |
137 /*e is an edge of the residual graph */ |
168 |
168 |
169 else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);} |
169 else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);} |
170 |
170 |
171 } //if (flow.get(e)<capacity.get(e)) |
171 } //if (flow.get(e)<capacity.get(e)) |
172 |
172 |
173 } //for(out_edge_iterator e=G.first_out_edge(w); e.is_valid(); ++e) |
173 } //for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) |
174 |
174 |
175 |
175 |
176 |
176 |
177 for(in_edge_iterator e=G.first_in_edge(w); e.is_valid(); ++e) { |
177 for(in_edge_iterator e=G.first_in_edge(w); e.valid(); ++e) { |
178 node_iterator v=G.tail(e); |
178 node_iterator v=G.tail(e); |
179 /*e is the edge vw.*/ |
179 /*e is the edge vw.*/ |
180 |
180 |
181 if (excess.get(w)==0) break; |
181 if (excess.get(w)==0) break; |
182 /*It may happen, that w became inactive in the first for cycle.*/ |
182 /*It may happen, that w became inactive in the first for cycle.*/ |
286 |
286 |
287 while (!queue.empty()) { |
287 while (!queue.empty()) { |
288 node_iterator w=queue.front(); |
288 node_iterator w=queue.front(); |
289 queue.pop(); |
289 queue.pop(); |
290 |
290 |
291 for(in_edge_iterator e=G.first_in_edge(w) ; e.is_valid(); ++e) { |
291 for(in_edge_iterator e=G.first_in_edge(w) ; e.valid(); ++e) { |
292 node_iterator v=G.tail(e); |
292 node_iterator v=G.tail(e); |
293 if (mincutvector.get(v) && flow.get(e) < capacity.get(e) ) { |
293 if (mincutvector.get(v) && flow.get(e) < capacity.get(e) ) { |
294 queue.push(v); |
294 queue.push(v); |
295 mincutvector.put(v, false); |
295 mincutvector.put(v, false); |
296 } |
296 } |
297 } // for |
297 } // for |
298 |
298 |
299 for(out_edge_iterator e=G.first_out_edge(w) ; e.is_valid(); ++e) { |
299 for(out_edge_iterator e=G.first_out_edge(w) ; e.valid(); ++e) { |
300 node_iterator v=G.head(e); |
300 node_iterator v=G.head(e); |
301 if (mincutvector.get(v) && flow.get(e) > 0 ) { |
301 if (mincutvector.get(v) && flow.get(e) > 0 ) { |
302 queue.push(v); |
302 queue.push(v); |
303 mincutvector.put(v, false); |
303 mincutvector.put(v, false); |
304 } |
304 } |