Concept modification to resolve the item by its ID.
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
8 //constzero helyett az kell hogy flow-e vagy csak preflow, ha flow akor csak
9 //excess[t]-t kell szmaolni
15 list 'level_list' on the nodes on level i implemented by hand
16 stack 'active' on the active nodes on level i implemented by hand
17 runs heuristic 'highest label' for H1*n relabels
18 runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label'
20 Parameters H0 and H1 are initialized to 20 and 10.
24 Preflow(Graph, Node, Node, CapMap, FlowMap, bool) : bool must be false if
25 FlowMap is not constant zero, and should be true if it is
31 T flowValue() : returns the value of a maximum flow
33 void minMinCut(CutMap& M) : sets M to the characteristic vector of the
34 minimum min cut. M should be a map of bools initialized to false.
36 void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
37 maximum min cut. M should be a map of bools initialized to false.
39 void minCut(CutMap& M) : sets M to the characteristic vector of
40 a min cut. M should be a map of bools initialized to false.
46 #ifndef LEMON_PREFLOW_H
47 #define LEMON_PREFLOW_H
58 template <typename Graph, typename T,
59 typename CapMap=typename Graph::template EdgeMap<T>,
60 typename FlowMap=typename Graph::template EdgeMap<T> >
63 typedef typename Graph::Node Node;
64 typedef typename Graph::Edge Edge;
65 typedef typename Graph::NodeIt NodeIt;
66 typedef typename Graph::OutEdgeIt OutEdgeIt;
67 typedef typename Graph::InEdgeIt InEdgeIt;
72 const CapMap& capacity;
79 Preflow(Graph& _G, Node _s, Node _t, CapMap& _capacity,
80 FlowMap& _flow, bool _constzero, bool _isflow ) :
81 G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow), constzero(_constzero), isflow(_isflow) {}
86 value=0; //for the subsequent runs
88 bool phase=0; //phase 0 is the 1st phase, phase 1 is the 2nd
90 int heur0=(int)(H0*n); //time while running 'bound decrease'
91 int heur1=(int)(H1*n); //time while running 'highest label'
92 int heur=heur1; //starting time interval (#of relabels)
95 what_heur is 0 in case 'bound decrease'
96 and 1 in case 'highest label'
100 Needed for 'bound decrease', 'true'
101 means no active nodes are above bound b.
104 int k=n-2; //bound on the highest level under n containing a node
105 int b=k; //bound on the highest level under n of an active node
107 typename Graph::template NodeMap<int> level(G,n);
108 typename Graph::template NodeMap<T> excess(G);
110 std::vector<std::stack<Node> > active(n);
111 /* std::vector<Node> active(n-1,INVALID);
112 typename Graph::template NodeMap<Node> next(G,INVALID);
113 //Stack of the active nodes in level i < n.
114 //We use it in both phases.*/
116 typename Graph::template NodeMap<Node> left(G,INVALID);
117 typename Graph::template NodeMap<Node> right(G,INVALID);
118 std::vector<Node> level_list(n,INVALID);
120 List of the nodes in level i<n.
126 /*Reverse_bfs from t, to find the starting level.*/
128 std::queue<Node> bfs_queue;
131 while (!bfs_queue.empty()) {
133 Node v=bfs_queue.front();
138 for(G.first(e,v); G.valid(e); G.next(e)) {
140 if ( level[w] == n && w != s ) {
142 Node first=level_list[l];
143 if ( G.valid(first) ) left.set(first,w);
153 for(G.first(e,s); G.valid(e); G.next(e))
156 if ( c == 0 ) continue;
158 if ( level[w] < n ) {
159 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
161 excess.set(w, excess[w]+c);
169 Reverse_bfs from t in the residual graph,
170 to find the starting level.
173 std::queue<Node> bfs_queue;
176 while (!bfs_queue.empty()) {
178 Node v=bfs_queue.front();
183 for(G.first(e,v); G.valid(e); G.next(e)) {
184 if ( capacity[e] == flow[e] ) continue;
186 if ( level[w] == n && w != s ) {
188 Node first=level_list[l];
189 if ( G.valid(first) ) left.set(first,w);
197 for(G.first(f,v); G.valid(f); G.next(f)) {
198 if ( 0 == flow[f] ) continue;
200 if ( level[w] == n && w != s ) {
202 Node first=level_list[l];
203 if ( G.valid(first) ) left.set(first,w);
218 for(G.first(v); G.valid(v); G.next(v)) {
222 for(G.first(e,v); G.valid(e); G.next(e)) exc+=flow[e];
224 for(G.first(f,v); G.valid(f); G.next(f)) exc-=flow[f];
228 //putting the active nodes into the stack
230 if ( exc > 0 && lev < n && v != t ) active[lev].push(v);
236 for(G.first(e,t); G.valid(e); G.next(e)) exc+=flow[e];
238 for(G.first(f,t); G.valid(f); G.next(f)) exc-=flow[f];
246 for(G.first(e,s); G.valid(e); G.next(e))
248 T rem=capacity[e]-flow[e];
249 if ( rem == 0 ) continue;
251 if ( level[w] < n ) {
252 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
253 flow.set(e, capacity[e]);
254 excess.set(w, excess[w]+rem);
259 for(G.first(f,s); G.valid(f); G.next(f))
261 if ( flow[f] == 0 ) continue;
263 if ( level[w] < n ) {
264 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
265 excess.set(w, excess[w]+flow[f]);
281 Push/relabel on the highest level active nodes.
288 if ( !what_heur && !end && k > 0 ) {
294 std::queue<Node> bfs_queue;
297 while (!bfs_queue.empty()) {
299 Node v=bfs_queue.front();
304 for(G.first(e,v); G.valid(e); G.next(e)) {
305 if ( capacity[e] == flow[e] ) continue;
307 if ( level[u] >= n ) {
310 if ( excess[u] > 0 ) active[l].push(u);
315 for(G.first(f,v); G.valid(f); G.next(f)) {
316 if ( 0 == flow[f] ) continue;
318 if ( level[u] >= n ) {
321 if ( excess[u] > 0 ) active[l].push(u);
332 if ( active[b].empty() ) --b;
336 Node w=active[b].top();
340 int newlevel=n; //bound on the next level of w
343 for(G.first(e,w); G.valid(e); G.next(e)) {
345 if ( flow[e] == capacity[e] ) continue;
349 if( lev > level[v] ) {
350 /*Push is allowed now*/
352 if ( excess[v]==0 && v!=t && v!=s ) {
354 active[lev_v].push(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 active[lev_v].push(v);
402 /*A nonsaturating push.*/
404 flow.set(e, flo-exc);
405 excess.set(v, excess[v]+exc);
409 /*A saturating push.*/
411 excess.set(v, excess[v]+flo);
415 } else if ( newlevel > level[v] ) {
420 } // if w still has excess after the out edge for cycle
432 //now 'lev' is the old level of w
435 level.set(w,++newlevel);
436 active[newlevel].push(w);
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;
471 while ( !active[i].empty() ) {
472 active[i].pop(); //FIXME: ezt szebben kene
484 if ( newlevel == n ) level.set(w,n);
486 level.set(w,++newlevel);
487 active[newlevel].push(w);
488 if ( what_heur ) b=newlevel;
489 if ( k < newlevel ) ++k; //now k=newlevel
490 Node first=level_list[newlevel];
491 if ( G.valid(first) ) left.set(first,w);
494 level_list[newlevel]=w;
500 if ( relabel >= heur ) {
518 } // if stack[b] is nonempty
533 Returns the maximum value of a flow.
546 void Flow(FlowMap& _flow ) {
548 for(G.first(v) ; G.valid(v); G.next(v))
549 _flow.set(v,flow[v]);
555 Returns the minimum min cut, by a bfs from s in the residual graph.
558 template<typename _CutMap>
559 void minMinCut(_CutMap& M) {
561 std::queue<Node> queue;
566 while (!queue.empty()) {
567 Node w=queue.front();
571 for(G.first(e,w) ; G.valid(e); G.next(e)) {
573 if (!M[v] && flow[e] < capacity[e] ) {
580 for(G.first(f,w) ; G.valid(f); G.next(f)) {
582 if (!M[v] && flow[f] > 0 ) {
593 Returns the maximum min cut, by a reverse bfs
594 from t in the residual graph.
597 template<typename _CutMap>
598 void maxMinCut(_CutMap& M) {
600 std::queue<Node> queue;
605 while (!queue.empty()) {
606 Node w=queue.front();
611 for(G.first(e,w) ; G.valid(e); G.next(e)) {
613 if (!M[v] && flow[e] < capacity[e] ) {
620 for(G.first(f,w) ; G.valid(f); G.next(f)) {
622 if (!M[v] && flow[f] > 0 ) {
630 for(G.first(v) ; G.valid(v); G.next(v)) {
638 template<typename CutMap>
639 void minCut(CutMap& M) {
644 void resetTarget (Node _t) {t=_t;}
645 void resetSource (Node _s) {s=_s;}
647 void resetCap (CapMap _cap) {capacity=_cap;}
649 void resetFlow (FlowMap _flow, bool _constzero) {
651 constzero=_constzero;