jacint@47: /* jacint@47: preflow_push_max_flow_hh jacint@47: by jacint. jacint@47: Runs a preflow push algorithm with the modification, jacint@47: that we do not push on nodes with level at least n. jacint@47: Moreover, if a level gets empty, we put all nodes above that jacint@47: level to level n. Hence, in the end, we arrive at a maximum preflow jacint@47: with value of a max flow value. An empty level gives a minimum cut. jacint@47: jacint@47: Member functions: jacint@47: jacint@47: void run() : runs the algorithm jacint@47: jacint@47: The following functions should be used after run() was already run. jacint@47: jacint@47: T maxflow() : returns the value of a maximum flow jacint@47: jacint@47: node_property_vector mincut(): returns a jacint@47: characteristic vector of a minimum cut. jacint@47: */ jacint@47: jacint@47: #ifndef PREFLOW_PUSH_MAX_FLOW_HH jacint@47: #define PREFLOW_PUSH_MAX_FLOW_HH jacint@47: jacint@47: #include jacint@47: #include jacint@47: #include jacint@47: jacint@47: #include jacint@47: #include jacint@47: #include jacint@47: #include jacint@47: jacint@47: alpar@105: namespace hugo { jacint@47: jacint@47: template jacint@47: class preflow_push_max_flow { jacint@47: jacint@47: typedef typename graph_traits::node_iterator node_iterator; jacint@47: typedef typename graph_traits::each_node_iterator each_node_iterator; jacint@47: typedef typename graph_traits::out_edge_iterator out_edge_iterator; jacint@47: typedef typename graph_traits::in_edge_iterator in_edge_iterator; jacint@47: jacint@47: graph_type& G; jacint@47: node_iterator s; jacint@47: node_iterator t; jacint@47: edge_property_vector& capacity; jacint@47: T value; jacint@47: node_property_vector mincutvector; jacint@47: jacint@47: jacint@47: jacint@47: public: jacint@47: jacint@47: preflow_push_max_flow(graph_type& _G, node_iterator _s, node_iterator _t, edge_property_vector& _capacity) : G(_G), s(_s), t(_t), capacity(_capacity), mincutvector(_G, false) { } jacint@47: jacint@47: jacint@47: /* jacint@47: The run() function runs a modified version of the highest label preflow-push, which only jacint@47: finds a maximum preflow, hence giving the value of a maximum flow. jacint@47: */ jacint@47: void run() { jacint@47: jacint@47: edge_property_vector flow(G, 0); //the flow value, 0 everywhere jacint@47: node_property_vector level(G); //level of node jacint@47: node_property_vector excess(G); //excess of node jacint@47: jacint@47: int n=number_of(G.first_node()); //number of nodes jacint@47: int b=n-2; jacint@47: /*b is a bound on the highest level of an active node. In the beginning it is at most n-2.*/ jacint@47: jacint@47: std::vector numb(n); //The number of nodes on level i < n. jacint@47: jacint@47: std::vector > stack(2*n-1); //Stack of the active nodes in level i. jacint@47: jacint@47: jacint@47: jacint@47: /*Reverse_bfs from t, to find the starting level.*/ jacint@47: jacint@47: reverse_bfs bfs(G, t); jacint@47: bfs.run(); jacint@47: for(each_node_iterator v=G.first_node(); v.valid(); ++v) jacint@47: { jacint@47: int dist=bfs.dist(v); jacint@47: level.put(v, dist); jacint@47: ++numb[dist]; jacint@47: } jacint@47: jacint@47: /*The level of s is fixed to n*/ jacint@47: level.put(s,n); jacint@47: jacint@47: jacint@47: /* Starting flow. It is everywhere 0 at the moment. */ jacint@47: jacint@47: for(out_edge_iterator i=G.first_out_edge(s); i.valid(); ++i) jacint@47: { jacint@47: node_iterator w=G.head(i); jacint@47: flow.put(i, capacity.get(i)); jacint@47: stack[bfs.dist(w)].push(w); jacint@47: excess.put(w, capacity.get(i)); jacint@47: } jacint@47: jacint@47: jacint@47: /* jacint@47: End of preprocessing jacint@47: */ jacint@47: jacint@47: jacint@47: jacint@47: jacint@47: /* jacint@47: Push/relabel on the highest level active nodes. jacint@47: */ jacint@47: jacint@47: /*While there exists an active node.*/ jacint@47: while (b) { jacint@47: jacint@47: /*We decrease the bound if there is no active node of level b.*/ jacint@47: if (stack[b].empty()) { jacint@47: --b; jacint@47: } else { jacint@47: jacint@47: node_iterator w=stack[b].top(); //w is the highest label active node. jacint@47: stack[b].pop(); //We delete w from the stack. jacint@47: jacint@47: int newlevel=2*n-2; //In newlevel we maintain the next level of w. jacint@47: jacint@47: for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) { jacint@47: node_iterator v=G.head(e); jacint@47: /*e is the edge wv.*/ jacint@47: jacint@47: if (flow.get(e) excess.get(w)) { jacint@47: /*A nonsaturating push.*/ jacint@47: jacint@47: if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); jacint@47: /*v becomes active.*/ jacint@47: jacint@47: flow.put(e, flow.get(e)+excess.get(w)); jacint@47: excess.put(v, excess.get(v)+excess.get(w)); jacint@47: excess.put(w,0); jacint@47: //std::cout << w << " " << v <<" elore elen nonsat pump " << std::endl; jacint@47: break; jacint@47: } else { jacint@47: /*A saturating push.*/ jacint@47: jacint@47: if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); jacint@47: /*v becomes active.*/ jacint@47: jacint@47: excess.put(v, excess.get(v)+capacity.get(e)-flow.get(e)); jacint@47: excess.put(w, excess.get(w)-capacity.get(e)+flow.get(e)); jacint@47: flow.put(e, capacity.get(e)); jacint@47: //std::cout << w <<" " << v <<" elore elen sat pump " << std::endl; jacint@47: if (excess.get(w)==0) break; jacint@47: /*If w is not active any more, then we go on to the next node.*/ jacint@47: jacint@47: } // if (capacity.get(e)-flow.get(e) > excess.get(w)) jacint@47: } // if (level.get(w)==level.get(v)+1) jacint@47: jacint@47: else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);} jacint@47: jacint@47: } //if (flow.get(e)0) { jacint@47: /*e is an edge of the residual graph */ jacint@47: jacint@47: if(level.get(w)==level.get(v)+1) { jacint@47: /*Push is allowed now*/ jacint@47: jacint@47: if (flow.get(e) > excess.get(w)) { jacint@47: /*A nonsaturating push.*/ jacint@47: jacint@47: if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); jacint@47: /*v becomes active.*/ jacint@47: jacint@47: flow.put(e, flow.get(e)-excess.get(w)); jacint@47: excess.put(v, excess.get(v)+excess.get(w)); jacint@47: excess.put(w,0); jacint@47: //std::cout << v << " " << w << " vissza elen nonsat pump " << std::endl; jacint@47: break; jacint@47: } else { jacint@47: /*A saturating push.*/ jacint@47: jacint@47: if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); jacint@47: /*v becomes active.*/ jacint@47: jacint@47: flow.put(e,0); jacint@47: excess.put(v, excess.get(v)+flow.get(e)); jacint@47: excess.put(w, excess.get(w)-flow.get(e)); jacint@47: //std::cout << v <<" " << w << " vissza elen sat pump " << std::endl; jacint@47: if (excess.get(w)==0) { break;} jacint@47: } //if (flow.get(e) > excess.get(v)) jacint@47: } //if(level.get(w)==level.get(v)+1) jacint@47: jacint@47: else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);} jacint@47: //std::cout << "Leveldecrease of node " << w << " to " << newlevel << std::endl; jacint@47: jacint@47: } //if (flow.get(e)>0) jacint@47: jacint@47: } //for in-edge jacint@47: jacint@47: jacint@47: jacint@47: jacint@47: /* jacint@47: Relabel jacint@47: */ jacint@47: if (excess.get(w)>0) { jacint@47: /*Now newlevel <= n*/ jacint@47: jacint@47: int l=level.get(w); //l is the old level of w. jacint@47: --numb[l]; jacint@47: jacint@47: if (newlevel == n) { jacint@47: level.put(w,n); jacint@47: jacint@47: } else { jacint@47: jacint@47: if (numb[l]) { jacint@47: /*If the level of w remains nonempty.*/ jacint@47: jacint@47: level.put(w,++newlevel); jacint@47: ++numb[newlevel]; jacint@47: stack[newlevel].push(w); jacint@47: b=newlevel; jacint@47: } else { jacint@47: /*If the level of w gets empty.*/ jacint@47: jacint@47: for (each_node_iterator v=G.first_node() ; v.valid() ; ++v) { jacint@47: if (level.get(v) >= l ) { jacint@47: level.put(v,n); jacint@47: } jacint@47: } jacint@47: jacint@47: for (int i=l+1 ; i!=n ; ++i) numb[i]=0; jacint@47: } //if (numb[l]) jacint@47: jacint@47: } // if (newlevel = n) jacint@47: jacint@47: } // if (excess.get(w)>0) jacint@47: jacint@47: jacint@47: } //else jacint@47: jacint@47: } //while(b) jacint@47: jacint@47: value=excess.get(t); jacint@47: /*Max flow value.*/ jacint@47: jacint@47: jacint@47: jacint@47: /* jacint@47: We find an empty level, e. The nodes above this level give jacint@47: a minimum cut. jacint@47: */ jacint@47: jacint@47: int e=1; jacint@47: jacint@47: while(e) { jacint@47: if(numb[e]) ++e; jacint@47: else break; jacint@47: } jacint@47: for (each_node_iterator v=G.first_node(); v.valid(); ++v) { jacint@47: if (level.get(v) > e) mincutvector.put(v, true); jacint@47: } jacint@47: jacint@47: jacint@47: } // void run() jacint@47: jacint@47: jacint@47: jacint@47: /* jacint@47: Returns the maximum value of a flow. jacint@47: */ jacint@47: jacint@47: T maxflow() { jacint@47: return value; jacint@47: } jacint@47: jacint@47: jacint@47: jacint@47: /* jacint@47: Returns a minimum cut. jacint@47: */ jacint@47: jacint@47: node_property_vector mincut() { jacint@47: return mincutvector; jacint@47: } jacint@47: jacint@47: jacint@47: }; alpar@105: }//namespace hugo jacint@47: #endif jacint@47: jacint@47: jacint@47: jacint@47: jacint@47: