Changeset 211:9222a9b8b323 in lemon0.x for src/work/jacint/preflow.h
 Timestamp:
 03/19/04 23:16:05 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@306
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/jacint/preflow.h
r174 r211 1 1 // * C++ * 2 2 /* 3 preflow.h4 by jacint.5 3 Heuristics: 6 4 2 phase … … 13 11 Parameters H0 and H1 are initialized to 20 and 10. 14 12 15 The best preflow I could ever write. 16 17 The constructor runs the algorithm. 13 Constructors: 14 15 Preflow(Graph, Node, Node, CapMap, FlowMap) 18 16 19 17 Members: 20 18 21 T maxFlow() : returns the value of a maximum flow 22 23 T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 24 25 FlowMap Flow() : returns the fixed maximum flow x 19 void run() 20 21 T flowValue() : returns the value of a maximum flow 26 22 27 23 void minMinCut(CutMap& M) : sets M to the characteristic vector of the … … 36 32 */ 37 33 38 #ifndef PREFLOW_H39 #define PREFLOW_H34 #ifndef HUGO_PREFLOW_H 35 #define HUGO_PREFLOW_H 40 36 41 37 #define H0 20 … … 44 40 #include <vector> 45 41 #include <queue> 46 47 #include <time_measure.h>48 42 49 43 namespace hugo { … … 52 46 typename FlowMap=typename Graph::EdgeMap<T>, 53 47 typename CapMap=typename Graph::EdgeMap<T> > 54 class preflow {48 class Preflow { 55 49 50 typedef typename Graph::Node Node; 51 typedef typename Graph::Edge Edge; 56 52 typedef typename Graph::NodeIt NodeIt; 57 typedef typename Graph::EdgeIt EdgeIt;58 typedef typename Graph::EachNodeIt EachNodeIt;59 53 typedef typename Graph::OutEdgeIt OutEdgeIt; 60 54 typedef typename Graph::InEdgeIt InEdgeIt; 61 55 62 Graph& G;63 Node Its;64 Node Itt;65 FlowMap flow;66 CapMap& capacity;56 const Graph& G; 57 Node s; 58 Node t; 59 FlowMap& flow; 60 const CapMap& capacity; 67 61 T value; 68 62 69 63 public: 70 double time; 71 preflow(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity ) : 72 G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) 73 { 64 Preflow(Graph& _G, Node _s, Node _t, CapMap& _capacity, FlowMap& _flow ) : 65 G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) {} 66 67 68 void run() { 74 69 75 70 bool phase=0; //phase 0 is the 1st phase, phase 1 is the 2nd … … 95 90 typename Graph::NodeMap<T> excess(G); 96 91 97 std::vector<Node It> active(n);98 typename Graph::NodeMap<Node It> next(G);92 std::vector<Node> active(n,INVALID); 93 typename Graph::NodeMap<Node> next(G,INVALID); 99 94 //Stack of the active nodes in level i < n. 100 95 //We use it in both phases. 101 96 102 typename Graph::NodeMap<Node It> left(G);103 typename Graph::NodeMap<Node It> right(G);104 std::vector<Node It> level_list(n);97 typename Graph::NodeMap<Node> left(G,INVALID); 98 typename Graph::NodeMap<Node> right(G,INVALID); 99 std::vector<Node> level_list(n,INVALID); 105 100 /* 106 101 List of the nodes in level i<n. … … 109 104 /*Reverse_bfs from t, to find the starting level.*/ 110 105 level.set(t,0); 111 std::queue<Node It> bfs_queue;106 std::queue<Node> bfs_queue; 112 107 bfs_queue.push(t); 113 108 114 109 while (!bfs_queue.empty()) { 115 110 116 Node Itv=bfs_queue.front();111 Node v=bfs_queue.front(); 117 112 bfs_queue.pop(); 118 int l=level.get(v)+1; 119 120 for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) { 121 NodeIt w=G.tail(e); 122 if ( level.get(w) == n && w != s ) { 113 int l=level[v]+1; 114 115 InEdgeIt e; 116 for(G.first(e,v); G.valid(e); G.next(e)) { 117 Node w=G.tail(e); 118 if ( level[w] == n && w != s ) { 123 119 bfs_queue.push(w); 124 Node Itfirst=level_list[l];125 if ( first != 0) left.set(first,w);120 Node first=level_list[l]; 121 if ( G.valid(first) ) left.set(first,w); 126 122 right.set(w,first); 127 123 level_list[l]=w; … … 135 131 136 132 /* Starting flow. It is everywhere 0 at the moment. */ 137 for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e) 133 OutEdgeIt e; 134 for(G.first(e,s); G.valid(e); G.next(e)) 138 135 { 139 T c=capacity .get(e);136 T c=capacity[e]; 140 137 if ( c == 0 ) continue; 141 Node Itw=G.head(e);142 if ( level .get(w)< n ) {143 if ( excess .get(w)== 0 && w!=t ) {144 next.set(w,active[level .get(w)]);145 active[level .get(w)]=w;138 Node w=G.head(e); 139 if ( level[w] < n ) { 140 if ( excess[w] == 0 && w!=t ) { 141 next.set(w,active[level[w]]); 142 active[level[w]]=w; 146 143 } 147 144 flow.set(e, c); 148 excess.set(w, excess .get(w)+c);145 excess.set(w, excess[w]+c); 149 146 } 150 147 } … … 169 166 } else { 170 167 phase=1; 171 time=currTime();172 168 level.set(s,0); 173 std::queue<Node It> bfs_queue;169 std::queue<Node> bfs_queue; 174 170 bfs_queue.push(s); 175 171 176 172 while (!bfs_queue.empty()) { 177 173 178 Node Itv=bfs_queue.front();174 Node v=bfs_queue.front(); 179 175 bfs_queue.pop(); 180 int l=level.get(v)+1; 181 182 for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) { 183 if ( capacity.get(e) == flow.get(e) ) continue; 184 NodeIt u=G.tail(e); 185 if ( level.get(u) >= n ) { 176 int l=level[v]+1; 177 178 InEdgeIt e; 179 for(G.first(e,v); G.valid(e); G.next(e)) { 180 if ( capacity[e] == flow[e] ) continue; 181 Node u=G.tail(e); 182 if ( level[u] >= n ) { 186 183 bfs_queue.push(u); 187 184 level.set(u, l); 188 if ( excess .get(u)> 0 ) {185 if ( excess[u] > 0 ) { 189 186 next.set(u,active[l]); 190 187 active[l]=u; … … 193 190 } 194 191 195 for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) { 196 if ( 0 == flow.get(e) ) continue; 197 NodeIt u=G.head(e); 198 if ( level.get(u) >= n ) { 192 OutEdgeIt f; 193 for(G.first(f,v); G.valid(f); G.next(f)) { 194 if ( 0 == flow[f] ) continue; 195 Node u=G.head(f); 196 if ( level[u] >= n ) { 199 197 bfs_queue.push(u); 200 198 level.set(u, l); 201 if ( excess .get(u)> 0 ) {199 if ( excess[u] > 0 ) { 202 200 next.set(u,active[l]); 203 201 active[l]=u; … … 212 210 213 211 214 if ( active[b] == 0) b;212 if ( !G.valid(active[b]) ) b; 215 213 else { 216 214 end=false; 217 215 218 Node Itw=active[b];219 active[b]=next .get(w);220 int lev=level .get(w);221 T exc=excess .get(w);216 Node w=active[b]; 217 active[b]=next[w]; 218 int lev=level[w]; 219 T exc=excess[w]; 222 220 int newlevel=n; //bound on the next level of w 223 221 224 for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) { 225 226 if ( flow.get(e) == capacity.get(e) ) continue; 227 NodeIt v=G.head(e); 222 OutEdgeIt e; 223 for(G.first(e,w); G.valid(e); G.next(e)) { 224 225 if ( flow[e] == capacity[e] ) continue; 226 Node v=G.head(e); 228 227 //e=wv 229 228 230 if( lev > level .get(v)) {229 if( lev > level[v] ) { 231 230 /*Push is allowed now*/ 232 231 233 if ( excess .get(v)==0 && v!=t && v!=s ) {234 int lev_v=level .get(v);232 if ( excess[v]==0 && v!=t && v!=s ) { 233 int lev_v=level[v]; 235 234 next.set(v,active[lev_v]); 236 235 active[lev_v]=v; 237 236 } 238 237 239 T cap=capacity .get(e);240 T flo=flow .get(e);238 T cap=capacity[e]; 239 T flo=flow[e]; 241 240 T remcap=capflo; 242 241 … … 245 244 246 245 flow.set(e, flo+exc); 247 excess.set(v, excess .get(v)+exc);246 excess.set(v, excess[v]+exc); 248 247 exc=0; 249 248 break; … … 253 252 254 253 flow.set(e, cap); 255 excess.set(v, excess .get(v)+remcap);254 excess.set(v, excess[v]+remcap); 256 255 exc=remcap; 257 256 } 258 } else if ( newlevel > level .get(v)){259 newlevel = level .get(v);257 } else if ( newlevel > level[v] ){ 258 newlevel = level[v]; 260 259 } 261 260 … … 264 263 265 264 if ( exc > 0 ) { 266 for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) { 267 268 if( flow.get(e) == 0 ) continue; 269 NodeIt v=G.tail(e); 265 InEdgeIt e; 266 for(G.first(e,w); G.valid(e); G.next(e)) { 267 268 if( flow[e] == 0 ) continue; 269 Node v=G.tail(e); 270 270 //e=vw 271 271 272 if( lev > level .get(v)) {272 if( lev > level[v] ) { 273 273 /*Push is allowed now*/ 274 274 275 if ( excess .get(v)==0 && v!=t && v!=s ) {276 int lev_v=level .get(v);275 if ( excess[v]==0 && v!=t && v!=s ) { 276 int lev_v=level[v]; 277 277 next.set(v,active[lev_v]); 278 278 active[lev_v]=v; 279 279 } 280 280 281 T flo=flow .get(e);281 T flo=flow[e]; 282 282 283 283 if ( flo >= exc ) { … … 285 285 286 286 flow.set(e, floexc); 287 excess.set(v, excess .get(v)+exc);287 excess.set(v, excess[v]+exc); 288 288 exc=0; 289 289 break; … … 291 291 /*A saturating push.*/ 292 292 293 excess.set(v, excess .get(v)+flo);293 excess.set(v, excess[v]+flo); 294 294 exc=flo; 295 295 flow.set(e,0); 296 296 } 297 } else if ( newlevel > level .get(v)) {298 newlevel = level .get(v);297 } else if ( newlevel > level[v] ) { 298 newlevel = level[v]; 299 299 } 300 300 } //for in edges vw … … 319 319 } else { 320 320 //unlacing starts 321 Node It right_n=right.get(w);322 Node It left_n=left.get(w);323 324 if ( right_n != 0) {325 if ( left_n != 0) {321 Node right_n=right[w]; 322 Node left_n=left[w]; 323 324 if ( G.valid(right_n) ) { 325 if ( G.valid(left_n) ) { 326 326 right.set(left_n, right_n); 327 327 left.set(right_n, left_n); 328 328 } else { 329 329 level_list[lev]=right_n; 330 left.set(right_n, 0);330 left.set(right_n, INVALID); 331 331 } 332 332 } else { 333 if ( left_n != 0) {334 right.set(left_n, 0);333 if ( G.valid(left_n) ) { 334 right.set(left_n, INVALID); 335 335 } else { 336 level_list[lev]=0; 337 336 level_list[lev]=INVALID; 338 337 } 339 338 } … … 341 340 342 341 //gapping starts 343 if ( level_list[lev]==0) {342 if ( !G.valid(level_list[lev]) ) { 344 343 345 344 for (int i=lev; i!=k ; ) { 346 Node Itv=level_list[++i];347 while ( v != 0) {345 Node v=level_list[++i]; 346 while ( G.valid(v) ) { 348 347 level.set(v,n); 349 v=right .get(v);348 v=right[v]; 350 349 } 351 level_list[i]= 0;352 if ( !what_heur ) active[i]= 0;350 level_list[i]=INVALID; 351 if ( !what_heur ) active[i]=INVALID; 353 352 } 354 353 … … 366 365 if ( what_heur ) b=newlevel; 367 366 if ( k < newlevel ) ++k; 368 Node Itfirst=level_list[newlevel];369 if ( first != 0) left.set(first,w);367 Node first=level_list[newlevel]; 368 if ( G.valid(first) ) left.set(first,w); 370 369 right.set(w,first); 371 left.set(w, 0);370 left.set(w,INVALID); 372 371 level_list[newlevel]=w; 373 372 } … … 399 398 400 399 401 value = excess .get(t);400 value = excess[t]; 402 401 /*Max flow value.*/ 403 402 … … 412 411 */ 413 412 414 T maxFlow() {413 T flowValue() { 415 414 return value; 416 415 } 417 418 419 420 /*421 For the maximum flow x found by the algorithm,422 it returns the flow value on edge e, i.e. x(e).423 */424 425 T flowOnEdge(EdgeIt e) {426 return flow.get(e);427 }428 429 416 430 417 … … 436 423 437 424 void Flow(FlowMap& _flow ) { 438 for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v) 439 _flow.set(v,flow.get(v)); 440 } 425 NodeIt v; 426 for(G.first(v) ; G.valid(v); G.next(v)) 427 _flow.set(v,flow[v]); 428 } 441 429 442 430 … … 449 437 void minMinCut(_CutMap& M) { 450 438 451 std::queue<Node It> queue;439 std::queue<Node> queue; 452 440 453 441 M.set(s,true); … … 455 443 456 444 while (!queue.empty()) { 457 Node Itw=queue.front();445 Node w=queue.front(); 458 446 queue.pop(); 459 447 460 for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) { 461 NodeIt v=G.head(e); 462 if (!M.get(v) && flow.get(e) < capacity.get(e) ) { 448 OutEdgeIt e; 449 for(G.first(e,w) ; G.valid(e); G.next(e)) { 450 Node v=G.head(e); 451 if (!M[v] && flow[e] < capacity[e] ) { 463 452 queue.push(v); 464 453 M.set(v, true); … … 466 455 } 467 456 468 for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) { 469 NodeIt v=G.tail(e); 470 if (!M.get(v) && flow.get(e) > 0 ) { 457 InEdgeIt f; 458 for(G.first(f,w) ; G.valid(f); G.next(f)) { 459 Node v=G.tail(f); 460 if (!M[v] && flow[f] > 0 ) { 471 461 queue.push(v); 472 462 M.set(v, true); … … 486 476 void maxMinCut(_CutMap& M) { 487 477 488 std::queue<Node It> queue;478 std::queue<Node> queue; 489 479 490 480 M.set(t,true); … … 492 482 493 483 while (!queue.empty()) { 494 Node Itw=queue.front();484 Node w=queue.front(); 495 485 queue.pop(); 496 486 497 for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) { 498 NodeIt v=G.tail(e); 499 if (!M.get(v) && flow.get(e) < capacity.get(e) ) { 487 488 InEdgeIt e; 489 for(G.first(e,w) ; G.valid(e); G.next(e)) { 490 Node v=G.tail(e); 491 if (!M[v] && flow[e] < capacity[e] ) { 500 492 queue.push(v); 501 493 M.set(v, true); 502 494 } 503 495 } 504 505 for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) { 506 NodeIt v=G.head(e); 507 if (!M.get(v) && flow.get(e) > 0 ) { 496 497 OutEdgeIt f; 498 for(G.first(f,w) ; G.valid(f); G.next(f)) { 499 Node v=G.head(f); 500 if (!M[v] && flow[f] > 0 ) { 508 501 queue.push(v); 509 502 M.set(v, true); … … 512 505 } 513 506 514 for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v) { 515 M.set(v, !M.get(v)); 507 NodeIt v; 508 for(G.first(v) ; G.valid(v); G.next(v)) { 509 M.set(v, !M[v]); 516 510 } 517 511
Note: See TracChangeset
for help on using the changeset viewer.