1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/jacint/flow_test.cc Fri Feb 13 15:12:10 2004 +0000
1.3 @@ -0,0 +1,247 @@
1.4 +#include <iostream>
1.5 +#include <vector>
1.6 +#include <string>
1.7 +
1.8 +#include <marci_list_graph.hh>
1.9 +#include <marci_graph_traits.hh>
1.10 +#include <marci_property_vector.hh>
1.11 +#include <preflow_push_hl.hh>
1.12 +#include <preflow_push_max_flow.hh>
1.13 +#include <reverse_bfs.hh>
1.14 +//#include <dijkstra.hh>
1.15 +
1.16 +using namespace marci;
1.17 +
1.18 +
1.19 +int main (int, char*[])
1.20 +{
1.21 + typedef graph_traits<list_graph>::node_iterator node_iterator;
1.22 + typedef graph_traits<list_graph>::edge_iterator edge_iterator;
1.23 + typedef graph_traits<list_graph>::each_node_iterator each_node_iterator;
1.24 + typedef graph_traits<list_graph>::each_edge_iterator each_edge_iterator;
1.25 + typedef graph_traits<list_graph>::out_edge_iterator out_edge_iterator;
1.26 + typedef graph_traits<list_graph>::in_edge_iterator in_edge_iterator;
1.27 + typedef graph_traits<list_graph>::sym_edge_iterator sym_edge_iterator;
1.28 +
1.29 + list_graph flow_test;
1.30 +
1.31 + //Ahuja könyv példája, maxflowvalue=13
1.32 + node_iterator s=flow_test.add_node();
1.33 + node_iterator v1=flow_test.add_node();
1.34 + node_iterator v2=flow_test.add_node();
1.35 + node_iterator v3=flow_test.add_node();
1.36 + node_iterator v4=flow_test.add_node();
1.37 + node_iterator v5=flow_test.add_node();
1.38 + node_iterator t=flow_test.add_node();
1.39 +
1.40 + node_property_vector<list_graph, std::string> node_name(flow_test);
1.41 + node_name.put(s, "s");
1.42 + node_name.put(v1, "v1");
1.43 + node_name.put(v2, "v2");
1.44 + node_name.put(v3, "v3");
1.45 + node_name.put(v4, "v4");
1.46 + node_name.put(v5, "v5");
1.47 + node_name.put(t, "t");
1.48 +
1.49 + edge_iterator s_v1=flow_test.add_edge(s, v1);
1.50 + edge_iterator s_v2=flow_test.add_edge(s, v2);
1.51 + edge_iterator s_v3=flow_test.add_edge(s, v3);
1.52 + edge_iterator v2_v4=flow_test.add_edge(v2, v4);
1.53 + edge_iterator v2_v5=flow_test.add_edge(v2, v5);
1.54 + edge_iterator v3_v5=flow_test.add_edge(v3, v5);
1.55 + edge_iterator v4_t=flow_test.add_edge(v4, t);
1.56 + edge_iterator v5_t=flow_test.add_edge(v5, t);
1.57 + edge_iterator v2_s=flow_test.add_edge(v2, s);
1.58 +
1.59 + edge_property_vector<list_graph, int> cap(flow_test);
1.60 + cap.put(s_v1, 0);
1.61 + cap.put(s_v2, 10);
1.62 + cap.put(s_v3, 10);
1.63 + cap.put(v2_v4, 5);
1.64 + cap.put(v2_v5, 8);
1.65 + cap.put(v3_v5, 5);
1.66 + cap.put(v4_t, 8);
1.67 + cap.put(v5_t, 8);
1.68 + cap.put(v2_s, 0);
1.69 +
1.70 +
1.71 +
1.72 + //Marci példája, maxflowvalue=23
1.73 + /* node_iterator s=flow_test.add_node();
1.74 + node_iterator v1=flow_test.add_node();
1.75 + node_iterator v2=flow_test.add_node();
1.76 + node_iterator v3=flow_test.add_node();
1.77 + node_iterator v4=flow_test.add_node();
1.78 + node_iterator t=flow_test.add_node();
1.79 + node_iterator w=flow_test.add_node();
1.80 +
1.81 +
1.82 + node_property_vector<list_graph, std::string> node_name(flow_test);
1.83 + node_name.put(s, "s");
1.84 + node_name.put(v1, "v1");
1.85 + node_name.put(v2, "v2");
1.86 + node_name.put(v3, "v3");
1.87 + node_name.put(v4, "v4");
1.88 + node_name.put(t, "t");
1.89 + node_name.put(w, "w");
1.90 +
1.91 + edge_iterator s_v1=flow_test.add_edge(s, v1);
1.92 + edge_iterator s_v2=flow_test.add_edge(s, v2);
1.93 + edge_iterator v1_v2=flow_test.add_edge(v1, v2);
1.94 + edge_iterator v2_v1=flow_test.add_edge(v2, v1);
1.95 + edge_iterator v1_v3=flow_test.add_edge(v1, v3);
1.96 + edge_iterator v3_v2=flow_test.add_edge(v3, v2);
1.97 + edge_iterator v2_v4=flow_test.add_edge(v2, v4);
1.98 + edge_iterator v4_v3=flow_test.add_edge(v4, v3);
1.99 + edge_iterator v3_t=flow_test.add_edge(v3, t);
1.100 + edge_iterator v4_t=flow_test.add_edge(v4, t);
1.101 + edge_iterator v3_v3=flow_test.add_edge(v3, v3);
1.102 + edge_iterator s_w=flow_test.add_edge(s, w);
1.103 + // edge_iterator v2_s=flow_test.add_edge(v2, s);
1.104 +
1.105 +
1.106 +
1.107 + edge_property_vector<list_graph, int> cap(flow_test); //serves as length in dijkstra
1.108 + cap.put(s_v1, 16);
1.109 + cap.put(s_v2, 13);
1.110 + cap.put(v1_v2, 10);
1.111 + cap.put(v2_v1, 4);
1.112 + cap.put(v1_v3, 12);
1.113 + cap.put(v3_v2, 9);
1.114 + cap.put(v2_v4, 14);
1.115 + cap.put(v4_v3, 7);
1.116 + cap.put(v3_t, 20);
1.117 + cap.put(v4_t, 4);
1.118 + cap.put(v3_v3, 4);
1.119 + cap.put(s_w, 4);
1.120 + // cap.put(v2_s, 0);
1.121 +
1.122 +*/
1.123 +
1.124 + //pelda 3, maxflowvalue=4
1.125 + /* node_iterator s=flow_test.add_node();
1.126 + node_iterator v1=flow_test.add_node();
1.127 + node_iterator v2=flow_test.add_node();
1.128 + node_iterator t=flow_test.add_node();
1.129 + node_iterator w=flow_test.add_node();
1.130 +
1.131 + node_property_vector<list_graph, std::string> node_name(flow_test);
1.132 + node_name.put(s, "s");
1.133 + node_name.put(v1, "v1");
1.134 + node_name.put(v2, "v2");
1.135 + node_name.put(t, "t");
1.136 + node_name.put(w, "w");
1.137 +
1.138 + edge_iterator s_v1=flow_test.add_edge(s, v1);
1.139 + edge_iterator v1_v2=flow_test.add_edge(v1, v2);
1.140 + edge_iterator v2_t=flow_test.add_edge(v2, t);
1.141 + edge_iterator v1_v1=flow_test.add_edge(v1, v1);
1.142 + edge_iterator s_w=flow_test.add_edge(s, w);
1.143 +
1.144 +
1.145 + edge_property_vector<list_graph, int> cap(flow_test);
1.146 +
1.147 + cap.put(s_v1, 16);
1.148 + cap.put(v1_v2, 10);
1.149 + cap.put(v2_t, 4);
1.150 + cap.put(v1_v1, 3);
1.151 + cap.put(s_w, 5);
1.152 + */
1.153 +
1.154 +
1.155 +
1.156 + /*
1.157 + std::cout << "Testing reverse_bfs..." << std::endl;
1.158 +
1.159 + reverse_bfs<list_graph> bfs_test(flow_test, t);
1.160 +
1.161 + bfs_test.run();
1.162 +
1.163 + for (each_node_iterator w=flow_test.first_node(); w.valid(); ++w) {
1.164 + std::cout <<"The distance of " << w << " is " << bfs_test.dist(w) <<std::endl;
1.165 + }
1.166 +
1.167 + */
1.168 +
1.169 +
1.170 +
1.171 + std::cout << "Testing preflow_push_hl..." << std::endl;
1.172 +
1.173 + preflow_push_hl<list_graph, int> preflow_push_test(flow_test, s, t, cap);
1.174 +
1.175 + preflow_push_test.run();
1.176 +
1.177 + std::cout << "Maximum flow value is: " << preflow_push_test.maxflow() << "."<<std::endl;
1.178 +
1.179 + std::cout<< "The flow on edge s-v1 is "<< preflow_push_test.flowonedge(s_v1) << "."<<std::endl;
1.180 +
1.181 + edge_property_vector<list_graph, int> flow=preflow_push_test.allflow();
1.182 + for (each_edge_iterator e=flow_test.first_edge(); e.valid(); ++e) {
1.183 + std::cout <<"Flow on edge " << flow_test.tail(e) <<"-" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl;
1.184 + }
1.185 +
1.186 + std::cout << "A minimum cut: " <<std::endl;
1.187 + node_property_vector<list_graph, bool> mincut=preflow_push_test.mincut();
1.188 +
1.189 + for (each_node_iterator v=flow_test.first_node(); v.valid(); ++v) {
1.190 + if (mincut.get(v)) std::cout <<node_name.get(v)<< " ";
1.191 + }
1.192 +
1.193 + std::cout<<"\n\n"<<std::endl;
1.194 +
1.195 +
1.196 +
1.197 +
1.198 + std::cout << "Testing preflow_push_max_flow..." << std::endl;
1.199 +
1.200 + preflow_push_max_flow<list_graph, int> max_flow_test(flow_test, s, t, cap);
1.201 +
1.202 + max_flow_test.run();
1.203 +
1.204 + std::cout << "Maximum flow value is: " << max_flow_test.maxflow() << "."<< std::endl;
1.205 +
1.206 + std::cout << "A minimum cut: " <<std::endl;
1.207 + node_property_vector<list_graph, bool> mincut2=max_flow_test.mincut();
1.208 +
1.209 + for (each_node_iterator v=flow_test.first_node(); v.valid(); ++v) {
1.210 + if (mincut2.get(v)) std::cout <<node_name.get(v)<< " ";
1.211 + }
1.212 +
1.213 + std::cout << std::endl <<std::endl;
1.214 +
1.215 +
1.216 + /*
1.217 + std::cout << "Testing dijkstra..." << std::endl;
1.218 +
1.219 + node_iterator root=v2;
1.220 +
1.221 + dijkstra<list_graph, int> dijkstra_test(flow_test, root, cap);
1.222 +
1.223 + dijkstra_test.run();
1.224 +
1.225 + for (each_node_iterator w=flow_test.first_node(); w.valid(); ++w) {
1.226 + if (dijkstra_test.reach(w)) {
1.227 + std::cout <<"The distance of " << w << " is " << dijkstra_test.dist(w);
1.228 + if (dijkstra_test.pred(w).valid()) {
1.229 + std::cout <<", a shortest path from the root ends with edge " << dijkstra_test.pred(w) <<std::endl;
1.230 + } else {
1.231 + std::cout <<", this is the root."<<std::endl; }
1.232 +
1.233 + } else {
1.234 + cout << w << " is not reachable from " << root <<std::endl;
1.235 + }
1.236 + }
1.237 +
1.238 + */
1.239 +
1.240 + return 0;
1.241 +}
1.242 +
1.243 +
1.244 +
1.245 +
1.246 +
1.247 +
1.248 +
1.249 +
1.250 +
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/jacint/makefile Fri Feb 13 15:12:10 2004 +0000
2.3 @@ -0,0 +1,5 @@
2.4 +BINARIES = flow_test
2.5 +
2.6 +include ../makefile
2.7 +
2.8 +CXXFLAGS := $(CXXFLAGS) -I.. -I../../include
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/work/jacint/preflow_push_hl.h Fri Feb 13 15:12:10 2004 +0000
3.3 @@ -0,0 +1,321 @@
3.4 +// -*- C++ -*-
3.5 +/*
3.6 +preflow_push_hl.hh
3.7 +by jacint.
3.8 +Runs the highest label variant of the preflow push algorithm with
3.9 +running time O(n^2\sqrt(m)).
3.10 +
3.11 +Member functions:
3.12 +
3.13 +void run() : runs the algorithm
3.14 +
3.15 + The following functions should be used after run() was already run.
3.16 +
3.17 +T maxflow() : returns the value of a maximum flow
3.18 +
3.19 +T flowonEdge(Edge_iterator e) : for a fixed maximum flow x it returns x(e)
3.20 +
3.21 +EdgeMap<graph_type, T> allflow() : returns the fixed maximum flow x
3.22 +
3.23 +NodeMap<graph_type, bool> mincut() : returns a
3.24 + characteristic vector of a minimum cut. (An empty level
3.25 + in the algorithm gives a minimum cut.)
3.26 +*/
3.27 +
3.28 +#ifndef PREFLOW_PUSH_HL_H
3.29 +#define PREFLOW_PUSH_HL_H
3.30 +
3.31 +#include <algorithm>
3.32 +#include <vector>
3.33 +#include <stack>
3.34 +
3.35 +#include <reverse_bfs.hh>
3.36 +
3.37 +namespace marci {
3.38 +
3.39 + template <typename Graph, typename T, typename FlowMap, typename CapacityMap>
3.40 + class preflow_push_hl {
3.41 +
3.42 + typedef typename Graph::NodeIt NodeIt;
3.43 + typedef typename Graph::EdgeIt EdgeIt;
3.44 + typedef typename Graph::EachNodeIt EachNodeIt;
3.45 + typedef typename Graph::OutEdgeIt OutEdgeIt;
3.46 + typedef typename Graph::InEdgeIt InEdgeIt;
3.47 + typedef typename Graph::EachEdgeIt EachEdgeIt;
3.48 +
3.49 +
3.50 + Graph& G;
3.51 + NodeIt s;
3.52 + NodeIt t;
3.53 + Graph::EdgeMap<T> flow;
3.54 + Graph::EdgeMap<T> capacity;
3.55 + T value;
3.56 + Graph::NodeMap<bool> mincutvector;
3.57 +
3.58 +
3.59 + public:
3.60 +
3.61 + preflow_push_hl(Graph& _G, NodeIt _s, NodeIt _t,
3.62 + Graph::EdgeMap<T>& _capacity) :
3.63 + G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), mincutvector(_G, true) { }
3.64 +
3.65 +
3.66 +
3.67 +
3.68 + /*
3.69 + The run() function runs the highest label preflow-push,
3.70 + running time: O(n^2\sqrt(m))
3.71 + */
3.72 + void run() {
3.73 +
3.74 + Graph::NodeMap<int> level(G); //level of Node
3.75 + Graph::NodeMap<T> excess(G); //excess of Node
3.76 +
3.77 + int n=G.nodeNum(); //number of Nodes
3.78 + int b=n;
3.79 + /*b is a bound on the highest level of an active Node. In the beginning it is at most n-2.*/
3.80 +
3.81 + std::vector<std::stack<NodeIt> > stack(2*n-1); //Stack of the active Nodes in level i.
3.82 +
3.83 +
3.84 +
3.85 +
3.86 + /*Reverse_bfs from t, to find the starting level.*/
3.87 +
3.88 + reverse_bfs<list_graph> bfs(G, t);
3.89 + bfs.run();
3.90 + for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) {
3.91 + level.set(v, bfs.dist(v));
3.92 + //std::cout << "the level of " << v << " is " << bfs.dist(v);
3.93 + }
3.94 +
3.95 + /*The level of s is fixed to n*/
3.96 + level.set(s,n);
3.97 +
3.98 +
3.99 +
3.100 +
3.101 +
3.102 + /* Starting flow. It is everywhere 0 at the moment. */
3.103 +
3.104 + for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i)
3.105 + {
3.106 + NodeIt w=G.head(i);
3.107 + flow.set(i, capacity.get(i));
3.108 + stack[bfs.dist(w)].push(w);
3.109 + excess.set(w, capacity.get(i));
3.110 + }
3.111 +
3.112 +
3.113 + /*
3.114 + End of preprocessing
3.115 + */
3.116 +
3.117 +
3.118 +
3.119 + /*
3.120 + Push/relabel on the highest level active Nodes.
3.121 + */
3.122 +
3.123 + /*While there exists active Node.*/
3.124 + while (b) {
3.125 +
3.126 + /*We decrease the bound if there is no active Node of level b.*/
3.127 + if (stack[b].empty()) {
3.128 + --b;
3.129 + } else {
3.130 +
3.131 + NodeIt w=stack[b].top(); //w is the highest label active Node.
3.132 + stack[b].pop(); //We delete w from the stack.
3.133 +
3.134 + int newlevel=2*n-2; //In newlevel we maintain the next level of w.
3.135 +
3.136 + for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
3.137 + NodeIt v=G.head(e);
3.138 + /*e is the Edge wv.*/
3.139 +
3.140 + if (flow.get(e)<capacity.get(e)) {
3.141 + /*e is an Edge of the residual graph */
3.142 +
3.143 + if(level.get(w)==level.get(v)+1) {
3.144 + /*Push is allowed now*/
3.145 +
3.146 + if (capacity.get(e)-flow.get(e) > excess.get(w)) {
3.147 + /*A nonsaturating push.*/
3.148 +
3.149 + if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
3.150 + /*v becomes active.*/
3.151 +
3.152 + flow.set(e, flow.get(e)+excess.get(w));
3.153 + excess.set(v, excess.get(v)+excess.get(w));
3.154 + excess.set(w,0);
3.155 + //std::cout << w << " " << v <<" elore elen nonsat pump " << std::endl;
3.156 + break;
3.157 + } else {
3.158 + /*A saturating push.*/
3.159 +
3.160 + if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
3.161 + /*v becomes active.*/
3.162 +
3.163 + excess.set(v, excess.get(v)+capacity.get(e)-flow.get(e));
3.164 + excess.set(w, excess.get(w)-capacity.get(e)+flow.get(e));
3.165 + flow.set(e, capacity.get(e));
3.166 + //std::cout << w<<" " <<v<<" elore elen sat pump " << std::endl;
3.167 + if (excess.get(w)==0) break;
3.168 + /*If w is not active any more, then we go on to the next Node.*/
3.169 +
3.170 + } // if (capacity.get(e)-flow.get(e) > excess.get(w))
3.171 + } // if(level.get(w)==level.get(v)+1)
3.172 +
3.173 + else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
3.174 +
3.175 + } //if (flow.get(e)<capacity.get(e))
3.176 +
3.177 + } //for(OutEdgeIt e=G.first_OutEdge(w); e.valid(); ++e)
3.178 +
3.179 +
3.180 +
3.181 + for(InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
3.182 + NodeIt v=G.tail(e);
3.183 + /*e is the Edge vw.*/
3.184 +
3.185 + if (excess.get(w)==0) break;
3.186 + /*It may happen, that w became inactive in the first for cycle.*/
3.187 + if(flow.get(e)>0) {
3.188 + /*e is an Edge of the residual graph */
3.189 +
3.190 + if(level.get(w)==level.get(v)+1) {
3.191 + /*Push is allowed now*/
3.192 +
3.193 + if (flow.get(e) > excess.get(w)) {
3.194 + /*A nonsaturating push.*/
3.195 +
3.196 + if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
3.197 + /*v becomes active.*/
3.198 +
3.199 + flow.set(e, flow.get(e)-excess.get(w));
3.200 + excess.set(v, excess.get(v)+excess.get(w));
3.201 + excess.set(w,0);
3.202 + //std::cout << v << " " << w << " vissza elen nonsat pump " << std::endl;
3.203 + break;
3.204 + } else {
3.205 + /*A saturating push.*/
3.206 +
3.207 + if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
3.208 + /*v becomes active.*/
3.209 +
3.210 + excess.set(v, excess.get(v)+flow.get(e));
3.211 + excess.set(w, excess.get(w)-flow.get(e));
3.212 + flow.set(e,0);
3.213 + //std::cout << v <<" " << w << " vissza elen sat pump " << std::endl;
3.214 + if (excess.get(w)==0) { break;}
3.215 + } //if (flow.get(e) > excess.get(v))
3.216 + } //if(level.get(w)==level.get(v)+1)
3.217 +
3.218 + else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
3.219 +
3.220 +
3.221 + } //if (flow.get(e)>0)
3.222 +
3.223 + } //for
3.224 +
3.225 +
3.226 + if (excess.get(w)>0) {
3.227 + level.set(w,++newlevel);
3.228 + stack[newlevel].push(w);
3.229 + b=newlevel;
3.230 + //std::cout << "The new level of " << w << " is "<< newlevel <<std::endl;
3.231 + }
3.232 +
3.233 +
3.234 + } //else
3.235 +
3.236 + } //while(b)
3.237 +
3.238 + value = excess.get(t);
3.239 + /*Max flow value.*/
3.240 +
3.241 +
3.242 +
3.243 +
3.244 + } //void run()
3.245 +
3.246 +
3.247 +
3.248 +
3.249 +
3.250 + /*
3.251 + Returns the maximum value of a flow.
3.252 + */
3.253 +
3.254 + T maxflow() {
3.255 + return value;
3.256 + }
3.257 +
3.258 +
3.259 +
3.260 + /*
3.261 + For the maximum flow x found by the algorithm, it returns the flow value on Edge e, i.e. x(e).
3.262 + */
3.263 +
3.264 + T flowonEdge(EdgeIt e) {
3.265 + return flow.get(e);
3.266 + }
3.267 +
3.268 +
3.269 +
3.270 + /*
3.271 + Returns the maximum flow x found by the algorithm.
3.272 + */
3.273 +
3.274 + EdgeMap<graph_type, T> allflow() {
3.275 + return flow;
3.276 + }
3.277 +
3.278 +
3.279 +
3.280 + /*
3.281 + Returns a minimum cut by using a reverse bfs from t in the residual graph.
3.282 + */
3.283 +
3.284 + NodeMap<graph_type, bool> mincut() {
3.285 +
3.286 + std::queue<NodeIt> queue;
3.287 +
3.288 + mincutvector.set(t,false);
3.289 + queue.push(t);
3.290 +
3.291 + while (!queue.empty()) {
3.292 + NodeIt w=queue.front();
3.293 + queue.pop();
3.294 +
3.295 + for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
3.296 + NodeIt v=G.tail(e);
3.297 + if (mincutvector.get(v) && flow.get(e) < capacity.get(e) ) {
3.298 + queue.push(v);
3.299 + mincutvector.set(v, false);
3.300 + }
3.301 + } // for
3.302 +
3.303 + for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
3.304 + NodeIt v=G.head(e);
3.305 + if (mincutvector.get(v) && flow.get(e) > 0 ) {
3.306 + queue.push(v);
3.307 + mincutvector.set(v, false);
3.308 + }
3.309 + } // for
3.310 +
3.311 + }
3.312 +
3.313 + return mincutvector;
3.314 +
3.315 + }
3.316 +
3.317 +
3.318 + };
3.319 +}//namespace marci
3.320 +#endif
3.321 +
3.322 +
3.323 +
3.324 +