57 |
57 |
58 typedef typename std::vector<std::stack<Node> > VecStack; |
58 typedef typename std::vector<std::stack<Node> > VecStack; |
59 typedef typename Graph::template NodeMap<Node> NNMap; |
59 typedef typename Graph::template NodeMap<Node> NNMap; |
60 typedef typename std::vector<Node> VecNode; |
60 typedef typename std::vector<Node> VecNode; |
61 |
61 |
62 const Graph& G; |
62 const Graph* g; |
63 Node s; |
63 Node s; |
64 Node t; |
64 Node t; |
65 const CapMap* capacity; |
65 const CapMap* capacity; |
66 FlowMap* flow; |
66 FlowMap* flow; |
67 int n; //the number of nodes of G |
67 int n; //the number of nodes of G |
77 PREFLOW=2 |
77 PREFLOW=2 |
78 }; |
78 }; |
79 |
79 |
80 Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, |
80 Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, |
81 FlowMap& _flow) : |
81 FlowMap& _flow) : |
82 G(_G), s(_s), t(_t), capacity(&_capacity), |
82 g(&_G), s(_s), t(_t), capacity(&_capacity), |
83 flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {} |
83 flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {} |
84 |
84 |
85 void run() { |
85 void run() { |
86 preflow( ZERO_FLOW ); |
86 preflow( ZERO_FLOW ); |
87 } |
87 } |
107 int k=n-2; //bound on the highest level under n containing a node |
107 int k=n-2; //bound on the highest level under n containing a node |
108 int b=k; //bound on the highest level under n of an active node |
108 int b=k; //bound on the highest level under n of an active node |
109 |
109 |
110 VecStack active(n); |
110 VecStack active(n); |
111 |
111 |
112 NNMap left(G,INVALID); |
112 NNMap left(*g, INVALID); |
113 NNMap right(G,INVALID); |
113 NNMap right(*g, INVALID); |
114 VecNode level_list(n,INVALID); |
114 VecNode level_list(n,INVALID); |
115 //List of the nodes in level i<n, set to n. |
115 //List of the nodes in level i<n, set to n. |
116 |
116 |
117 NodeIt v; |
117 NodeIt v; |
118 for(G.first(v); G.valid(v); G.next(v)) level.set(v,n); |
118 for(g->first(v); g->valid(v); g->next(v)) level.set(v,n); |
119 //setting each node to level n |
119 //setting each node to level n |
120 |
120 |
121 switch ( fe ) { |
121 switch ( fe ) { |
122 case PREFLOW: |
122 case PREFLOW: |
123 { |
123 { |
124 //counting the excess |
124 //counting the excess |
125 NodeIt v; |
125 NodeIt v; |
126 for(G.first(v); G.valid(v); G.next(v)) { |
126 for(g->first(v); g->valid(v); g->next(v)) { |
127 T exc=0; |
127 T exc=0; |
128 |
128 |
129 InEdgeIt e; |
129 InEdgeIt e; |
130 for(G.first(e,v); G.valid(e); G.next(e)) exc+=(*flow)[e]; |
130 for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e]; |
131 OutEdgeIt f; |
131 OutEdgeIt f; |
132 for(G.first(f,v); G.valid(f); G.next(f)) exc-=(*flow)[f]; |
132 for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f]; |
133 |
133 |
134 excess.set(v,exc); |
134 excess.set(v,exc); |
135 |
135 |
136 //putting the active nodes into the stack |
136 //putting the active nodes into the stack |
137 int lev=level[v]; |
137 int lev=level[v]; |
214 Node v=bfs_queue.front(); |
214 Node v=bfs_queue.front(); |
215 bfs_queue.pop(); |
215 bfs_queue.pop(); |
216 int l=level[v]+1; |
216 int l=level[v]+1; |
217 |
217 |
218 InEdgeIt e; |
218 InEdgeIt e; |
219 for(G.first(e,v); G.valid(e); G.next(e)) { |
219 for(g->first(e,v); g->valid(e); g->next(e)) { |
220 if ( (*capacity)[e] == (*flow)[e] ) continue; |
220 if ( (*capacity)[e] == (*flow)[e] ) continue; |
221 Node u=G.tail(e); |
221 Node u=g->tail(e); |
222 if ( level[u] >= n ) { |
222 if ( level[u] >= n ) { |
223 bfs_queue.push(u); |
223 bfs_queue.push(u); |
224 level.set(u, l); |
224 level.set(u, l); |
225 if ( excess[u] > 0 ) active[l].push(u); |
225 if ( excess[u] > 0 ) active[l].push(u); |
226 } |
226 } |
227 } |
227 } |
228 |
228 |
229 OutEdgeIt f; |
229 OutEdgeIt f; |
230 for(G.first(f,v); G.valid(f); G.next(f)) { |
230 for(g->first(f,v); g->valid(f); g->next(f)) { |
231 if ( 0 == (*flow)[f] ) continue; |
231 if ( 0 == (*flow)[f] ) continue; |
232 Node u=G.head(f); |
232 Node u=g->head(f); |
233 if ( level[u] >= n ) { |
233 if ( level[u] >= n ) { |
234 bfs_queue.push(u); |
234 bfs_queue.push(u); |
235 level.set(u, l); |
235 level.set(u, l); |
236 if ( excess[u] > 0 ) active[l].push(u); |
236 if ( excess[u] > 0 ) active[l].push(u); |
237 } |
237 } |
290 while (!queue.empty()) { |
293 while (!queue.empty()) { |
291 Node w=queue.front(); |
294 Node w=queue.front(); |
292 queue.pop(); |
295 queue.pop(); |
293 |
296 |
294 OutEdgeIt e; |
297 OutEdgeIt e; |
295 for(G.first(e,w) ; G.valid(e); G.next(e)) { |
298 for(g->first(e,w) ; g->valid(e); g->next(e)) { |
296 Node v=G.head(e); |
299 Node v=g->head(e); |
297 if (!M[v] && (*flow)[e] < (*capacity)[e] ) { |
300 if (!M[v] && (*flow)[e] < (*capacity)[e] ) { |
298 queue.push(v); |
301 queue.push(v); |
299 M.set(v, true); |
302 M.set(v, true); |
300 } |
303 } |
301 } |
304 } |
302 |
305 |
303 InEdgeIt f; |
306 InEdgeIt f; |
304 for(G.first(f,w) ; G.valid(f); G.next(f)) { |
307 for(g->first(f,w) ; g->valid(f); g->next(f)) { |
305 Node v=G.tail(f); |
308 Node v=g->tail(f); |
306 if (!M[v] && (*flow)[f] > 0 ) { |
309 if (!M[v] && (*flow)[f] > 0 ) { |
307 queue.push(v); |
310 queue.push(v); |
308 M.set(v, true); |
311 M.set(v, true); |
309 } |
312 } |
310 } |
313 } |
335 Node w=queue.front(); |
338 Node w=queue.front(); |
336 queue.pop(); |
339 queue.pop(); |
337 |
340 |
338 |
341 |
339 InEdgeIt e; |
342 InEdgeIt e; |
340 for(G.first(e,w) ; G.valid(e); G.next(e)) { |
343 for(g->first(e,w) ; g->valid(e); g->next(e)) { |
341 Node v=G.tail(e); |
344 Node v=g->tail(e); |
342 if (M[v] && (*flow)[e] < (*capacity)[e] ) { |
345 if (M[v] && (*flow)[e] < (*capacity)[e] ) { |
343 queue.push(v); |
346 queue.push(v); |
344 M.set(v, false); |
347 M.set(v, false); |
345 } |
348 } |
346 } |
349 } |
347 |
350 |
348 OutEdgeIt f; |
351 OutEdgeIt f; |
349 for(G.first(f,w) ; G.valid(f); G.next(f)) { |
352 for(g->first(f,w) ; g->valid(f); g->next(f)) { |
350 Node v=G.head(f); |
353 Node v=g->head(f); |
351 if (M[v] && (*flow)[f] > 0 ) { |
354 if (M[v] && (*flow)[f] > 0 ) { |
352 queue.push(v); |
355 queue.push(v); |
353 M.set(v, false); |
356 M.set(v, false); |
354 } |
357 } |
355 } |
358 } |
383 int lev=level[w]; |
386 int lev=level[w]; |
384 T exc=excess[w]; |
387 T exc=excess[w]; |
385 int newlevel=n; //bound on the next level of w |
388 int newlevel=n; //bound on the next level of w |
386 |
389 |
387 OutEdgeIt e; |
390 OutEdgeIt e; |
388 for(G.first(e,w); G.valid(e); G.next(e)) { |
391 for(g->first(e,w); g->valid(e); g->next(e)) { |
389 |
392 |
390 if ( (*flow)[e] == (*capacity)[e] ) continue; |
393 if ( (*flow)[e] == (*capacity)[e] ) continue; |
391 Node v=G.head(e); |
394 Node v=g->head(e); |
392 |
395 |
393 if( lev > level[v] ) { //Push is allowed now |
396 if( lev > level[v] ) { //Push is allowed now |
394 |
397 |
395 if ( excess[v]==0 && v!=t && v!=s ) { |
398 if ( excess[v]==0 && v!=t && v!=s ) { |
396 int lev_v=level[v]; |
399 int lev_v=level[v]; |
416 } else if ( newlevel > level[v] ) newlevel = level[v]; |
419 } else if ( newlevel > level[v] ) newlevel = level[v]; |
417 } //for out edges wv |
420 } //for out edges wv |
418 |
421 |
419 if ( exc > 0 ) { |
422 if ( exc > 0 ) { |
420 InEdgeIt e; |
423 InEdgeIt e; |
421 for(G.first(e,w); G.valid(e); G.next(e)) { |
424 for(g->first(e,w); g->valid(e); g->next(e)) { |
422 |
425 |
423 if( (*flow)[e] == 0 ) continue; |
426 if( (*flow)[e] == 0 ) continue; |
424 Node v=G.tail(e); |
427 Node v=g->tail(e); |
425 |
428 |
426 if( lev > level[v] ) { //Push is allowed now |
429 if( lev > level[v] ) { //Push is allowed now |
427 |
430 |
428 if ( excess[v]==0 && v!=t && v!=s ) { |
431 if ( excess[v]==0 && v!=t && v!=s ) { |
429 int lev_v=level[v]; |
432 int lev_v=level[v]; |
472 Node v=bfs_queue.front(); |
475 Node v=bfs_queue.front(); |
473 bfs_queue.pop(); |
476 bfs_queue.pop(); |
474 int l=level[v]+1; |
477 int l=level[v]+1; |
475 |
478 |
476 InEdgeIt e; |
479 InEdgeIt e; |
477 for(G.first(e,v); G.valid(e); G.next(e)) { |
480 for(g->first(e,v); g->valid(e); g->next(e)) { |
478 Node w=G.tail(e); |
481 Node w=g->tail(e); |
479 if ( level[w] == n && w != s ) { |
482 if ( level[w] == n && w != s ) { |
480 bfs_queue.push(w); |
483 bfs_queue.push(w); |
481 Node first=level_list[l]; |
484 Node first=level_list[l]; |
482 if ( G.valid(first) ) left.set(first,w); |
485 if ( g->valid(first) ) left.set(first,w); |
483 right.set(w,first); |
486 right.set(w,first); |
484 level_list[l]=w; |
487 level_list[l]=w; |
485 level.set(w, l); |
488 level.set(w, l); |
486 } |
489 } |
487 } |
490 } |
488 } |
491 } |
489 |
492 |
490 //the starting flow |
493 //the starting flow |
491 OutEdgeIt e; |
494 OutEdgeIt e; |
492 for(G.first(e,s); G.valid(e); G.next(e)) |
495 for(g->first(e,s); g->valid(e); g->next(e)) |
493 { |
496 { |
494 T c=(*capacity)[e]; |
497 T c=(*capacity)[e]; |
495 if ( c == 0 ) continue; |
498 if ( c == 0 ) continue; |
496 Node w=G.head(e); |
499 Node w=g->head(e); |
497 if ( level[w] < n ) { |
500 if ( level[w] < n ) { |
498 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); |
501 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); |
499 flow->set(e, c); |
502 flow->set(e, c); |
500 excess.set(w, excess[w]+c); |
503 excess.set(w, excess[w]+c); |
501 } |
504 } |
516 Node v=bfs_queue.front(); |
519 Node v=bfs_queue.front(); |
517 bfs_queue.pop(); |
520 bfs_queue.pop(); |
518 int l=level[v]+1; |
521 int l=level[v]+1; |
519 |
522 |
520 InEdgeIt e; |
523 InEdgeIt e; |
521 for(G.first(e,v); G.valid(e); G.next(e)) { |
524 for(g->first(e,v); g->valid(e); g->next(e)) { |
522 if ( (*capacity)[e] == (*flow)[e] ) continue; |
525 if ( (*capacity)[e] == (*flow)[e] ) continue; |
523 Node w=G.tail(e); |
526 Node w=g->tail(e); |
524 if ( level[w] == n && w != s ) { |
527 if ( level[w] == n && w != s ) { |
525 bfs_queue.push(w); |
528 bfs_queue.push(w); |
526 Node first=level_list[l]; |
529 Node first=level_list[l]; |
527 if ( G.valid(first) ) left.set(first,w); |
530 if ( g->valid(first) ) left.set(first,w); |
528 right.set(w,first); |
531 right.set(w,first); |
529 level_list[l]=w; |
532 level_list[l]=w; |
530 level.set(w, l); |
533 level.set(w, l); |
531 } |
534 } |
532 } |
535 } |
533 |
536 |
534 OutEdgeIt f; |
537 OutEdgeIt f; |
535 for(G.first(f,v); G.valid(f); G.next(f)) { |
538 for(g->first(f,v); g->valid(f); g->next(f)) { |
536 if ( 0 == (*flow)[f] ) continue; |
539 if ( 0 == (*flow)[f] ) continue; |
537 Node w=G.head(f); |
540 Node w=g->head(f); |
538 if ( level[w] == n && w != s ) { |
541 if ( level[w] == n && w != s ) { |
539 bfs_queue.push(w); |
542 bfs_queue.push(w); |
540 Node first=level_list[l]; |
543 Node first=level_list[l]; |
541 if ( G.valid(first) ) left.set(first,w); |
544 if ( g->valid(first) ) left.set(first,w); |
542 right.set(w,first); |
545 right.set(w,first); |
543 level_list[l]=w; |
546 level_list[l]=w; |
544 level.set(w, l); |
547 level.set(w, l); |
545 } |
548 } |
546 } |
549 } |
547 } |
550 } |
548 |
551 |
549 |
552 |
550 //the starting flow |
553 //the starting flow |
551 OutEdgeIt e; |
554 OutEdgeIt e; |
552 for(G.first(e,s); G.valid(e); G.next(e)) |
555 for(g->first(e,s); g->valid(e); g->next(e)) |
553 { |
556 { |
554 T rem=(*capacity)[e]-(*flow)[e]; |
557 T rem=(*capacity)[e]-(*flow)[e]; |
555 if ( rem == 0 ) continue; |
558 if ( rem == 0 ) continue; |
556 Node w=G.head(e); |
559 Node w=g->head(e); |
557 if ( level[w] < n ) { |
560 if ( level[w] < n ) { |
558 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); |
561 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); |
559 flow->set(e, (*capacity)[e]); |
562 flow->set(e, (*capacity)[e]); |
560 excess.set(w, excess[w]+rem); |
563 excess.set(w, excess[w]+rem); |
561 } |
564 } |
562 } |
565 } |
563 |
566 |
564 InEdgeIt f; |
567 InEdgeIt f; |
565 for(G.first(f,s); G.valid(f); G.next(f)) |
568 for(g->first(f,s); g->valid(f); g->next(f)) |
566 { |
569 { |
567 if ( (*flow)[f] == 0 ) continue; |
570 if ( (*flow)[f] == 0 ) continue; |
568 Node w=G.tail(f); |
571 Node w=g->tail(f); |
569 if ( level[w] < n ) { |
572 if ( level[w] < n ) { |
570 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); |
573 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); |
571 excess.set(w, excess[w]+(*flow)[f]); |
574 excess.set(w, excess[w]+(*flow)[f]); |
572 flow->set(f, 0); |
575 flow->set(f, 0); |
573 } |
576 } |
587 |
590 |
588 Node right_n=right[w]; |
591 Node right_n=right[w]; |
589 Node left_n=left[w]; |
592 Node left_n=left[w]; |
590 |
593 |
591 //unlacing starts |
594 //unlacing starts |
592 if ( G.valid(right_n) ) { |
595 if ( g->valid(right_n) ) { |
593 if ( G.valid(left_n) ) { |
596 if ( g->valid(left_n) ) { |
594 right.set(left_n, right_n); |
597 right.set(left_n, right_n); |
595 left.set(right_n, left_n); |
598 left.set(right_n, left_n); |
596 } else { |
599 } else { |
597 level_list[lev]=right_n; |
600 level_list[lev]=right_n; |
598 left.set(right_n, INVALID); |
601 left.set(right_n, INVALID); |
599 } |
602 } |
600 } else { |
603 } else { |
601 if ( G.valid(left_n) ) { |
604 if ( g->valid(left_n) ) { |
602 right.set(left_n, INVALID); |
605 right.set(left_n, INVALID); |
603 } else { |
606 } else { |
604 level_list[lev]=INVALID; |
607 level_list[lev]=INVALID; |
605 } |
608 } |
606 } |
609 } |
607 //unlacing ends |
610 //unlacing ends |
608 |
611 |
609 if ( !G.valid(level_list[lev]) ) { |
612 if ( !g->valid(level_list[lev]) ) { |
610 |
613 |
611 //gapping starts |
614 //gapping starts |
612 for (int i=lev; i!=k ; ) { |
615 for (int i=lev; i!=k ; ) { |
613 Node v=level_list[++i]; |
616 Node v=level_list[++i]; |
614 while ( G.valid(v) ) { |
617 while ( g->valid(v) ) { |
615 level.set(v,n); |
618 level.set(v,n); |
616 v=right[v]; |
619 v=right[v]; |
617 } |
620 } |
618 level_list[i]=INVALID; |
621 level_list[i]=INVALID; |
619 if ( !what_heur ) { |
622 if ( !what_heur ) { |
635 level.set(w,++newlevel); |
638 level.set(w,++newlevel); |
636 active[newlevel].push(w); |
639 active[newlevel].push(w); |
637 if ( what_heur ) b=newlevel; |
640 if ( what_heur ) b=newlevel; |
638 if ( k < newlevel ) ++k; //now k=newlevel |
641 if ( k < newlevel ) ++k; //now k=newlevel |
639 Node first=level_list[newlevel]; |
642 Node first=level_list[newlevel]; |
640 if ( G.valid(first) ) left.set(first,w); |
643 if ( g->valid(first) ) left.set(first,w); |
641 right.set(w,first); |
644 right.set(w,first); |
642 left.set(w,INVALID); |
645 left.set(w,INVALID); |
643 level_list[newlevel]=w; |
646 level_list[newlevel]=w; |
644 } |
647 } |
645 } |
648 } |