7 list 'level_list' on the nodes on level i implemented by hand
8 stack 'active' on the active nodes on level i
9 runs heuristic 'highest label' for H1*n relabels
10 runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label'
12 Parameters H0 and H1 are initialized to 20 and 1.
16 Preflow(Graph, Node, Node, CapMap, FlowMap, bool) : bool must be false if
17 FlowMap is not constant zero, and should be true if it is
23 T flowValue() : returns the value of a maximum flow
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?
28 void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
29 maximum min cut. M should be a map of bools initialized to false.
31 void minCut(CutMap& M) : sets M to the characteristic vector of
32 a min cut. M should be a map of bools initialized to false.
36 #ifndef HUGO_PREFLOW_H
37 #define HUGO_PREFLOW_H
48 template <typename Graph, typename T,
49 typename CapMap=typename Graph::template EdgeMap<T>,
50 typename FlowMap=typename Graph::template EdgeMap<T> >
53 typedef typename Graph::Node Node;
54 typedef typename Graph::NodeIt NodeIt;
55 typedef typename Graph::OutEdgeIt OutEdgeIt;
56 typedef typename Graph::InEdgeIt InEdgeIt;
58 typedef typename std::vector<std::stack<Node> > VecStack;
59 typedef typename Graph::template NodeMap<Node> NNMap;
60 typedef typename std::vector<Node> VecNode;
65 const CapMap* capacity;
67 int n; //the number of nodes of G
68 typename Graph::template NodeMap<int> level;
69 typename Graph::template NodeMap<T> excess;
80 Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
82 G(_G), s(_s), t(_t), capacity(&_capacity),
83 flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {}
89 void preflow( flowEnum fe ) {
94 void preflowPhase0( flowEnum fe ) {
96 int heur0=(int)(H0*n); //time while running 'bound decrease'
97 int heur1=(int)(H1*n); //time while running 'highest label'
98 int heur=heur1; //starting time interval (#of relabels)
102 //It is 0 in case 'bound decrease' and 1 in case 'highest label'
105 //Needed for 'bound decrease', true means no active nodes are above bound b.
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
112 NNMap left(G,INVALID);
113 NNMap right(G,INVALID);
114 VecNode level_list(n,INVALID);
115 //List of the nodes in level i<n, set to n.
118 for(G.first(v); G.valid(v); G.next(v)) level.set(v,n);
119 //setting each node to level n
124 //counting the excess
126 for(G.first(v); G.valid(v); G.next(v)) {
130 for(G.first(e,v); G.valid(e); G.next(e)) exc+=(*flow)[e];
132 for(G.first(f,v); G.valid(f); G.next(f)) exc-=(*flow)[f];
136 //putting the active nodes into the stack
138 if ( exc > 0 && lev < n && v != t ) active[lev].push(v);
144 //Counting the excess of t
148 for(G.first(e,t); G.valid(e); G.next(e)) exc+=(*flow)[e];
150 for(G.first(f,t); G.valid(f); G.next(f)) exc-=(*flow)[f];
158 // ZERO_FLOW ize kell
162 preflowPreproc( fe, active, level_list, left, right );
163 //End of preprocessing
166 //Push/relabel on the highest level active nodes.
169 if ( !what_heur && !end && k > 0 ) {
175 if ( active[b].empty() ) --b;
178 Node w=active[b].top();
180 int newlevel=push(w,active);
181 if ( excess[w] > 0 ) relabel(w, newlevel, active, level_list,
182 left, right, b, k, what_heur);
185 if ( numrelabel >= heur ) {
202 void preflowPhase1() {
204 int k=n-2; //bound on the highest level under n containing a node
205 int b=k; //bound on the highest level under n of an active node
209 std::queue<Node> bfs_queue;
212 while (!bfs_queue.empty()) {
214 Node v=bfs_queue.front();
219 for(G.first(e,v); G.valid(e); G.next(e)) {
220 if ( (*capacity)[e] == (*flow)[e] ) continue;
222 if ( level[u] >= n ) {
225 if ( excess[u] > 0 ) active[l].push(u);
230 for(G.first(f,v); G.valid(f); G.next(f)) {
231 if ( 0 == (*flow)[f] ) continue;
233 if ( level[u] >= n ) {
236 if ( excess[u] > 0 ) active[l].push(u);
246 if ( active[b].empty() ) --b;
248 Node w=active[b].top();
250 int newlevel=push(w,active);
253 if ( excess[w] > 0 ) {
254 level.set(w,++newlevel);
255 active[newlevel].push(w);
258 } // if stack[b] is nonempty
263 //Returns the maximum value of a flow.
268 //should be used only between preflowPhase0 and preflowPhase1
269 template<typename _CutMap>
270 void actMinCut(_CutMap& M) {
272 for(G.first(v); G.valid(v); G.next(v))
273 if ( level[v] < n ) M.set(v,false);
280 Returns the minimum min cut, by a bfs from s in the residual graph.
282 template<typename _CutMap>
283 void minMinCut(_CutMap& M) {
285 std::queue<Node> queue;
290 while (!queue.empty()) {
291 Node w=queue.front();
295 for(G.first(e,w) ; G.valid(e); G.next(e)) {
297 if (!M[v] && (*flow)[e] < (*capacity)[e] ) {
304 for(G.first(f,w) ; G.valid(f); G.next(f)) {
306 if (!M[v] && (*flow)[f] > 0 ) {
317 Returns the maximum min cut, by a reverse bfs
318 from t in the residual graph.
321 template<typename _CutMap>
322 void maxMinCut(_CutMap& M) {
325 for(G.first(v) ; G.valid(v); G.next(v)) {
329 std::queue<Node> queue;
334 while (!queue.empty()) {
335 Node w=queue.front();
340 for(G.first(e,w) ; G.valid(e); G.next(e)) {
342 if (M[v] && (*flow)[e] < (*capacity)[e] ) {
349 for(G.first(f,w) ; G.valid(f); G.next(f)) {
351 if (M[v] && (*flow)[f] > 0 ) {
360 template<typename CutMap>
361 void minCut(CutMap& M) {
366 void resetTarget (const Node _t) {t=_t;}
368 void resetSource (const Node _s) {s=_s;}
370 void resetCap (const CapMap& _cap) {
374 void resetFlow (FlowMap& _flow) {
381 int push(const Node w, VecStack& active) {
385 int newlevel=n; //bound on the next level of w
388 for(G.first(e,w); G.valid(e); G.next(e)) {
390 if ( (*flow)[e] == (*capacity)[e] ) continue;
393 if( lev > level[v] ) { //Push is allowed now
395 if ( excess[v]==0 && v!=t && v!=s ) {
397 active[lev_v].push(v);
400 T cap=(*capacity)[e];
404 if ( remcap >= exc ) { //A nonsaturating push.
406 flow->set(e, flo+exc);
407 excess.set(v, excess[v]+exc);
411 } else { //A saturating push.
413 excess.set(v, excess[v]+remcap);
416 } else if ( newlevel > level[v] ) newlevel = level[v];
421 for(G.first(e,w); G.valid(e); G.next(e)) {
423 if( (*flow)[e] == 0 ) continue;
426 if( lev > level[v] ) { //Push is allowed now
428 if ( excess[v]==0 && v!=t && v!=s ) {
430 active[lev_v].push(v);
435 if ( flo >= exc ) { //A nonsaturating push.
437 flow->set(e, flo-exc);
438 excess.set(v, excess[v]+exc);
441 } else { //A saturating push.
443 excess.set(v, excess[v]+flo);
447 } else if ( newlevel > level[v] ) newlevel = level[v];
450 } // if w still has excess after the out edge for cycle
458 void preflowPreproc ( flowEnum fe, VecStack& active,
459 VecNode& level_list, NNMap& left, NNMap& right ) {
461 std::queue<Node> bfs_queue;
466 //Reverse_bfs from t, to find the starting level.
470 while (!bfs_queue.empty()) {
472 Node v=bfs_queue.front();
477 for(G.first(e,v); G.valid(e); G.next(e)) {
479 if ( level[w] == n && w != s ) {
481 Node first=level_list[l];
482 if ( G.valid(first) ) left.set(first,w);
492 for(G.first(e,s); G.valid(e); G.next(e))
495 if ( c == 0 ) continue;
497 if ( level[w] < n ) {
498 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
500 excess.set(w, excess[w]+c);
509 //Reverse_bfs from t in the residual graph,
510 //to find the starting level.
514 while (!bfs_queue.empty()) {
516 Node v=bfs_queue.front();
521 for(G.first(e,v); G.valid(e); G.next(e)) {
522 if ( (*capacity)[e] == (*flow)[e] ) continue;
524 if ( level[w] == n && w != s ) {
526 Node first=level_list[l];
527 if ( G.valid(first) ) left.set(first,w);
535 for(G.first(f,v); G.valid(f); G.next(f)) {
536 if ( 0 == (*flow)[f] ) continue;
538 if ( level[w] == n && w != s ) {
540 Node first=level_list[l];
541 if ( G.valid(first) ) left.set(first,w);
552 for(G.first(e,s); G.valid(e); G.next(e))
554 T rem=(*capacity)[e]-(*flow)[e];
555 if ( rem == 0 ) continue;
557 if ( level[w] < n ) {
558 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
559 flow->set(e, (*capacity)[e]);
560 excess.set(w, excess[w]+rem);
565 for(G.first(f,s); G.valid(f); G.next(f))
567 if ( (*flow)[f] == 0 ) continue;
569 if ( level[w] < n ) {
570 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
571 excess.set(w, excess[w]+(*flow)[f]);
582 void relabel( const Node w, int newlevel, VecStack& active,
583 VecNode& level_list, NNMap& left,
584 NNMap& right, int& b, int& k, const bool what_heur ) {
588 Node right_n=right[w];
592 if ( G.valid(right_n) ) {
593 if ( G.valid(left_n) ) {
594 right.set(left_n, right_n);
595 left.set(right_n, left_n);
597 level_list[lev]=right_n;
598 left.set(right_n, INVALID);
601 if ( G.valid(left_n) ) {
602 right.set(left_n, INVALID);
604 level_list[lev]=INVALID;
609 if ( !G.valid(level_list[lev]) ) {
612 for (int i=lev; i!=k ; ) {
613 Node v=level_list[++i];
614 while ( G.valid(v) ) {
618 level_list[i]=INVALID;
620 while ( !active[i].empty() ) {
621 active[i].pop(); //FIXME: ezt szebben kene
633 if ( newlevel == n ) level.set(w,n);
635 level.set(w,++newlevel);
636 active[newlevel].push(w);
637 if ( what_heur ) b=newlevel;
638 if ( k < newlevel ) ++k; //now k=newlevel
639 Node first=level_list[newlevel];
640 if ( G.valid(first) ) left.set(first,w);
643 level_list[newlevel]=w;
654 #endif //HUGO_PREFLOW_H