10 |
16 |
11 Parameters H0 and H1 are initialized to 20 and 10. |
17 Parameters H0 and H1 are initialized to 20 and 10. |
12 |
18 |
13 Constructors: |
19 Constructors: |
14 |
20 |
15 Preflow(Graph, Node, Node, CapMap, FlowMap) |
21 Preflow(Graph, Node, Node, CapMap, FlowMap, bool) : bool must be false if |
|
22 FlowMap is not constant zero, and should be true if it is |
16 |
23 |
17 Members: |
24 Members: |
18 |
25 |
19 void run() |
26 void run() |
20 |
27 |
27 maximum min cut. M should be a map of bools initialized to false. |
34 maximum min cut. M should be a map of bools initialized to false. |
28 |
35 |
29 void minCut(CutMap& M) : sets M to the characteristic vector of |
36 void minCut(CutMap& M) : sets M to the characteristic vector of |
30 a min cut. M should be a map of bools initialized to false. |
37 a min cut. M should be a map of bools initialized to false. |
31 |
38 |
|
39 FIXME reset |
|
40 |
32 */ |
41 */ |
33 |
42 |
34 #ifndef HUGO_PREFLOW_H |
43 #ifndef HUGO_PREFLOW_H |
35 #define HUGO_PREFLOW_H |
44 #define HUGO_PREFLOW_H |
36 |
45 |
42 |
51 |
43 namespace hugo { |
52 namespace hugo { |
44 |
53 |
45 template <typename Graph, typename T, |
54 template <typename Graph, typename T, |
46 typename CapMap=typename Graph::EdgeMap<T>, |
55 typename CapMap=typename Graph::EdgeMap<T>, |
47 typename FlowMap=typename Graph::EdgeMap<T> > |
56 typename FlowMap=typename Graph::EdgeMap<T> > |
48 class Preflow { |
57 class Preflow { |
49 |
58 |
50 typedef typename Graph::Node Node; |
59 typedef typename Graph::Node Node; |
51 typedef typename Graph::Edge Edge; |
60 typedef typename Graph::Edge Edge; |
52 typedef typename Graph::NodeIt NodeIt; |
61 typedef typename Graph::NodeIt NodeIt; |
57 Node s; |
66 Node s; |
58 Node t; |
67 Node t; |
59 const CapMap& capacity; |
68 const CapMap& capacity; |
60 FlowMap& flow; |
69 FlowMap& flow; |
61 T value; |
70 T value; |
|
71 bool constzero; |
62 |
72 |
63 public: |
73 public: |
64 Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, |
74 Preflow(Graph& _G, Node _s, Node _t, CapMap& _capacity, |
65 FlowMap& _flow ) : |
75 FlowMap& _flow, bool _constzero ) : |
66 G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow) {} |
76 G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow), constzero(_constzero) {} |
67 |
77 |
|
78 |
68 void run() { |
79 void run() { |
|
80 |
|
81 value=0; //for the subsequent runs |
69 |
82 |
70 bool phase=0; //phase 0 is the 1st phase, phase 1 is the 2nd |
83 bool phase=0; //phase 0 is the 1st phase, phase 1 is the 2nd |
71 int n=G.nodeNum(); |
84 int n=G.nodeNum(); |
72 int heur0=(int)(H0*n); //time while running 'bound decrease' |
85 int heur0=(int)(H0*n); //time while running 'bound decrease' |
73 int heur1=(int)(H1*n); //time while running 'highest label' |
86 int heur1=(int)(H1*n); //time while running 'highest label' |
87 int b=k; //bound on the highest level under n of an active node |
100 int b=k; //bound on the highest level under n of an active node |
88 |
101 |
89 typename Graph::NodeMap<int> level(G,n); |
102 typename Graph::NodeMap<int> level(G,n); |
90 typename Graph::NodeMap<T> excess(G); |
103 typename Graph::NodeMap<T> excess(G); |
91 |
104 |
92 std::vector<Node> active(n,INVALID); |
105 std::vector<Node> active(n-1,INVALID); |
93 typename Graph::NodeMap<Node> next(G,INVALID); |
106 typename Graph::NodeMap<Node> next(G,INVALID); |
94 //Stack of the active nodes in level i < n. |
107 //Stack of the active nodes in level i < n. |
95 //We use it in both phases. |
108 //We use it in both phases. |
96 |
109 |
97 typename Graph::NodeMap<Node> left(G,INVALID); |
110 typename Graph::NodeMap<Node> left(G,INVALID); |
99 std::vector<Node> level_list(n,INVALID); |
112 std::vector<Node> level_list(n,INVALID); |
100 /* |
113 /* |
101 List of the nodes in level i<n. |
114 List of the nodes in level i<n. |
102 */ |
115 */ |
103 |
116 |
104 /*Reverse_bfs from t, to find the starting level.*/ |
117 |
105 level.set(t,0); |
118 if ( constzero ) { |
106 std::queue<Node> bfs_queue; |
119 |
107 bfs_queue.push(t); |
120 /*Reverse_bfs from t, to find the starting level.*/ |
108 |
121 level.set(t,0); |
109 while (!bfs_queue.empty()) { |
122 std::queue<Node> bfs_queue; |
110 |
123 bfs_queue.push(t); |
111 Node v=bfs_queue.front(); |
124 |
112 bfs_queue.pop(); |
125 while (!bfs_queue.empty()) { |
113 int l=level[v]+1; |
126 |
114 |
127 Node v=bfs_queue.front(); |
115 InEdgeIt e; |
128 bfs_queue.pop(); |
116 for(G.first(e,v); G.valid(e); G.next(e)) { |
129 int l=level[v]+1; |
117 Node w=G.tail(e); |
130 |
118 if ( level[w] == n && w != s ) { |
131 InEdgeIt e; |
119 bfs_queue.push(w); |
132 for(G.first(e,v); G.valid(e); G.next(e)) { |
120 Node first=level_list[l]; |
133 Node w=G.tail(e); |
121 if ( G.valid(first) ) left.set(first,w); |
134 if ( level[w] == n && w != s ) { |
122 right.set(w,first); |
135 bfs_queue.push(w); |
123 level_list[l]=w; |
136 Node first=level_list[l]; |
124 level.set(w, l); |
137 if ( G.valid(first) ) left.set(first,w); |
125 } |
138 right.set(w,first); |
126 } |
139 level_list[l]=w; |
127 } |
140 level.set(w, l); |
128 |
141 } |
129 level.set(s,n); |
142 } |
130 |
143 } |
131 |
144 |
132 /* Starting flow. It is everywhere 0 at the moment. */ |
145 //the starting flow |
133 OutEdgeIt e; |
146 OutEdgeIt e; |
134 for(G.first(e,s); G.valid(e); G.next(e)) |
147 for(G.first(e,s); G.valid(e); G.next(e)) |
135 { |
148 { |
136 T c=capacity[e]; |
149 T c=capacity[e]; |
137 if ( c == 0 ) continue; |
150 if ( c == 0 ) continue; |
138 Node w=G.head(e); |
151 Node w=G.head(e); |
139 if ( level[w] < n ) { |
152 if ( level[w] < n ) { |
143 } |
156 } |
144 flow.set(e, c); |
157 flow.set(e, c); |
145 excess.set(w, excess[w]+c); |
158 excess.set(w, excess[w]+c); |
146 } |
159 } |
147 } |
160 } |
|
161 } |
|
162 else |
|
163 { |
|
164 |
|
165 /* |
|
166 Reverse_bfs from t in the residual graph, |
|
167 to find the starting level. |
|
168 */ |
|
169 level.set(t,0); |
|
170 std::queue<Node> bfs_queue; |
|
171 bfs_queue.push(t); |
|
172 |
|
173 while (!bfs_queue.empty()) { |
|
174 |
|
175 Node v=bfs_queue.front(); |
|
176 bfs_queue.pop(); |
|
177 int l=level[v]+1; |
|
178 |
|
179 InEdgeIt e; |
|
180 for(G.first(e,v); G.valid(e); G.next(e)) { |
|
181 if ( capacity[e] == flow[e] ) continue; |
|
182 Node w=G.tail(e); |
|
183 if ( level[w] == n && w != s ) { |
|
184 bfs_queue.push(w); |
|
185 Node first=level_list[l]; |
|
186 if ( G.valid(first) ) left.set(first,w); |
|
187 right.set(w,first); |
|
188 level_list[l]=w; |
|
189 level.set(w, l); |
|
190 } |
|
191 } |
|
192 |
|
193 OutEdgeIt f; |
|
194 for(G.first(f,v); G.valid(f); G.next(f)) { |
|
195 if ( 0 == flow[f] ) continue; |
|
196 Node w=G.head(f); |
|
197 if ( level[w] == n && w != s ) { |
|
198 bfs_queue.push(w); |
|
199 Node first=level_list[l]; |
|
200 if ( G.valid(first) ) left.set(first,w); |
|
201 right.set(w,first); |
|
202 level_list[l]=w; |
|
203 level.set(w, l); |
|
204 } |
|
205 } |
|
206 } |
|
207 |
|
208 |
|
209 /* |
|
210 Counting the excess |
|
211 */ |
|
212 NodeIt v; |
|
213 for(G.first(v); G.valid(v); G.next(v)) { |
|
214 T exc=0; |
|
215 |
|
216 InEdgeIt e; |
|
217 for(G.first(e,v); G.valid(e); G.next(e)) exc+=flow[e]; |
|
218 OutEdgeIt f; |
|
219 for(G.first(f,v); G.valid(f); G.next(f)) exc-=flow[e]; |
|
220 |
|
221 excess.set(v,exc); |
|
222 |
|
223 //putting the active nodes into the stack |
|
224 int lev=level[v]; |
|
225 if ( exc > 0 && lev < n ) { |
|
226 next.set(v,active[lev]); |
|
227 active[lev]=v; |
|
228 } |
|
229 } |
|
230 |
|
231 |
|
232 //the starting flow |
|
233 OutEdgeIt e; |
|
234 for(G.first(e,s); G.valid(e); G.next(e)) |
|
235 { |
|
236 T rem=capacity[e]-flow[e]; |
|
237 if ( rem == 0 ) continue; |
|
238 Node w=G.head(e); |
|
239 if ( level[w] < n ) { |
|
240 if ( excess[w] == 0 && w!=t ) { |
|
241 next.set(w,active[level[w]]); |
|
242 active[level[w]]=w; |
|
243 } |
|
244 flow.set(e, capacity[e]); |
|
245 excess.set(w, excess[w]+rem); |
|
246 } |
|
247 } |
|
248 |
|
249 InEdgeIt f; |
|
250 for(G.first(f,s); G.valid(f); G.next(f)) |
|
251 { |
|
252 if ( flow[f] == 0 ) continue; |
|
253 Node w=G.head(f); |
|
254 if ( level[w] < n ) { |
|
255 if ( excess[w] == 0 && w!=t ) { |
|
256 next.set(w,active[level[w]]); |
|
257 active[level[w]]=w; |
|
258 } |
|
259 excess.set(w, excess[w]+flow[f]); |
|
260 flow.set(f, 0); |
|
261 } |
|
262 } |
|
263 } |
|
264 |
|
265 |
|
266 |
148 |
267 |
149 /* |
268 /* |
150 End of preprocessing |
269 End of preprocessing |
151 */ |
270 */ |
152 |
271 |
353 |
472 |
354 level.set(w,n); |
473 level.set(w,n); |
355 b=lev-1; |
474 b=lev-1; |
356 k=b; |
475 k=b; |
357 //gapping ends |
476 //gapping ends |
|
477 |
358 } else { |
478 } else { |
359 |
479 |
360 if ( newlevel == n ) level.set(w,n); |
480 if ( newlevel == n ) level.set(w,n); |
361 else { |
481 else { |
362 level.set(w,++newlevel); |
482 level.set(w,++newlevel); |
363 next.set(w,active[newlevel]); |
483 next.set(w,active[newlevel]); |
364 active[newlevel]=w; |
484 active[newlevel]=w; |
365 if ( what_heur ) b=newlevel; |
485 if ( what_heur ) b=newlevel; |
366 if ( k < newlevel ) ++k; |
486 if ( k < newlevel ) ++k; //now k=newlevel |
367 Node first=level_list[newlevel]; |
487 Node first=level_list[newlevel]; |
368 if ( G.valid(first) ) left.set(first,w); |
488 if ( G.valid(first) ) left.set(first,w); |
369 right.set(w,first); |
489 right.set(w,first); |
370 left.set(w,INVALID); |
490 left.set(w,INVALID); |
371 level_list[newlevel]=w; |
491 level_list[newlevel]=w; |
516 template<typename CutMap> |
636 template<typename CutMap> |
517 void minCut(CutMap& M) { |
637 void minCut(CutMap& M) { |
518 minMinCut(M); |
638 minMinCut(M); |
519 } |
639 } |
520 |
640 |
|
641 |
|
642 void reset_target (Node _t) {t=_t;} |
|
643 void reset_source (Node _s) {s=_s;} |
|
644 |
|
645 template<typename _CapMap> |
|
646 void reset_cap (_CapMap _cap) {capacity=_cap;} |
|
647 |
|
648 template<typename _FlowMap> |
|
649 void reset_cap (_FlowMap _flow, bool _constzero) { |
|
650 flow=_flow; |
|
651 constzero=_constzero; |
|
652 } |
|
653 |
|
654 |
521 |
655 |
522 }; |
656 }; |
523 |
657 |
524 } //namespace hugo |
658 } //namespace hugo |
525 |
659 |