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
51 #include<graph_wrapper.h>
55 template <typename Graph, typename T,
56 typename CapMap=typename Graph::EdgeMap<T>,
57 typename FlowMap=typename Graph::EdgeMap<T> >
60 typedef typename Graph::Node Node;
61 typedef typename Graph::Edge Edge;
62 typedef typename Graph::NodeIt NodeIt;
63 typedef typename Graph::OutEdgeIt OutEdgeIt;
64 typedef typename Graph::InEdgeIt InEdgeIt;
69 const CapMap& capacity;
74 typedef ResGraphWrapper<const Graph, T, CapMap, FlowMap> ResGW;
75 typedef typename ResGW::OutEdgeIt ResOutEdgeIt;
76 typedef typename ResGW::InEdgeIt ResInEdgeIt;
77 typedef typename ResGW::Edge ResEdge;
80 Preflow(Graph& _G, Node _s, Node _t, CapMap& _capacity,
81 FlowMap& _flow, bool _constzero ) :
82 G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow), constzero(_constzero) {}
87 ResGW res_graph(G, capacity, flow);
89 value=0; //for the subsequent runs
91 bool phase=0; //phase 0 is the 1st phase, phase 1 is the 2nd
93 int heur0=(int)(H0*n); //time while running 'bound decrease'
94 int heur1=(int)(H1*n); //time while running 'highest label'
95 int heur=heur1; //starting time interval (#of relabels)
98 what_heur is 0 in case 'bound decrease'
99 and 1 in case 'highest label'
103 Needed for 'bound decrease', 'true'
104 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
110 typename Graph::NodeMap<int> level(G,n);
111 typename Graph::NodeMap<T> excess(G);
113 std::vector<Node> active(n-1,INVALID);
114 typename Graph::NodeMap<Node> next(G,INVALID);
115 //Stack of the active nodes in level i < n.
116 //We use it in both phases.
118 typename Graph::NodeMap<Node> left(G,INVALID);
119 typename Graph::NodeMap<Node> right(G,INVALID);
120 std::vector<Node> level_list(n,INVALID);
122 List of the nodes in level i<n.
128 /*Reverse_bfs from t, to find the starting level.*/
130 std::queue<Node> bfs_queue;
133 while (!bfs_queue.empty()) {
135 Node v=bfs_queue.front();
140 for(G.first(e,v); G.valid(e); G.next(e)) {
142 if ( level[w] == n && w != s ) {
144 Node first=level_list[l];
145 if ( G.valid(first) ) left.set(first,w);
155 for(G.first(e,s); G.valid(e); G.next(e))
158 if ( c == 0 ) continue;
160 if ( level[w] < n ) {
161 if ( excess[w] == 0 && w!=t ) {
162 next.set(w,active[level[w]]);
166 excess.set(w, excess[w]+c);
174 Reverse_bfs from t in the residual graph,
175 to find the starting level.
178 std::queue<Node> bfs_queue;
181 while (!bfs_queue.empty()) {
183 Node v=bfs_queue.front();
188 for(G.first(e,v); G.valid(e); G.next(e)) {
189 if ( capacity[e] == flow[e] ) continue;
191 if ( level[w] == n && w != s ) {
193 Node first=level_list[l];
194 if ( G.valid(first) ) left.set(first,w);
202 for(G.first(f,v); G.valid(f); G.next(f)) {
203 if ( 0 == flow[f] ) continue;
205 if ( level[w] == n && w != s ) {
207 Node first=level_list[l];
208 if ( G.valid(first) ) left.set(first,w);
221 for(G.first(v); G.valid(v); G.next(v)) {
225 for(G.first(e,v); G.valid(e); G.next(e)) exc+=flow[e];
227 for(G.first(f,v); G.valid(f); G.next(f)) exc-=flow[e];
231 //putting the active nodes into the stack
233 if ( exc > 0 && lev < n ) {
234 next.set(v,active[lev]);
242 for(G.first(e,s); G.valid(e); G.next(e))
244 T rem=capacity[e]-flow[e];
245 if ( rem == 0 ) continue;
247 if ( level[w] < n ) {
248 if ( excess[w] == 0 && w!=t ) {
249 next.set(w,active[level[w]]);
252 flow.set(e, capacity[e]);
253 excess.set(w, excess[w]+rem);
258 for(G.first(f,s); G.valid(f); G.next(f))
260 if ( flow[f] == 0 ) continue;
262 if ( level[w] < n ) {
263 if ( excess[w] == 0 && w!=t ) {
264 next.set(w,active[level[w]]);
267 excess.set(w, excess[w]+flow[f]);
283 Push/relabel on the highest level active nodes.
290 if ( !what_heur && !end && k > 0 ) {
296 std::queue<Node> bfs_queue;
299 while (!bfs_queue.empty()) {
301 Node v=bfs_queue.front();
306 for(res_graph.first(e,s); res_graph.valid(e);
308 Node u=res_graph.tail(e);
309 if ( level[u] >= n ) {
312 if ( excess[u] > 0 ) {
313 next.set(u,active[l]);
319 for(G.first(e,v); G.valid(e); G.next(e)) {
320 if ( capacity[e] == flow[e] ) continue;
322 if ( level[u] >= n ) {
325 if ( excess[u] > 0 ) {
326 next.set(u,active[l]);
333 for(G.first(f,v); G.valid(f); G.next(f)) {
334 if ( 0 == flow[f] ) continue;
336 if ( level[u] >= n ) {
339 if ( excess[u] > 0 ) {
340 next.set(u,active[l]);
352 if ( !G.valid(active[b]) ) --b;
360 int newlevel=n; //bound on the next level of w
363 for(G.first(e,w); G.valid(e); G.next(e)) {
365 if ( flow[e] == capacity[e] ) continue;
369 if( lev > level[v] ) {
370 /*Push is allowed now*/
372 if ( excess[v]==0 && v!=t && v!=s ) {
374 next.set(v,active[lev_v]);
382 if ( remcap >= exc ) {
383 /*A nonsaturating push.*/
385 flow.set(e, flo+exc);
386 excess.set(v, excess[v]+exc);
391 /*A saturating push.*/
394 excess.set(v, excess[v]+remcap);
397 } else if ( newlevel > level[v] ){
406 for(G.first(e,w); G.valid(e); G.next(e)) {
408 if( flow[e] == 0 ) continue;
412 if( lev > level[v] ) {
413 /*Push is allowed now*/
415 if ( excess[v]==0 && v!=t && v!=s ) {
417 next.set(v,active[lev_v]);
424 /*A nonsaturating push.*/
426 flow.set(e, flo-exc);
427 excess.set(v, excess[v]+exc);
431 /*A saturating push.*/
433 excess.set(v, excess[v]+flo);
437 } else if ( newlevel > level[v] ) {
442 } // if w still has excess after the out edge for cycle
452 //now 'lev' is the old level of w
455 level.set(w,++newlevel);
456 next.set(w,active[newlevel]);
461 Node right_n=right[w];
464 if ( G.valid(right_n) ) {
465 if ( G.valid(left_n) ) {
466 right.set(left_n, right_n);
467 left.set(right_n, left_n);
469 level_list[lev]=right_n;
470 left.set(right_n, INVALID);
473 if ( G.valid(left_n) ) {
474 right.set(left_n, INVALID);
476 level_list[lev]=INVALID;
481 if ( !G.valid(level_list[lev]) ) {
484 for (int i=lev; i!=k ; ) {
485 Node v=level_list[++i];
486 while ( G.valid(v) ) {
490 level_list[i]=INVALID;
491 if ( !what_heur ) active[i]=INVALID;
501 if ( newlevel == n ) level.set(w,n);
503 level.set(w,++newlevel);
504 next.set(w,active[newlevel]);
506 if ( what_heur ) b=newlevel;
507 if ( k < newlevel ) ++k; //now k=newlevel
508 Node first=level_list[newlevel];
509 if ( G.valid(first) ) left.set(first,w);
512 level_list[newlevel]=w;
518 if ( relabel >= heur ) {
536 } // if stack[b] is nonempty
551 Returns the maximum value of a flow.
565 void Flow(FlowMap& _flow ) {
567 for(G.first(v) ; G.valid(v); G.next(v))
568 _flow.set(v,flow[v]);
574 Returns the minimum min cut, by a bfs from s in the residual graph.
577 template<typename _CutMap>
578 void minMinCut(_CutMap& M) {
580 std::queue<Node> queue;
585 while (!queue.empty()) {
586 Node w=queue.front();
590 for(G.first(e,w) ; G.valid(e); G.next(e)) {
592 if (!M[v] && flow[e] < capacity[e] ) {
599 for(G.first(f,w) ; G.valid(f); G.next(f)) {
601 if (!M[v] && flow[f] > 0 ) {
612 Returns the maximum min cut, by a reverse bfs
613 from t in the residual graph.
616 template<typename _CutMap>
617 void maxMinCut(_CutMap& M) {
619 std::queue<Node> queue;
624 while (!queue.empty()) {
625 Node w=queue.front();
630 for(G.first(e,w) ; G.valid(e); G.next(e)) {
632 if (!M[v] && flow[e] < capacity[e] ) {
639 for(G.first(f,w) ; G.valid(f); G.next(f)) {
641 if (!M[v] && flow[f] > 0 ) {
649 for(G.first(v) ; G.valid(v); G.next(v)) {
657 template<typename CutMap>
658 void minCut(CutMap& M) {
663 void reset_target (Node _t) {t=_t;}
664 void reset_source (Node _s) {s=_s;}
666 template<typename _CapMap>
667 void reset_cap (_CapMap _cap) {capacity=_cap;}
669 template<typename _FlowMap>
670 void reset_cap (_FlowMap _flow, bool _constzero) {
672 constzero=_constzero;