equal
deleted
inserted
replaced
18 |
18 |
19 Members: |
19 Members: |
20 |
20 |
21 void run() |
21 void run() |
22 |
22 |
23 T flowValue() : returns the value of a maximum flow |
23 Num flowValue() : returns the value of a maximum flow |
24 |
24 |
25 void minMinCut(CutMap& M) : sets M to the characteristic vector of the |
25 void minMinCut(CutMap& M) : sets M to the characteristic vector of the |
26 minimum min cut. M should be a map of bools initialized to false. ??Is it OK? |
26 minimum min cut. M should be a map of bools initialized to false. ??Is it OK? |
27 |
27 |
28 void maxMinCut(CutMap& M) : sets M to the characteristic vector of the |
28 void maxMinCut(CutMap& M) : sets M to the characteristic vector of the |
43 #include <queue> |
43 #include <queue> |
44 #include <stack> |
44 #include <stack> |
45 |
45 |
46 namespace hugo { |
46 namespace hugo { |
47 |
47 |
48 template <typename Graph, typename T, |
48 template <typename Graph, typename Num, |
49 typename CapMap=typename Graph::template EdgeMap<T>, |
49 typename CapMap=typename Graph::template EdgeMap<Num>, |
50 typename FlowMap=typename Graph::template EdgeMap<T> > |
50 typename FlowMap=typename Graph::template EdgeMap<Num> > |
51 class Preflow { |
51 class Preflow { |
52 |
52 |
53 typedef typename Graph::Node Node; |
53 typedef typename Graph::Node Node; |
54 typedef typename Graph::NodeIt NodeIt; |
54 typedef typename Graph::NodeIt NodeIt; |
55 typedef typename Graph::OutEdgeIt OutEdgeIt; |
55 typedef typename Graph::OutEdgeIt OutEdgeIt; |
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 |
68 typename Graph::template NodeMap<int> level; |
68 typename Graph::template NodeMap<int> level; |
69 typename Graph::template NodeMap<T> excess; |
69 typename Graph::template NodeMap<Num> excess; |
70 |
70 |
71 |
71 |
72 public: |
72 public: |
73 |
73 |
74 enum flowEnum{ |
74 enum flowEnum{ |
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 Num 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]; |
140 break; |
140 break; |
141 } |
141 } |
142 case GEN_FLOW: |
142 case GEN_FLOW: |
143 { |
143 { |
144 //Counting the excess of t |
144 //Counting the excess of t |
145 T exc=0; |
145 Num exc=0; |
146 |
146 |
147 InEdgeIt e; |
147 InEdgeIt e; |
148 for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e]; |
148 for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e]; |
149 OutEdgeIt f; |
149 OutEdgeIt f; |
150 for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f]; |
150 for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f]; |
259 } // while(true) |
259 } // while(true) |
260 } |
260 } |
261 |
261 |
262 |
262 |
263 //Returns the maximum value of a flow. |
263 //Returns the maximum value of a flow. |
264 T flowValue() { |
264 Num flowValue() { |
265 return excess[t]; |
265 return excess[t]; |
266 } |
266 } |
267 |
267 |
268 //should be used only between preflowPhase0 and preflowPhase1 |
268 //should be used only between preflowPhase0 and preflowPhase1 |
269 template<typename _CutMap> |
269 template<typename _CutMap> |
363 template<typename CutMap> |
363 template<typename CutMap> |
364 void minCut(CutMap& M) { |
364 void minCut(CutMap& M) { |
365 minMinCut(M); |
365 minMinCut(M); |
366 } |
366 } |
367 |
367 |
|
368 void resetTarget(Node _t) {t=_t;} |
|
369 void resetSource(Node _s) {s=_s;} |
|
370 |
|
371 void resetCap(const CapMap& _cap) { |
|
372 capacity=&_cap; |
|
373 } |
368 |
374 |
369 void resetTarget (const Node _t) {t=_t;} |
375 void resetFlow(FlowMap& _flow) { |
370 |
|
371 void resetSource (const Node _s) {s=_s;} |
|
372 |
|
373 void resetCap (const CapMap& _cap) { |
|
374 capacity=&_cap; |
|
375 } |
|
376 |
|
377 void resetFlow (FlowMap& _flow) { |
|
378 flow=&_flow; |
376 flow=&_flow; |
379 } |
377 } |
380 |
378 |
381 |
379 |
382 private: |
380 private: |
383 |
381 |
384 int push(const Node w, VecStack& active) { |
382 int push(const Node w, VecStack& active) { |
385 |
383 |
386 int lev=level[w]; |
384 int lev=level[w]; |
387 T exc=excess[w]; |
385 Num exc=excess[w]; |
388 int newlevel=n; //bound on the next level of w |
386 int newlevel=n; //bound on the next level of w |
389 |
387 |
390 OutEdgeIt e; |
388 OutEdgeIt e; |
391 for(g->first(e,w); g->valid(e); g->next(e)) { |
389 for(g->first(e,w); g->valid(e); g->next(e)) { |
392 |
390 |
398 if ( excess[v]==0 && v!=t && v!=s ) { |
396 if ( excess[v]==0 && v!=t && v!=s ) { |
399 int lev_v=level[v]; |
397 int lev_v=level[v]; |
400 active[lev_v].push(v); |
398 active[lev_v].push(v); |
401 } |
399 } |
402 |
400 |
403 T cap=(*capacity)[e]; |
401 Num cap=(*capacity)[e]; |
404 T flo=(*flow)[e]; |
402 Num flo=(*flow)[e]; |
405 T remcap=cap-flo; |
403 Num remcap=cap-flo; |
406 |
404 |
407 if ( remcap >= exc ) { //A nonsaturating push. |
405 if ( remcap >= exc ) { //A nonsaturating push. |
408 |
406 |
409 flow->set(e, flo+exc); |
407 flow->set(e, flo+exc); |
410 excess.set(v, excess[v]+exc); |
408 excess.set(v, excess[v]+exc); |
431 if ( excess[v]==0 && v!=t && v!=s ) { |
429 if ( excess[v]==0 && v!=t && v!=s ) { |
432 int lev_v=level[v]; |
430 int lev_v=level[v]; |
433 active[lev_v].push(v); |
431 active[lev_v].push(v); |
434 } |
432 } |
435 |
433 |
436 T flo=(*flow)[e]; |
434 Num flo=(*flow)[e]; |
437 |
435 |
438 if ( flo >= exc ) { //A nonsaturating push. |
436 if ( flo >= exc ) { //A nonsaturating push. |
439 |
437 |
440 flow->set(e, flo-exc); |
438 flow->set(e, flo-exc); |
441 excess.set(v, excess[v]+exc); |
439 excess.set(v, excess[v]+exc); |
492 |
490 |
493 //the starting flow |
491 //the starting flow |
494 OutEdgeIt e; |
492 OutEdgeIt e; |
495 for(g->first(e,s); g->valid(e); g->next(e)) |
493 for(g->first(e,s); g->valid(e); g->next(e)) |
496 { |
494 { |
497 T c=(*capacity)[e]; |
495 Num c=(*capacity)[e]; |
498 if ( c == 0 ) continue; |
496 if ( c == 0 ) continue; |
499 Node w=g->head(e); |
497 Node w=g->head(e); |
500 if ( level[w] < n ) { |
498 if ( level[w] < n ) { |
501 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); |
499 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); |
502 flow->set(e, c); |
500 flow->set(e, c); |
552 |
550 |
553 //the starting flow |
551 //the starting flow |
554 OutEdgeIt e; |
552 OutEdgeIt e; |
555 for(g->first(e,s); g->valid(e); g->next(e)) |
553 for(g->first(e,s); g->valid(e); g->next(e)) |
556 { |
554 { |
557 T rem=(*capacity)[e]-(*flow)[e]; |
555 Num rem=(*capacity)[e]-(*flow)[e]; |
558 if ( rem == 0 ) continue; |
556 if ( rem == 0 ) continue; |
559 Node w=g->head(e); |
557 Node w=g->head(e); |
560 if ( level[w] < n ) { |
558 if ( level[w] < n ) { |
561 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); |
559 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); |
562 flow->set(e, (*capacity)[e]); |
560 flow->set(e, (*capacity)[e]); |
584 |
582 |
585 void relabel( const Node w, int newlevel, VecStack& active, |
583 void relabel( const Node w, int newlevel, VecStack& active, |
586 VecNode& level_list, NNMap& left, |
584 VecNode& level_list, NNMap& left, |
587 NNMap& right, int& b, int& k, const bool what_heur ) { |
585 NNMap& right, int& b, int& k, const bool what_heur ) { |
588 |
586 |
589 T lev=level[w]; |
587 Num lev=level[w]; |
590 |
588 |
591 Node right_n=right[w]; |
589 Node right_n=right[w]; |
592 Node left_n=left[w]; |
590 Node left_n=left[w]; |
593 |
591 |
594 //unlacing starts |
592 //unlacing starts |