1.1 --- a/src/work/jacint/preflow_push_hl.hh Fri Feb 20 22:01:02 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,320 +0,0 @@
1.4 -/*
1.5 -preflow_push_hl.hh
1.6 -by jacint.
1.7 -Runs the highest label variant of the preflow push algorithm with
1.8 -running time O(n^2\sqrt(m)).
1.9 -
1.10 -Member functions:
1.11 -
1.12 -void run() : runs the algorithm
1.13 -
1.14 - The following functions should be used after run() was already run.
1.15 -
1.16 -T maxflow() : returns the value of a maximum flow
1.17 -
1.18 -T flowonedge(edge_iterator e) : for a fixed maximum flow x it returns x(e)
1.19 -
1.20 -edge_property_vector<graph_type, T> allflow() : returns the fixed maximum flow x
1.21 -
1.22 -node_property_vector<graph_type, bool> mincut() : returns a
1.23 - characteristic vector of a minimum cut. (An empty level
1.24 - in the algorithm gives a minimum cut.)
1.25 -*/
1.26 -
1.27 -#ifndef PREFLOW_PUSH_HL_HH
1.28 -#define PREFLOW_PUSH_HL_HH
1.29 -
1.30 -#include <algorithm>
1.31 -#include <vector>
1.32 -#include <stack>
1.33 -
1.34 -#include <marci_graph_traits.hh>
1.35 -#include <marci_property_vector.hh>
1.36 -#include <reverse_bfs.hh>
1.37 -
1.38 -namespace hugo {
1.39 -
1.40 - template <typename graph_type, typename T>
1.41 - class preflow_push_hl {
1.42 -
1.43 - typedef typename graph_traits<graph_type>::node_iterator node_iterator;
1.44 - typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
1.45 - typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
1.46 - typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
1.47 - typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
1.48 - typedef typename graph_traits<graph_type>::each_edge_iterator each_edge_iterator;
1.49 -
1.50 -
1.51 - graph_type& G;
1.52 - node_iterator s;
1.53 - node_iterator t;
1.54 - edge_property_vector<graph_type, T> flow;
1.55 - edge_property_vector<graph_type, T>& capacity;
1.56 - T value;
1.57 - node_property_vector<graph_type, bool> mincutvector;
1.58 -
1.59 -
1.60 - public:
1.61 -
1.62 - preflow_push_hl(graph_type& _G, node_iterator _s, node_iterator _t, edge_property_vector<graph_type, T>& _capacity) : G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), mincutvector(_G, true) { }
1.63 -
1.64 -
1.65 -
1.66 -
1.67 - /*
1.68 - The run() function runs the highest label preflow-push,
1.69 - running time: O(n^2\sqrt(m))
1.70 - */
1.71 - void run() {
1.72 -
1.73 - node_property_vector<graph_type, int> level(G); //level of node
1.74 - node_property_vector<graph_type, T> excess(G); //excess of node
1.75 -
1.76 - int n=number_of(G.first_node()); //number of nodes
1.77 - int b=n;
1.78 - /*b is a bound on the highest level of an active node. In the beginning it is at most n-2.*/
1.79 -
1.80 - std::vector<std::stack<node_iterator> > stack(2*n-1); //Stack of the active nodes in level i.
1.81 -
1.82 -
1.83 -
1.84 -
1.85 - /*Reverse_bfs from t, to find the starting level.*/
1.86 -
1.87 - reverse_bfs<list_graph> bfs(G, t);
1.88 - bfs.run();
1.89 - for(each_node_iterator v=G.first_node(); v.valid(); ++v) {
1.90 - level.put(v, bfs.dist(v));
1.91 - //std::cout << "the level of " << v << " is " << bfs.dist(v);
1.92 - }
1.93 -
1.94 - /*The level of s is fixed to n*/
1.95 - level.put(s,n);
1.96 -
1.97 -
1.98 -
1.99 -
1.100 -
1.101 - /* Starting flow. It is everywhere 0 at the moment. */
1.102 -
1.103 - for(out_edge_iterator i=G.first_out_edge(s); i.valid(); ++i)
1.104 - {
1.105 - node_iterator w=G.head(i);
1.106 - flow.put(i, capacity.get(i));
1.107 - stack[bfs.dist(w)].push(w);
1.108 - excess.put(w, capacity.get(i));
1.109 - }
1.110 -
1.111 -
1.112 - /*
1.113 - End of preprocessing
1.114 - */
1.115 -
1.116 -
1.117 -
1.118 - /*
1.119 - Push/relabel on the highest level active nodes.
1.120 - */
1.121 -
1.122 - /*While there exists active node.*/
1.123 - while (b) {
1.124 -
1.125 - /*We decrease the bound if there is no active node of level b.*/
1.126 - if (stack[b].empty()) {
1.127 - --b;
1.128 - } else {
1.129 -
1.130 - node_iterator w=stack[b].top(); //w is the highest label active node.
1.131 - stack[b].pop(); //We delete w from the stack.
1.132 -
1.133 - int newlevel=2*n-2; //In newlevel we maintain the next level of w.
1.134 -
1.135 - for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) {
1.136 - node_iterator v=G.head(e);
1.137 - /*e is the edge wv.*/
1.138 -
1.139 - if (flow.get(e)<capacity.get(e)) {
1.140 - /*e is an edge of the residual graph */
1.141 -
1.142 - if(level.get(w)==level.get(v)+1) {
1.143 - /*Push is allowed now*/
1.144 -
1.145 - if (capacity.get(e)-flow.get(e) > excess.get(w)) {
1.146 - /*A nonsaturating push.*/
1.147 -
1.148 - if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
1.149 - /*v becomes active.*/
1.150 -
1.151 - flow.put(e, flow.get(e)+excess.get(w));
1.152 - excess.put(v, excess.get(v)+excess.get(w));
1.153 - excess.put(w,0);
1.154 - //std::cout << w << " " << v <<" elore elen nonsat pump " << std::endl;
1.155 - break;
1.156 - } else {
1.157 - /*A saturating push.*/
1.158 -
1.159 - if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
1.160 - /*v becomes active.*/
1.161 -
1.162 - excess.put(v, excess.get(v)+capacity.get(e)-flow.get(e));
1.163 - excess.put(w, excess.get(w)-capacity.get(e)+flow.get(e));
1.164 - flow.put(e, capacity.get(e));
1.165 - //std::cout << w<<" " <<v<<" elore elen sat pump " << std::endl;
1.166 - if (excess.get(w)==0) break;
1.167 - /*If w is not active any more, then we go on to the next node.*/
1.168 -
1.169 - } // if (capacity.get(e)-flow.get(e) > excess.get(w))
1.170 - } // if(level.get(w)==level.get(v)+1)
1.171 -
1.172 - else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
1.173 -
1.174 - } //if (flow.get(e)<capacity.get(e))
1.175 -
1.176 - } //for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e)
1.177 -
1.178 -
1.179 -
1.180 - for(in_edge_iterator e=G.first_in_edge(w); e.valid(); ++e) {
1.181 - node_iterator v=G.tail(e);
1.182 - /*e is the edge vw.*/
1.183 -
1.184 - if (excess.get(w)==0) break;
1.185 - /*It may happen, that w became inactive in the first for cycle.*/
1.186 - if(flow.get(e)>0) {
1.187 - /*e is an edge of the residual graph */
1.188 -
1.189 - if(level.get(w)==level.get(v)+1) {
1.190 - /*Push is allowed now*/
1.191 -
1.192 - if (flow.get(e) > excess.get(w)) {
1.193 - /*A nonsaturating push.*/
1.194 -
1.195 - if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
1.196 - /*v becomes active.*/
1.197 -
1.198 - flow.put(e, flow.get(e)-excess.get(w));
1.199 - excess.put(v, excess.get(v)+excess.get(w));
1.200 - excess.put(w,0);
1.201 - //std::cout << v << " " << w << " vissza elen nonsat pump " << std::endl;
1.202 - break;
1.203 - } else {
1.204 - /*A saturating push.*/
1.205 -
1.206 - if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
1.207 - /*v becomes active.*/
1.208 -
1.209 - excess.put(v, excess.get(v)+flow.get(e));
1.210 - excess.put(w, excess.get(w)-flow.get(e));
1.211 - flow.put(e,0);
1.212 - //std::cout << v <<" " << w << " vissza elen sat pump " << std::endl;
1.213 - if (excess.get(w)==0) { break;}
1.214 - } //if (flow.get(e) > excess.get(v))
1.215 - } //if(level.get(w)==level.get(v)+1)
1.216 -
1.217 - else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
1.218 -
1.219 -
1.220 - } //if (flow.get(e)>0)
1.221 -
1.222 - } //for
1.223 -
1.224 -
1.225 - if (excess.get(w)>0) {
1.226 - level.put(w,++newlevel);
1.227 - stack[newlevel].push(w);
1.228 - b=newlevel;
1.229 - //std::cout << "The new level of " << w << " is "<< newlevel <<std::endl;
1.230 - }
1.231 -
1.232 -
1.233 - } //else
1.234 -
1.235 - } //while(b)
1.236 -
1.237 - value = excess.get(t);
1.238 - /*Max flow value.*/
1.239 -
1.240 -
1.241 -
1.242 -
1.243 - } //void run()
1.244 -
1.245 -
1.246 -
1.247 -
1.248 -
1.249 - /*
1.250 - Returns the maximum value of a flow.
1.251 - */
1.252 -
1.253 - T maxflow() {
1.254 - return value;
1.255 - }
1.256 -
1.257 -
1.258 -
1.259 - /*
1.260 - For the maximum flow x found by the algorithm, it returns the flow value on edge e, i.e. x(e).
1.261 - */
1.262 -
1.263 - T flowonedge(edge_iterator e) {
1.264 - return flow.get(e);
1.265 - }
1.266 -
1.267 -
1.268 -
1.269 - /*
1.270 - Returns the maximum flow x found by the algorithm.
1.271 - */
1.272 -
1.273 - edge_property_vector<graph_type, T> allflow() {
1.274 - return flow;
1.275 - }
1.276 -
1.277 -
1.278 -
1.279 - /*
1.280 - Returns a minimum cut by using a reverse bfs from t in the residual graph.
1.281 - */
1.282 -
1.283 - node_property_vector<graph_type, bool> mincut() {
1.284 -
1.285 - std::queue<node_iterator> queue;
1.286 -
1.287 - mincutvector.put(t,false);
1.288 - queue.push(t);
1.289 -
1.290 - while (!queue.empty()) {
1.291 - node_iterator w=queue.front();
1.292 - queue.pop();
1.293 -
1.294 - for(in_edge_iterator e=G.first_in_edge(w) ; e.valid(); ++e) {
1.295 - node_iterator v=G.tail(e);
1.296 - if (mincutvector.get(v) && flow.get(e) < capacity.get(e) ) {
1.297 - queue.push(v);
1.298 - mincutvector.put(v, false);
1.299 - }
1.300 - } // for
1.301 -
1.302 - for(out_edge_iterator e=G.first_out_edge(w) ; e.valid(); ++e) {
1.303 - node_iterator v=G.head(e);
1.304 - if (mincutvector.get(v) && flow.get(e) > 0 ) {
1.305 - queue.push(v);
1.306 - mincutvector.put(v, false);
1.307 - }
1.308 - } // for
1.309 -
1.310 - }
1.311 -
1.312 - return mincutvector;
1.313 -
1.314 - }
1.315 -
1.316 -
1.317 - };
1.318 -}//namespace hugo
1.319 -#endif
1.320 -
1.321 -
1.322 -
1.323 -