Changeset 97:a5127ecb2914 in lemon0.x for src/work/jacint/preflow_push_hl.h
 Timestamp:
 02/18/04 15:42:38 (16 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@126
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/jacint/preflow_push_hl.h
r88 r97 4 4 by jacint. 5 5 Runs the highest label variant of the preflow push algorithm with 6 running time O(n^2\sqrt(m)). 6 running time O(n^2\sqrt(m)), and with the 'empty level' heuristic. 7 8 'A' is a parameter for the empty_level heuristic 7 9 8 10 Member functions: … … 16 18 T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 17 19 18 Graph::EdgeMap<T> allflow() : returns the fixed maximum flow x 19 20 Graph::NodeMap<bool> mincut() : returns a 21 characteristic vector of a minimum cut. (An empty level 22 in the algorithm gives a minimum cut.) 20 FlowMap allflow() : returns the fixed maximum flow x 21 22 void mincut(CutMap& M) : sets M to the characteristic vector of a 23 minimum cut. M should be a map of bools initialized to false. 24 25 void min_mincut(CutMap& M) : sets M to the characteristic vector of the 26 minimum min cut. M should be a map of bools initialized to false. 27 28 void max_mincut(CutMap& M) : sets M to the characteristic vector of the 29 maximum min cut. M should be a map of bools initialized to false. 30 23 31 */ 24 32 … … 30 38 #include <vector> 31 39 #include <stack> 32 33 #include <reverse_bfs.h> 40 #include <queue> 34 41 35 42 namespace marci { 36 43 37 template <typename Graph, typename T> 44 template <typename Graph, typename T, 45 typename FlowMap=typename Graph::EdgeMap<T>, typename CapMap=typename Graph::EdgeMap<T>, 46 typename IntMap=typename Graph::NodeMap<int>, typename TMap=typename Graph::NodeMap<T> > 38 47 class preflow_push_hl { 39 48 … … 47 56 NodeIt s; 48 57 NodeIt t; 49 typename Graph::EdgeMap<T>flow;50 typename Graph::EdgeMap<T> capacity;58 FlowMap flow; 59 CapMap& capacity; 51 60 T value; 52 typename Graph::NodeMap<bool> mincutvector; 53 61 54 62 public: 55 63 56 preflow_push_hl(Graph& _G, NodeIt _s, NodeIt _t, 57 typename Graph::EdgeMap<T>& _capacity) : 58 G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), 59 mincutvector(_G, true) { } 60 61 62 /* 63 The run() function runs the highest label preflowpush, 64 running time: O(n^2\sqrt(m)) 65 */ 64 preflow_push_hl(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) : 65 G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { } 66 67 68 69 66 70 void run() { 67 71 68 std::cout<<"A is "<<A<<" ";69 70 typename Graph::NodeMap<int> level(G);71 typename Graph::NodeMap<T> excess(G);72 73 72 int n=G.nodeNum(); 74 73 int b=n2; 75 74 /* 76 75 b is a bound on the highest level of an active node. 77 In the beginning it is at most n2.78 76 */ 79 77 80 std::vector<int> numb(n); //The number of nodes on level i < n. 78 IntMap level(G,n); 79 TMap excess(G); 80 81 std::vector<int> numb(n); 82 /* 83 The number of nodes on level i < n. It is 84 initialized to n+1, because of the reverse_bfspart. 85 */ 86 81 87 std::vector<std::stack<NodeIt> > stack(2*n1); 82 88 //Stack of the active nodes in level i. … … 84 90 85 91 /*Reverse_bfs from t, to find the starting level.*/ 86 reverse_bfs<Graph> bfs(G, t); 87 bfs.run(); 88 for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) 89 { 90 int dist=bfs.dist(v); 91 level.set(v, dist); 92 ++numb[dist]; 93 } 94 92 level.set(t,0); 93 std::queue<NodeIt> bfs_queue; 94 bfs_queue.push(t); 95 96 while (!bfs_queue.empty()) { 97 98 NodeIt v=bfs_queue.front(); 99 bfs_queue.pop(); 100 int l=level.get(v)+1; 101 102 for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) { 103 NodeIt w=G.tail(e); 104 if ( level.get(w) == n ) { 105 bfs_queue.push(w); 106 ++numb[l]; 107 level.set(w, l); 108 } 109 } 110 } 111 95 112 level.set(s,n); 113 96 114 97 115 … … 99 117 for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e) 100 118 { 101 if ( capacity.get(e) > 0 ) { 102 NodeIt w=G.head(e); 103 if ( w!=s ) { 104 if ( excess.get(w) == 0 && w!=t ) stack[level.get(w)].push(w); 105 flow.set(e, capacity.get(e)); 106 excess.set(w, excess.get(w)+capacity.get(e)); 107 } 108 } 109 } 110 119 if ( capacity.get(e) == 0 ) continue; 120 NodeIt w=G.head(e); 121 if ( w!=s ) { 122 if ( excess.get(w) == 0 && w!=t ) stack[level.get(w)].push(w); 123 flow.set(e, capacity.get(e)); 124 excess.set(w, excess.get(w)+capacity.get(e)); 125 } 126 } 127 111 128 /* 112 129 End of preprocessing … … 114 131 115 132 116 117 133 /* 118 134 Push/relabel on the highest level active nodes. 119 135 */ 120 121 136 /*While there exists an active node.*/ 122 137 while (b) { 123 124 /*We decrease the bound if there is no active node of level b.*/ 125 if (stack[b].empty()) { 138 if ( stack[b].empty() ) { 126 139 b; 127 } else { 128 129 NodeIt w=stack[b].top(); //w is a highest label active node. 130 stack[b].pop(); 131 132 int newlevel=2*n2; //In newlevel we bound the next level of w. 133 140 continue; 141 } 142 143 NodeIt w=stack[b].top(); //w is a highest label active node. 144 stack[b].pop(); 145 int lev=level.get(w); 146 int exc=excess.get(w); 147 int newlevel=2*n2; //In newlevel we bound the next level of w. 148 149 // if ( level.get(w) < n ) { //Nem tudom ez mukodike 134 150 for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) { 135 151 136 if ( flow.get(e) < capacity.get(e) ) { 137 /*e is an edge of the residual graph */ 138 139 NodeIt v=G.head(e); /*e is the edge wv.*/ 140 141 if( level.get(w) == level.get(v)+1 ) { 142 /*Push is allowed now*/ 143 144 if ( excess.get(v)==0 && v != s && v !=t ) stack[level.get(v)].push(v); 145 /*v becomes active.*/ 146 147 if ( capacity.get(e)flow.get(e) > excess.get(w) ) { 148 /*A nonsaturating push.*/ 149 150 flow.set(e, flow.get(e)+excess.get(w)); 151 excess.set(v, excess.get(v)+excess.get(w)); 152 excess.set(w,0); 153 break; 154 155 } else { 156 /*A saturating push.*/ 157 158 excess.set(v, excess.get(v)+capacity.get(e)flow.get(e)); 159 excess.set(w, excess.get(w)capacity.get(e)+flow.get(e)); 160 flow.set(e, capacity.get(e)); 161 if ( excess.get(w)==0 ) break; 162 /*If w is not active any more, then we go on to the next node.*/ 163 164 } 165 } else { 166 newlevel = newlevel < level.get(v) ? newlevel : level.get(v); 152 if ( flow.get(e) == capacity.get(e) ) continue; 153 NodeIt v=G.head(e); 154 //e=wv 155 156 if( lev > level.get(v) ) { 157 /*Push is allowed now*/ 158 159 if ( excess.get(v)==0 && v != s && v !=t ) 160 stack[level.get(v)].push(v); 161 /*v becomes active.*/ 162 163 int cap=capacity.get(e); 164 int flo=flow.get(e); 165 int remcap=capflo; 166 167 if ( remcap >= exc ) { 168 /*A nonsaturating push.*/ 169 170 flow.set(e, flo+exc); 171 excess.set(v, excess.get(v)+exc); 172 exc=0; 173 break; 174 175 } else { 176 /*A saturating push.*/ 177 178 flow.set(e, cap ); 179 excess.set(v, excess.get(v)+remcap); 180 exc=remcap; 167 181 } 168 169 } //if the out edge wv is in the res graph 170 182 } else if ( newlevel > level.get(v) ) newlevel = level.get(v); 183 171 184 } //for out edges wv 185 186 187 if ( exc > 0 ) { 188 for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) { 189 190 if( flow.get(e) == 0 ) continue; 191 NodeIt v=G.tail(e); 192 //e=vw 193 194 if( lev > level.get(v) ) { 195 /*Push is allowed now*/ 196 197 if ( excess.get(v)==0 && v != s && v !=t) 198 stack[level.get(v)].push(v); 199 /*v becomes active.*/ 200 201 int flo=flow.get(e); 202 203 if ( flo >= exc ) { 204 /*A nonsaturating push.*/ 205 206 flow.set(e, floexc); 207 excess.set(v, excess.get(v)+exc); 208 exc=0; 209 break; 210 } else { 211 /*A saturating push.*/ 212 213 excess.set(v, excess.get(v)+flo); 214 exc=flo; 215 flow.set(e,0); 216 } 217 } else if ( newlevel > level.get(v) ) newlevel = level.get(v); 218 219 } //for in edges vw 172 220 173 174 if ( excess.get(w) > 0 ) { 175 176 for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) { 177 NodeIt v=G.tail(e); /*e is the edge vw.*/ 178 179 if( flow.get(e) > 0 ) { 180 /*e is an edge of the residual graph */ 181 182 if( level.get(w)==level.get(v)+1 ) { 183 /*Push is allowed now*/ 184 185 if ( excess.get(v)==0 && v != s && v !=t) stack[level.get(v)].push(v); 186 /*v becomes active.*/ 187 188 if ( flow.get(e) > excess.get(w) ) { 189 /*A nonsaturating push.*/ 190 191 flow.set(e, flow.get(e)excess.get(w)); 192 excess.set(v, excess.get(v)+excess.get(w)); 193 excess.set(w,0); 194 break; 195 } else { 196 /*A saturating push.*/ 197 198 excess.set(v, excess.get(v)+flow.get(e)); 199 excess.set(w, excess.get(w)flow.get(e)); 200 flow.set(e,0); 201 if ( excess.get(w)==0 ) break; 202 } 203 } else { 204 newlevel = newlevel < level.get(v) ? newlevel : level.get(v); 205 } 206 207 } //if in edge vw is in the res graph 208 209 } //for in edges vw 210 211 } // if w still has excess after the out edge for cycle 212 213 214 /* 215 Relabel 216 */ 221 } // if w still has excess after the out edge for cycle 222 223 excess.set(w, exc); 224 225 226 227 228 /* 229 Relabel 230 */ 231 232 if ( exc > 0 ) { 233 //now 'lev' is the old level of w 234 level.set(w,++newlevel); 217 235 218 if ( excess.get(w) > 0 ) { 219 220 int oldlevel=level.get(w); 221 level.set(w,++newlevel); 222 223 if ( oldlevel < n ) { 224 numb[oldlevel]; 225 226 if ( !numb[oldlevel] && oldlevel < A*n ) { //If the level of w gets empty. 227 228 for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) { 229 if (level.get(v) > oldlevel && level.get(v) < n ) level.set(v,n); 230 } 231 for (int i=oldlevel+1 ; i!=n ; ++i) numb[i]=0; 232 if ( newlevel < n ) newlevel=n; 233 } else { 234 if ( newlevel < n ) ++numb[newlevel]; 236 if ( lev < n ) { 237 numb[lev]; 238 239 if ( !numb[lev] && lev < A*n ) { //If the level of w gets empty. 240 241 for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) { 242 if (level.get(v) > lev && level.get(v) < n ) level.set(v,n); 235 243 } 244 for (int i=lev+1 ; i!=n ; ++i) numb[i]=0; 245 if ( newlevel < n ) newlevel=n; 236 246 } else { 237 if ( newlevel < n ) ++numb[newlevel];247 if ( newlevel < n ) ++numb[newlevel]; 238 248 } 239 240 stack[newlevel].push(w); 241 b=newlevel; 242 243 } 244 245 } // if stack[b] is nonempty 246 249 } 250 251 stack[newlevel].push(w); 252 b=newlevel; 253 254 } 255 247 256 } // while(b) 248 249 257 258 250 259 value = excess.get(t); 251 260 /*Max flow value.*/ … … 272 281 */ 273 282 274 T flowonedge( EdgeIt e) {283 T flowonedge(const EdgeIt e) { 275 284 return flow.get(e); 276 285 } … … 282 291 */ 283 292 284 typename Graph::EdgeMap<T>allflow() {293 FlowMap allflow() { 285 294 return flow; 286 295 } … … 288 297 289 298 290 /* 291 Returns a minimum cut by using a reverse bfs from t in the residual graph. 299 300 /* 301 Returns the minimum min cut, by a bfs from s in the residual graph. 292 302 */ 293 303 294 typename Graph::NodeMap<bool> mincut() { 304 template<typename CutMap> 305 void mincut(CutMap& M) { 295 306 296 307 std::queue<NodeIt> queue; 297 308 298 mincutvector.set(t,false);299 queue.push( t);309 M.set(s,true); 310 queue.push(s); 300 311 301 312 while (!queue.empty()) { 302 313 NodeIt w=queue.front(); 303 314 queue.pop(); 315 316 for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) { 317 NodeIt v=G.head(e); 318 if (!M.get(v) && flow.get(e) < capacity.get(e) ) { 319 queue.push(v); 320 M.set(v, true); 321 } 322 } 304 323 305 324 for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) { 306 325 NodeIt v=G.tail(e); 307 if ( mincutvector.get(v) && flow.get(e) < capacity.get(e)) {326 if (!M.get(v) && flow.get(e) > 0 ) { 308 327 queue.push(v); 309 mincutvector.set(v, false); 310 } 311 } // for 328 M.set(v, true); 329 } 330 } 331 332 } 333 } 334 335 336 337 /* 338 Returns the maximum min cut, by a reverse bfs 339 from t in the residual graph. 340 */ 341 342 template<typename CutMap> 343 void max_mincut(CutMap& M) { 344 345 std::queue<NodeIt> queue; 346 347 M.set(t,true); 348 queue.push(t); 349 350 while (!queue.empty()) { 351 NodeIt w=queue.front(); 352 queue.pop(); 353 354 for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) { 355 NodeIt v=G.tail(e); 356 if (!M.get(v) && flow.get(e) < capacity.get(e) ) { 357 queue.push(v); 358 M.set(v, true); 359 } 360 } 312 361 313 362 for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) { 314 363 NodeIt v=G.head(e); 315 if ( mincutvector.get(v) && flow.get(e) > 0 ) {364 if (!M.get(v) && flow.get(e) > 0 ) { 316 365 queue.push(v); 317 mincutvector.set(v, false); 318 } 319 } // for 320 366 M.set(v, true); 367 } 368 } 321 369 } 322 370 323 return mincutvector; 324 325 } 371 for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v) { 372 M.set(v, !M.get(v)); 373 } 374 375 } 376 377 378 379 template<typename CutMap> 380 void min_mincut(CutMap& M) { 381 mincut(M); 382 } 383 384 385 326 386 }; 327 387 }//namespace marci
Note: See TracChangeset
for help on using the changeset viewer.