1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/jacint/preflow_push_hl.hh Fri Jan 30 14:53:17 2004 +0000
1.3 @@ -0,0 +1,320 @@
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 marci {
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 marci
1.319 +#endif
1.320 +
1.321 +
1.322 +
1.323 +
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/jacint/preflow_push_max_flow.hh Fri Jan 30 14:53:17 2004 +0000
2.3 @@ -0,0 +1,315 @@
2.4 +/*
2.5 +preflow_push_max_flow_hh
2.6 +by jacint.
2.7 +Runs a preflow push algorithm with the modification,
2.8 +that we do not push on nodes with level at least n.
2.9 +Moreover, if a level gets empty, we put all nodes above that
2.10 +level to level n. Hence, in the end, we arrive at a maximum preflow
2.11 +with value of a max flow value. An empty level gives a minimum cut.
2.12 +
2.13 +Member functions:
2.14 +
2.15 +void run() : runs the algorithm
2.16 +
2.17 + The following functions should be used after run() was already run.
2.18 +
2.19 +T maxflow() : returns the value of a maximum flow
2.20 +
2.21 +node_property_vector<graph_type, bool> mincut(): returns a
2.22 + characteristic vector of a minimum cut.
2.23 +*/
2.24 +
2.25 +#ifndef PREFLOW_PUSH_MAX_FLOW_HH
2.26 +#define PREFLOW_PUSH_MAX_FLOW_HH
2.27 +
2.28 +#include <algorithm>
2.29 +#include <vector>
2.30 +#include <stack>
2.31 +
2.32 +#include <marci_list_graph.hh>
2.33 +#include <marci_graph_traits.hh>
2.34 +#include <marci_property_vector.hh>
2.35 +#include <reverse_bfs.hh>
2.36 +
2.37 +
2.38 +namespace marci {
2.39 +
2.40 + template <typename graph_type, typename T>
2.41 + class preflow_push_max_flow {
2.42 +
2.43 + typedef typename graph_traits<graph_type>::node_iterator node_iterator;
2.44 + typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
2.45 + typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
2.46 + typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
2.47 +
2.48 + graph_type& G;
2.49 + node_iterator s;
2.50 + node_iterator t;
2.51 + edge_property_vector<graph_type, T>& capacity;
2.52 + T value;
2.53 + node_property_vector<graph_type, bool> mincutvector;
2.54 +
2.55 +
2.56 +
2.57 + public:
2.58 +
2.59 + preflow_push_max_flow(graph_type& _G, node_iterator _s, node_iterator _t, edge_property_vector<graph_type, T>& _capacity) : G(_G), s(_s), t(_t), capacity(_capacity), mincutvector(_G, false) { }
2.60 +
2.61 +
2.62 + /*
2.63 + The run() function runs a modified version of the highest label preflow-push, which only
2.64 + finds a maximum preflow, hence giving the value of a maximum flow.
2.65 + */
2.66 + void run() {
2.67 +
2.68 + edge_property_vector<graph_type, T> flow(G, 0); //the flow value, 0 everywhere
2.69 + node_property_vector<graph_type, int> level(G); //level of node
2.70 + node_property_vector<graph_type, T> excess(G); //excess of node
2.71 +
2.72 + int n=number_of(G.first_node()); //number of nodes
2.73 + int b=n-2;
2.74 + /*b is a bound on the highest level of an active node. In the beginning it is at most n-2.*/
2.75 +
2.76 + std::vector<int> numb(n); //The number of nodes on level i < n.
2.77 +
2.78 + std::vector<std::stack<node_iterator> > stack(2*n-1); //Stack of the active nodes in level i.
2.79 +
2.80 +
2.81 +
2.82 + /*Reverse_bfs from t, to find the starting level.*/
2.83 +
2.84 + reverse_bfs<list_graph> bfs(G, t);
2.85 + bfs.run();
2.86 + for(each_node_iterator v=G.first_node(); v.valid(); ++v)
2.87 + {
2.88 + int dist=bfs.dist(v);
2.89 + level.put(v, dist);
2.90 + ++numb[dist];
2.91 + }
2.92 +
2.93 + /*The level of s is fixed to n*/
2.94 + level.put(s,n);
2.95 +
2.96 +
2.97 + /* Starting flow. It is everywhere 0 at the moment. */
2.98 +
2.99 + for(out_edge_iterator i=G.first_out_edge(s); i.valid(); ++i)
2.100 + {
2.101 + node_iterator w=G.head(i);
2.102 + flow.put(i, capacity.get(i));
2.103 + stack[bfs.dist(w)].push(w);
2.104 + excess.put(w, capacity.get(i));
2.105 + }
2.106 +
2.107 +
2.108 + /*
2.109 + End of preprocessing
2.110 + */
2.111 +
2.112 +
2.113 +
2.114 +
2.115 + /*
2.116 + Push/relabel on the highest level active nodes.
2.117 + */
2.118 +
2.119 + /*While there exists an active node.*/
2.120 + while (b) {
2.121 +
2.122 + /*We decrease the bound if there is no active node of level b.*/
2.123 + if (stack[b].empty()) {
2.124 + --b;
2.125 + } else {
2.126 +
2.127 + node_iterator w=stack[b].top(); //w is the highest label active node.
2.128 + stack[b].pop(); //We delete w from the stack.
2.129 +
2.130 + int newlevel=2*n-2; //In newlevel we maintain the next level of w.
2.131 +
2.132 + for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) {
2.133 + node_iterator v=G.head(e);
2.134 + /*e is the edge wv.*/
2.135 +
2.136 + if (flow.get(e)<capacity.get(e)) {
2.137 + /*e is an edge of the residual graph */
2.138 +
2.139 + if(level.get(w)==level.get(v)+1) {
2.140 + /*Push is allowed now*/
2.141 +
2.142 + if (capacity.get(e)-flow.get(e) > excess.get(w)) {
2.143 + /*A nonsaturating push.*/
2.144 +
2.145 + if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
2.146 + /*v becomes active.*/
2.147 +
2.148 + flow.put(e, flow.get(e)+excess.get(w));
2.149 + excess.put(v, excess.get(v)+excess.get(w));
2.150 + excess.put(w,0);
2.151 + //std::cout << w << " " << v <<" elore elen nonsat pump " << std::endl;
2.152 + break;
2.153 + } else {
2.154 + /*A saturating push.*/
2.155 +
2.156 + if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
2.157 + /*v becomes active.*/
2.158 +
2.159 + excess.put(v, excess.get(v)+capacity.get(e)-flow.get(e));
2.160 + excess.put(w, excess.get(w)-capacity.get(e)+flow.get(e));
2.161 + flow.put(e, capacity.get(e));
2.162 + //std::cout << w <<" " << v <<" elore elen sat pump " << std::endl;
2.163 + if (excess.get(w)==0) break;
2.164 + /*If w is not active any more, then we go on to the next node.*/
2.165 +
2.166 + } // if (capacity.get(e)-flow.get(e) > excess.get(w))
2.167 + } // if (level.get(w)==level.get(v)+1)
2.168 +
2.169 + else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
2.170 +
2.171 + } //if (flow.get(e)<capacity.get(e))
2.172 +
2.173 + } //for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e)
2.174 +
2.175 +
2.176 +
2.177 + for(in_edge_iterator e=G.first_in_edge(w); e.valid(); ++e) {
2.178 + node_iterator v=G.tail(e);
2.179 + /*e is the edge vw.*/
2.180 +
2.181 + if (excess.get(w)==0) break;
2.182 + /*It may happen, that w became inactive in the first 'for' cycle.*/
2.183 +
2.184 + if(flow.get(e)>0) {
2.185 + /*e is an edge of the residual graph */
2.186 +
2.187 + if(level.get(w)==level.get(v)+1) {
2.188 + /*Push is allowed now*/
2.189 +
2.190 + if (flow.get(e) > excess.get(w)) {
2.191 + /*A nonsaturating push.*/
2.192 +
2.193 + if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
2.194 + /*v becomes active.*/
2.195 +
2.196 + flow.put(e, flow.get(e)-excess.get(w));
2.197 + excess.put(v, excess.get(v)+excess.get(w));
2.198 + excess.put(w,0);
2.199 + //std::cout << v << " " << w << " vissza elen nonsat pump " << std::endl;
2.200 + break;
2.201 + } else {
2.202 + /*A saturating push.*/
2.203 +
2.204 + if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
2.205 + /*v becomes active.*/
2.206 +
2.207 + flow.put(e,0);
2.208 + excess.put(v, excess.get(v)+flow.get(e));
2.209 + excess.put(w, excess.get(w)-flow.get(e));
2.210 + //std::cout << v <<" " << w << " vissza elen sat pump " << std::endl;
2.211 + if (excess.get(w)==0) { break;}
2.212 + } //if (flow.get(e) > excess.get(v))
2.213 + } //if(level.get(w)==level.get(v)+1)
2.214 +
2.215 + else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
2.216 + //std::cout << "Leveldecrease of node " << w << " to " << newlevel << std::endl;
2.217 +
2.218 + } //if (flow.get(e)>0)
2.219 +
2.220 + } //for in-edge
2.221 +
2.222 +
2.223 +
2.224 +
2.225 + /*
2.226 + Relabel
2.227 + */
2.228 + if (excess.get(w)>0) {
2.229 + /*Now newlevel <= n*/
2.230 +
2.231 + int l=level.get(w); //l is the old level of w.
2.232 + --numb[l];
2.233 +
2.234 + if (newlevel == n) {
2.235 + level.put(w,n);
2.236 +
2.237 + } else {
2.238 +
2.239 + if (numb[l]) {
2.240 + /*If the level of w remains nonempty.*/
2.241 +
2.242 + level.put(w,++newlevel);
2.243 + ++numb[newlevel];
2.244 + stack[newlevel].push(w);
2.245 + b=newlevel;
2.246 + } else {
2.247 + /*If the level of w gets empty.*/
2.248 +
2.249 + for (each_node_iterator v=G.first_node() ; v.valid() ; ++v) {
2.250 + if (level.get(v) >= l ) {
2.251 + level.put(v,n);
2.252 + }
2.253 + }
2.254 +
2.255 + for (int i=l+1 ; i!=n ; ++i) numb[i]=0;
2.256 + } //if (numb[l])
2.257 +
2.258 + } // if (newlevel = n)
2.259 +
2.260 + } // if (excess.get(w)>0)
2.261 +
2.262 +
2.263 + } //else
2.264 +
2.265 + } //while(b)
2.266 +
2.267 + value=excess.get(t);
2.268 + /*Max flow value.*/
2.269 +
2.270 +
2.271 +
2.272 + /*
2.273 + We find an empty level, e. The nodes above this level give
2.274 + a minimum cut.
2.275 + */
2.276 +
2.277 + int e=1;
2.278 +
2.279 + while(e) {
2.280 + if(numb[e]) ++e;
2.281 + else break;
2.282 + }
2.283 + for (each_node_iterator v=G.first_node(); v.valid(); ++v) {
2.284 + if (level.get(v) > e) mincutvector.put(v, true);
2.285 + }
2.286 +
2.287 +
2.288 + } // void run()
2.289 +
2.290 +
2.291 +
2.292 + /*
2.293 + Returns the maximum value of a flow.
2.294 + */
2.295 +
2.296 + T maxflow() {
2.297 + return value;
2.298 + }
2.299 +
2.300 +
2.301 +
2.302 + /*
2.303 + Returns a minimum cut.
2.304 + */
2.305 +
2.306 + node_property_vector<graph_type, bool> mincut() {
2.307 + return mincutvector;
2.308 + }
2.309 +
2.310 +
2.311 + };
2.312 +}//namespace marci
2.313 +#endif
2.314 +
2.315 +
2.316 +
2.317 +
2.318 +