Testing preprocess.
3 //run gyorsan tudna adni a minmincutot a 2 fazis elejen , ne vegyuk be konstruktorba egy cutmapet?
6 //majd marci megmondja betegyem-e bfs-t meg resgraphot
12 list 'level_list' on the nodes on level i implemented by hand
13 stack 'active' on the active nodes on level i implemented by hand
14 runs heuristic 'highest label' for H1*n relabels
15 runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label'
17 Parameters H0 and H1 are initialized to 20 and 10.
21 Preflow(Graph, Node, Node, CapMap, FlowMap, bool) : bool must be false if
22 FlowMap is not constant zero, and should be true if it is
28 T flowValue() : returns the value of a maximum flow
30 void minMinCut(CutMap& M) : sets M to the characteristic vector of the
31 minimum min cut. M should be a map of bools initialized to false.
33 void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
34 maximum min cut. M should be a map of bools initialized to false.
36 void minCut(CutMap& M) : sets M to the characteristic vector of
37 a min cut. M should be a map of bools initialized to false.
43 #ifndef HUGO_PREFLOW_H
44 #define HUGO_PREFLOW_H
54 template <typename Graph, typename T,
55 typename CapMap=typename Graph::template EdgeMap<T>,
56 typename FlowMap=typename Graph::template EdgeMap<T> >
59 typedef typename Graph::Node Node;
60 typedef typename Graph::Edge Edge;
61 typedef typename Graph::NodeIt NodeIt;
62 typedef typename Graph::OutEdgeIt OutEdgeIt;
63 typedef typename Graph::InEdgeIt InEdgeIt;
68 const CapMap& capacity;
74 Preflow(Graph& _G, Node _s, Node _t, CapMap& _capacity,
75 FlowMap& _flow, bool _constzero ) :
76 G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow), constzero(_constzero) {}
81 value=0; //for the subsequent runs
83 bool phase=0; //phase 0 is the 1st phase, phase 1 is the 2nd
85 int heur0=(int)(H0*n); //time while running 'bound decrease'
86 int heur1=(int)(H1*n); //time while running 'highest label'
87 int heur=heur1; //starting time interval (#of relabels)
90 what_heur is 0 in case 'bound decrease'
91 and 1 in case 'highest label'
95 Needed for 'bound decrease', 'true'
96 means no active nodes are above bound b.
99 int k=n-2; //bound on the highest level under n containing a node
100 int b=k; //bound on the highest level under n of an active node
102 typename Graph::template NodeMap<int> level(G,n);
103 typename Graph::template NodeMap<T> excess(G);
105 std::vector<Node> active(n-1,INVALID);
106 typename Graph::template NodeMap<Node> next(G,INVALID);
107 //Stack of the active nodes in level i < n.
108 //We use it in both phases.
110 typename Graph::template NodeMap<Node> left(G,INVALID);
111 typename Graph::template NodeMap<Node> right(G,INVALID);
112 std::vector<Node> level_list(n,INVALID);
114 List of the nodes in level i<n.
120 /*Reverse_bfs from t, to find the starting level.*/
122 std::queue<Node> bfs_queue;
125 while (!bfs_queue.empty()) {
127 Node v=bfs_queue.front();
132 for(G.first(e,v); G.valid(e); G.next(e)) {
134 if ( level[w] == n && w != s ) {
136 Node first=level_list[l];
137 if ( G.valid(first) ) left.set(first,w);
147 for(G.first(e,s); G.valid(e); G.next(e))
150 if ( c == 0 ) continue;
152 if ( level[w] < n ) {
153 if ( excess[w] == 0 && w!=t ) {
154 next.set(w,active[level[w]]);
158 excess.set(w, excess[w]+c);
166 Reverse_bfs from t in the residual graph,
167 to find the starting level.
170 std::queue<Node> bfs_queue;
173 while (!bfs_queue.empty()) {
175 Node v=bfs_queue.front();
180 for(G.first(e,v); G.valid(e); G.next(e)) {
181 if ( capacity[e] == flow[e] ) continue;
183 if ( level[w] == n && w != s ) {
185 Node first=level_list[l];
186 if ( G.valid(first) ) left.set(first,w);
194 for(G.first(f,v); G.valid(f); G.next(f)) {
195 if ( 0 == flow[f] ) continue;
197 if ( level[w] == n && w != s ) {
199 Node first=level_list[l];
200 if ( G.valid(first) ) left.set(first,w);
213 for(G.first(v); G.valid(v); G.next(v)) {
217 for(G.first(e,v); G.valid(e); G.next(e)) exc+=flow[e];
219 for(G.first(f,v); G.valid(f); G.next(f)) exc-=flow[e];
223 //putting the active nodes into the stack
225 if ( exc > 0 && lev < n ) {
226 next.set(v,active[lev]);
234 for(G.first(e,s); G.valid(e); G.next(e))
236 T rem=capacity[e]-flow[e];
237 if ( rem == 0 ) continue;
239 if ( level[w] < n ) {
240 if ( excess[w] == 0 && w!=t ) {
241 next.set(w,active[level[w]]);
244 flow.set(e, capacity[e]);
245 excess.set(w, excess[w]+rem);
250 for(G.first(f,s); G.valid(f); G.next(f))
252 if ( flow[f] == 0 ) continue;
254 if ( level[w] < n ) {
255 if ( excess[w] == 0 && w!=t ) {
256 next.set(w,active[level[w]]);
259 excess.set(w, excess[w]+flow[f]);
275 Push/relabel on the highest level active nodes.
282 if ( !what_heur && !end && k > 0 ) {
288 std::queue<Node> bfs_queue;
291 while (!bfs_queue.empty()) {
293 Node v=bfs_queue.front();
298 for(G.first(e,v); G.valid(e); G.next(e)) {
299 if ( capacity[e] == flow[e] ) continue;
301 if ( level[u] >= n ) {
304 if ( excess[u] > 0 ) {
305 next.set(u,active[l]);
312 for(G.first(f,v); G.valid(f); G.next(f)) {
313 if ( 0 == flow[f] ) continue;
315 if ( level[u] >= n ) {
318 if ( excess[u] > 0 ) {
319 next.set(u,active[l]);
331 if ( !G.valid(active[b]) ) --b;
339 int newlevel=n; //bound on the next level of w
342 for(G.first(e,w); G.valid(e); G.next(e)) {
344 if ( flow[e] == capacity[e] ) continue;
348 if( lev > level[v] ) {
349 /*Push is allowed now*/
351 if ( excess[v]==0 && v!=t && v!=s ) {
353 next.set(v,active[lev_v]);
361 if ( remcap >= exc ) {
362 /*A nonsaturating push.*/
364 flow.set(e, flo+exc);
365 excess.set(v, excess[v]+exc);
370 /*A saturating push.*/
373 excess.set(v, excess[v]+remcap);
376 } else if ( newlevel > level[v] ){
385 for(G.first(e,w); G.valid(e); G.next(e)) {
387 if( flow[e] == 0 ) continue;
391 if( lev > level[v] ) {
392 /*Push is allowed now*/
394 if ( excess[v]==0 && v!=t && v!=s ) {
396 next.set(v,active[lev_v]);
403 /*A nonsaturating push.*/
405 flow.set(e, flo-exc);
406 excess.set(v, excess[v]+exc);
410 /*A saturating push.*/
412 excess.set(v, excess[v]+flo);
416 } else if ( newlevel > level[v] ) {
421 } // if w still has excess after the out edge for cycle
431 //now 'lev' is the old level of w
434 level.set(w,++newlevel);
435 next.set(w,active[newlevel]);
440 Node right_n=right[w];
443 if ( G.valid(right_n) ) {
444 if ( G.valid(left_n) ) {
445 right.set(left_n, right_n);
446 left.set(right_n, left_n);
448 level_list[lev]=right_n;
449 left.set(right_n, INVALID);
452 if ( G.valid(left_n) ) {
453 right.set(left_n, INVALID);
455 level_list[lev]=INVALID;
460 if ( !G.valid(level_list[lev]) ) {
463 for (int i=lev; i!=k ; ) {
464 Node v=level_list[++i];
465 while ( G.valid(v) ) {
469 level_list[i]=INVALID;
470 if ( !what_heur ) active[i]=INVALID;
480 if ( newlevel == n ) level.set(w,n);
482 level.set(w,++newlevel);
483 next.set(w,active[newlevel]);
485 if ( what_heur ) b=newlevel;
486 if ( k < newlevel ) ++k; //now k=newlevel
487 Node first=level_list[newlevel];
488 if ( G.valid(first) ) left.set(first,w);
491 level_list[newlevel]=w;
497 if ( relabel >= heur ) {
515 } // if stack[b] is nonempty
530 Returns the maximum value of a flow.
544 void Flow(FlowMap& _flow ) {
546 for(G.first(v) ; G.valid(v); G.next(v))
547 _flow.set(v,flow[v]);
553 Returns the minimum min cut, by a bfs from s in the residual graph.
556 template<typename _CutMap>
557 void minMinCut(_CutMap& M) {
559 std::queue<Node> queue;
564 while (!queue.empty()) {
565 Node w=queue.front();
569 for(G.first(e,w) ; G.valid(e); G.next(e)) {
571 if (!M[v] && flow[e] < capacity[e] ) {
578 for(G.first(f,w) ; G.valid(f); G.next(f)) {
580 if (!M[v] && flow[f] > 0 ) {
591 Returns the maximum min cut, by a reverse bfs
592 from t in the residual graph.
595 template<typename _CutMap>
596 void maxMinCut(_CutMap& M) {
598 std::queue<Node> queue;
603 while (!queue.empty()) {
604 Node w=queue.front();
609 for(G.first(e,w) ; G.valid(e); G.next(e)) {
611 if (!M[v] && flow[e] < capacity[e] ) {
618 for(G.first(f,w) ; G.valid(f); G.next(f)) {
620 if (!M[v] && flow[f] > 0 ) {
628 for(G.first(v) ; G.valid(v); G.next(v)) {
636 template<typename CutMap>
637 void minCut(CutMap& M) {
642 void reset_target (Node _t) {t=_t;}
643 void reset_source (Node _s) {s=_s;}
645 template<typename _CapMap>
646 void reset_cap (_CapMap _cap) {capacity=_cap;}
648 template<typename _FlowMap>
649 void reset_cap (_FlowMap _flow, bool _constzero) {
651 constzero=_constzero;