1.1 --- a/src/work/jacint/dimacs_jgraph.hh Mon Mar 01 17:24:34 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,61 +0,0 @@
1.4 -#ifndef DIMACS_HH
1.5 -#define DIMACS_HH
1.6 -
1.7 -#include <iostream>
1.8 -#include <string>
1.9 -#include <vector>
1.10 -
1.11 -namespace hugo {
1.12 -
1.13 - template<typename Graph, typename CapacityMap>
1.14 - void readDimacsMaxFlow(std::istream& is, Graph &G, typename Graph::TrivNodeIt &s, typename Graph::TrivNodeIt &t, CapacityMap& capacity) {
1.15 - G.clear();
1.16 - int cap;
1.17 - char d;
1.18 - std::string problem;
1.19 - char c;
1.20 - int i, j;
1.21 - std::string str;
1.22 - int n, m;
1.23 - std::vector<typename Graph::TrivNodeIt> nodes;
1.24 - while (is>>c) {
1.25 - switch (c) {
1.26 - case 'c': //comment
1.27 - getline(is, str);
1.28 - break;
1.29 - case 't': //type
1.30 - getline(is, str);
1.31 - break;
1.32 - case 'p': //problem definition
1.33 - is >> problem >> n >> m;
1.34 - getline(is, str);
1.35 - nodes.resize(n+1);
1.36 - for (int k=1; k<=n; ++k) nodes[k]=G.addNode();
1.37 - break;
1.38 - case 'n': //node definition
1.39 - if (problem=="sp") { //shortest path problem
1.40 - is >> i;
1.41 - getline(is, str);
1.42 - s=nodes[i];
1.43 - }
1.44 - if (problem=="max") { //max flow problem
1.45 - is >> i >> d;
1.46 - getline(is, str);
1.47 - if (d=='s') s=nodes[i];
1.48 - if (d=='t') t=nodes[i];
1.49 - }
1.50 - break;
1.51 - case 'a':
1.52 - is >> i >> j >> cap;
1.53 - getline(is, str);
1.54 - typename Graph::TrivEdgeIt e=G.addEdge(nodes[i], nodes[j]);
1.55 - capacity.update();
1.56 - capacity.set(e, cap);
1.57 - break;
1.58 - }
1.59 - }
1.60 - }
1.61 -
1.62 -} //namespace marci
1.63 -
1.64 -#endif //DIMACS_HH
2.1 --- a/src/work/jacint/flow_test.cc Mon Mar 01 17:24:34 2004 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,244 +0,0 @@
2.4 -#include <iostream>
2.5 -#include <vector>
2.6 -#include <string>
2.7 -
2.8 -#include <list_graph.hh>
2.9 -#include <preflow_push_hl.h>
2.10 -#include <preflow_push_max_flow.h>
2.11 -#include <reverse_bfs.h>
2.12 -//#include <dijkstra.h>
2.13 -
2.14 -using namespace hugo;
2.15 -
2.16 -
2.17 -int main (int, char*[])
2.18 -{
2.19 - typedef ListGraph::NodeIt NodeIt;
2.20 - typedef ListGraph::EdgeIt EdgeIt;
2.21 - typedef ListGraph::EachNodeIt EachNodeIt;
2.22 - typedef ListGraph::EachEdgeIt EachEdgeIt;
2.23 - typedef ListGraph::OutEdgeIt OutEdgeIt;
2.24 - typedef ListGraph::InEdgeIt InEdgeIt;
2.25 -
2.26 - ListGraph flow_test;
2.27 -
2.28 - //Ahuja könyv példája, maxflowvalue=13
2.29 - NodeIt s=flow_test.addNode();
2.30 - NodeIt v1=flow_test.addNode();
2.31 - NodeIt v2=flow_test.addNode();
2.32 - NodeIt v3=flow_test.addNode();
2.33 - NodeIt v4=flow_test.addNode();
2.34 - NodeIt v5=flow_test.addNode();
2.35 - NodeIt t=flow_test.addNode();
2.36 -
2.37 - ListGraph::NodeMap<std::string> Node_name(flow_test);
2.38 - Node_name.set(s, "s");
2.39 - Node_name.set(v1, "v1");
2.40 - Node_name.set(v2, "v2");
2.41 - Node_name.set(v3, "v3");
2.42 - Node_name.set(v4, "v4");
2.43 - Node_name.set(v5, "v5");
2.44 - Node_name.set(t, "t");
2.45 -
2.46 - EdgeIt s_v1=flow_test.addEdge(s, v1);
2.47 - EdgeIt s_v2=flow_test.addEdge(s, v2);
2.48 - EdgeIt s_v3=flow_test.addEdge(s, v3);
2.49 - EdgeIt v2_v4=flow_test.addEdge(v2, v4);
2.50 - EdgeIt v2_v5=flow_test.addEdge(v2, v5);
2.51 - EdgeIt v3_v5=flow_test.addEdge(v3, v5);
2.52 - EdgeIt v4_t=flow_test.addEdge(v4, t);
2.53 - EdgeIt v5_t=flow_test.addEdge(v5, t);
2.54 - EdgeIt v2_s=flow_test.addEdge(v2, s);
2.55 -
2.56 - ListGraph::EdgeMap<int> cap(flow_test);
2.57 - cap.set(s_v1, 0);
2.58 - cap.set(s_v2, 10);
2.59 - cap.set(s_v3, 10);
2.60 - cap.set(v2_v4, 5);
2.61 - cap.set(v2_v5, 8);
2.62 - cap.set(v3_v5, 5);
2.63 - cap.set(v4_t, 8);
2.64 - cap.set(v5_t, 8);
2.65 - cap.set(v2_s, 0);
2.66 -
2.67 -
2.68 -
2.69 - //Marci példája, maxflowvalue=23
2.70 - /* NodeIt s=flow_test.addNode();
2.71 - NodeIt v1=flow_test.addNode();
2.72 - NodeIt v2=flow_test.addNode();
2.73 - NodeIt v3=flow_test.addNode();
2.74 - NodeIt v4=flow_test.addNode();
2.75 - NodeIt t=flow_test.addNode();
2.76 - NodeIt w=flow_test.addNode();
2.77 -
2.78 -
2.79 - NodeMap<ListGraph, std::string> Node_name(flow_test);
2.80 - Node_name.set(s, "s");
2.81 - Node_name.set(v1, "v1");
2.82 - Node_name.set(v2, "v2");
2.83 - Node_name.set(v3, "v3");
2.84 - Node_name.set(v4, "v4");
2.85 - Node_name.set(t, "t");
2.86 - Node_name.set(w, "w");
2.87 -
2.88 - EdgeIt s_v1=flow_test.addEdge(s, v1);
2.89 - EdgeIt s_v2=flow_test.addEdge(s, v2);
2.90 - EdgeIt v1_v2=flow_test.addEdge(v1, v2);
2.91 - EdgeIt v2_v1=flow_test.addEdge(v2, v1);
2.92 - EdgeIt v1_v3=flow_test.addEdge(v1, v3);
2.93 - EdgeIt v3_v2=flow_test.addEdge(v3, v2);
2.94 - EdgeIt v2_v4=flow_test.addEdge(v2, v4);
2.95 - EdgeIt v4_v3=flow_test.addEdge(v4, v3);
2.96 - EdgeIt v3_t=flow_test.addEdge(v3, t);
2.97 - EdgeIt v4_t=flow_test.addEdge(v4, t);
2.98 - EdgeIt v3_v3=flow_test.addEdge(v3, v3);
2.99 - EdgeIt s_w=flow_test.addEdge(s, w);
2.100 - // EdgeIt v2_s=flow_test.addEdge(v2, s);
2.101 -
2.102 -
2.103 -
2.104 - EdgeMap<ListGraph, int> cap(flow_test); //serves as length in dijkstra
2.105 - cap.set(s_v1, 16);
2.106 - cap.set(s_v2, 13);
2.107 - cap.set(v1_v2, 10);
2.108 - cap.set(v2_v1, 4);
2.109 - cap.set(v1_v3, 12);
2.110 - cap.set(v3_v2, 9);
2.111 - cap.set(v2_v4, 14);
2.112 - cap.set(v4_v3, 7);
2.113 - cap.set(v3_t, 20);
2.114 - cap.set(v4_t, 4);
2.115 - cap.set(v3_v3, 4);
2.116 - cap.set(s_w, 4);
2.117 - // cap.set(v2_s, 0);
2.118 -
2.119 -*/
2.120 -
2.121 - //pelda 3, maxflowvalue=4
2.122 - /* NodeIt s=flow_test.addNode();
2.123 - NodeIt v1=flow_test.addNode();
2.124 - NodeIt v2=flow_test.addNode();
2.125 - NodeIt t=flow_test.addNode();
2.126 - NodeIt w=flow_test.addNode();
2.127 -
2.128 - NodeMap<ListGraph, std::string> Node_name(flow_test);
2.129 - Node_name.set(s, "s");
2.130 - Node_name.set(v1, "v1");
2.131 - Node_name.set(v2, "v2");
2.132 - Node_name.set(t, "t");
2.133 - Node_name.set(w, "w");
2.134 -
2.135 - EdgeIt s_v1=flow_test.addEdge(s, v1);
2.136 - EdgeIt v1_v2=flow_test.addEdge(v1, v2);
2.137 - EdgeIt v2_t=flow_test.addEdge(v2, t);
2.138 - EdgeIt v1_v1=flow_test.addEdge(v1, v1);
2.139 - EdgeIt s_w=flow_test.addEdge(s, w);
2.140 -
2.141 -
2.142 - EdgeMap<ListGraph, int> cap(flow_test);
2.143 -
2.144 - cap.set(s_v1, 16);
2.145 - cap.set(v1_v2, 10);
2.146 - cap.set(v2_t, 4);
2.147 - cap.set(v1_v1, 3);
2.148 - cap.set(s_w, 5);
2.149 - */
2.150 -
2.151 -
2.152 -
2.153 - /*
2.154 - std::cout << "Testing reverse_bfs..." << std::endl;
2.155 -
2.156 - reverse_bfs<ListGraph> bfs_test(flow_test, t);
2.157 -
2.158 - bfs_test.run();
2.159 -
2.160 - for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) {
2.161 - std::cout <<"The distance of " << w << " is " << bfs_test.dist(w) <<std::endl;
2.162 - }
2.163 -
2.164 - */
2.165 -
2.166 -
2.167 -
2.168 - std::cout << "Testing preflow_push_hl..." << std::endl;
2.169 -
2.170 - preflow_push_hl<ListGraph, int> preflow_push_test(flow_test, s, t, cap);
2.171 -
2.172 - preflow_push_test.run();
2.173 -
2.174 - std::cout << "Maximum flow value is: " << preflow_push_test.maxflow() << "."<<std::endl;
2.175 -
2.176 - std::cout<< "The flow on Edge s-v1 is "<< preflow_push_test.flowonEdge(s_v1) << "."<<std::endl;
2.177 -
2.178 - ListGraph::EdgeMap<int> flow=preflow_push_test.allflow();
2.179 - for (EachEdgeIt e=flow_test.template first<EachEdgeIt>(); e.valid(); ++e) {
2.180 - std::cout <<"Flow on Edge " << flow_test.tail(e) <<"-" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl;
2.181 - }
2.182 -
2.183 - std::cout << "A minimum cut: " <<std::endl;
2.184 - ListGraph::NodeMap<bool> mincut=preflow_push_test.mincut();
2.185 -
2.186 - for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) {
2.187 - if (mincut.get(v)) std::cout <<Node_name.get(v)<< " ";
2.188 - }
2.189 -
2.190 - std::cout<<"\n\n"<<std::endl;
2.191 -
2.192 -
2.193 -
2.194 -
2.195 - std::cout << "Testing preflow_push_max_flow..." << std::endl;
2.196 -
2.197 - preflow_push_max_flow<ListGraph, int> max_flow_test(flow_test, s, t, cap);
2.198 -
2.199 - max_flow_test.run();
2.200 -
2.201 - std::cout << "Maximum flow value is: " << max_flow_test.maxflow() << "."<< std::endl;
2.202 -
2.203 - std::cout << "A minimum cut: " <<std::endl;
2.204 - ListGraph::NodeMap<bool> mincut2=max_flow_test.mincut();
2.205 -
2.206 - for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) {
2.207 - if (mincut2.get(v)) std::cout <<Node_name.get(v)<< " ";
2.208 - }
2.209 -
2.210 - std::cout << std::endl <<std::endl;
2.211 -
2.212 -
2.213 - /*
2.214 - std::cout << "Testing dijkstra..." << std::endl;
2.215 -
2.216 - NodeIt root=v2;
2.217 -
2.218 - dijkstra<ListGraph, int> dijkstra_test(flow_test, root, cap);
2.219 -
2.220 - dijkstra_test.run();
2.221 -
2.222 - for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) {
2.223 - if (dijkstra_test.reach(w)) {
2.224 - std::cout <<"The distance of " << w << " is " << dijkstra_test.dist(w);
2.225 - if (dijkstra_test.pred(w).valid()) {
2.226 - std::cout <<", a shortest path from the root ends with Edge " << dijkstra_test.pred(w) <<std::endl;
2.227 - } else {
2.228 - std::cout <<", this is the root."<<std::endl; }
2.229 -
2.230 - } else {
2.231 - cout << w << " is not reachable from " << root <<std::endl;
2.232 - }
2.233 - }
2.234 -
2.235 - */
2.236 -
2.237 - return 0;
2.238 -}
2.239 -
2.240 -
2.241 -
2.242 -
2.243 -
2.244 -
2.245 -
2.246 -
2.247 -
3.1 --- a/src/work/jacint/preflow_aug.h Mon Mar 01 17:24:34 2004 +0000
3.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
3.3 @@ -1,588 +0,0 @@
3.4 -// -*- C++ -*-
3.5 -
3.6 -//hogy kell azt megcsinalni hogy a konstruktorban a FlowMap-nek legyen default erteke (a 0 map)
3.7 -
3.8 -/*
3.9 -preflow_aug.h
3.10 -by jacint.
3.11 -
3.12 -The same as preflow.h, the only difference is that here
3.13 -we start from a given flow.
3.14 -
3.15 -
3.16 -The constructor runs the algorithm:
3.17 -
3.18 -template <typename Graph, typename T,
3.19 - typename Graph_EdgeMap_T_1=typename Graph::EdgeMap<T>,
3.20 - typename Graph_EdgeMap_T_2=typename Graph::EdgeMap<T> >
3.21 -PreflowAug(Graph G, G_NodeIt s, G_NodeIt t, G_EdgeMap_T_1 capacity,
3.22 - G_EdgeMap_T_2 flow, bool flow_type)
3.23 -
3.24 -'capacity' must be non-negative, if flow_type=0 then
3.25 -'flow' must be a flow, otherwise it must be a preflow.
3.26 -
3.27 -
3.28 -Members:
3.29 -
3.30 -T maxFlow() : returns the value of a maximum flow
3.31 -
3.32 -T flow(G_EdgeIt e) : for a fixed maximum flow x it returns x(e)
3.33 -
3.34 -G_EdgeMap_T_2 flow() : returns the fixed maximum flow x
3.35 -
3.36 -void minMinCut(G_NodeMap_bool& M) :
3.37 - sets M to the characteristic vector of the
3.38 - minimum min cut. M must be initialized to false.
3.39 -
3.40 -void maxMinCut(G_NodeMap_bool& M) :
3.41 - sets M to the characteristic vector of the
3.42 - maximum min cut. M must be initialized to false.
3.43 -
3.44 -void minCut(G_NodeMap_bool& M) :
3.45 - sets M to the characteristic vector of a
3.46 - min cut. M must be initialized to false.
3.47 -*/
3.48 -
3.49 -#ifndef PREFLOW_H
3.50 -#define PREFLOW_H
3.51 -
3.52 -#define H0 20
3.53 -#define H1 1
3.54 -
3.55 -#include <vector>
3.56 -#include <queue>
3.57 -
3.58 -#include <iostream> //for error handling
3.59 -
3.60 -#include <time_measure.h>
3.61 -
3.62 -namespace hugo {
3.63 -
3.64 - template <typename Graph, typename T,
3.65 - typename CapMap=typename Graph::EdgeMap<T>,
3.66 - typename FlowMap=typename Graph::EdgeMap<T> >
3.67 - class PreflowAug {
3.68 -
3.69 - typedef typename Graph::NodeIt NodeIt;
3.70 - typedef typename Graph::EdgeIt EdgeIt;
3.71 - typedef typename Graph::EachNodeIt EachNodeIt;
3.72 - typedef typename Graph::EachEdgeIt EachEdgeIt;
3.73 - typedef typename Graph::OutEdgeIt OutEdgeIt;
3.74 - typedef typename Graph::InEdgeIt InEdgeIt;
3.75 -
3.76 - Graph& G;
3.77 - NodeIt s;
3.78 - NodeIt t;
3.79 - CapMap& capacity;
3.80 - FlowMap& _flow;
3.81 - bool flow_type;
3.82 - T value;
3.83 -
3.84 - public:
3.85 - double time;
3.86 - PreflowAug(Graph& _G, NodeIt _s, NodeIt _t,
3.87 - CapMap& _capacity, FlowMap& __flow, bool _flow_type ) :
3.88 - G(_G), s(_s), t(_t), capacity(_capacity), _flow(__flow),
3.89 - flow_type(_flow_type)
3.90 - {
3.91 -
3.92 -
3.93 - bool phase=0; //phase 0 is the 1st phase, phase 1 is the 2nd
3.94 - int n=G.nodeNum();
3.95 - int heur0=(int)(H0*n); //time while running 'bound decrease'
3.96 - int heur1=(int)(H1*n); //time while running 'highest label'
3.97 - int heur=heur1; //starting time interval (#of relabels)
3.98 - bool what_heur=1;
3.99 - /*
3.100 - what_heur is 0 in case 'bound decrease'
3.101 - and 1 in case 'highest label'
3.102 - */
3.103 - bool end=false;
3.104 - /*
3.105 - Needed for 'bound decrease', 'true'
3.106 - means no active nodes are above bound b.
3.107 - */
3.108 - int relabel=0;
3.109 - int k=n-2; //bound on the highest level under n containing a node
3.110 - int b=k; //bound on the highest level under n of an active node
3.111 -
3.112 - typename Graph::NodeMap<int> level(G,n);
3.113 - typename Graph::NodeMap<T> excess(G);
3.114 -
3.115 - std::vector<NodeIt> active(n);
3.116 - typename Graph::NodeMap<NodeIt> next(G);
3.117 - //Stack of the active nodes in level i < n.
3.118 - //We use it in both phases.
3.119 -
3.120 - typename Graph::NodeMap<NodeIt> left(G);
3.121 - typename Graph::NodeMap<NodeIt> right(G);
3.122 - std::vector<NodeIt> level_list(n);
3.123 - /*
3.124 - List of the nodes in level i<n.
3.125 - */
3.126 -
3.127 - /*Reverse_bfs from t, to find the starting level.*/
3.128 - level.set(t,0);
3.129 - std::queue<NodeIt> bfs_queue;
3.130 - bfs_queue.push(t);
3.131 -
3.132 -
3.133 - while (!bfs_queue.empty()) {
3.134 -
3.135 - NodeIt v=bfs_queue.front();
3.136 - bfs_queue.pop();
3.137 - int l=level.get(v)+1;
3.138 -
3.139 - for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
3.140 - if ( capacity.get(e) == _flow.get(e) ) continue;
3.141 - NodeIt w=G.tail(e);
3.142 - if ( level.get(w) == n && w != s ) {
3.143 - bfs_queue.push(w);
3.144 - NodeIt first=level_list[l];
3.145 - if ( first.valid() ) left.set(first,w);
3.146 - right.set(w,first);
3.147 - level_list[l]=w;
3.148 - level.set(w, l);
3.149 - }
3.150 - }
3.151 -
3.152 - for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) {
3.153 - if ( 0 == _flow.get(e) ) continue;
3.154 - NodeIt w=G.head(e);
3.155 - if ( level.get(w) == n && w != s ) {
3.156 - bfs_queue.push(w);
3.157 - NodeIt first=level_list[l];
3.158 - if ( first != 0 ) left.set(first,w);
3.159 - right.set(w,first);
3.160 - level_list[l]=w;
3.161 - level.set(w, l);
3.162 - }
3.163 - }
3.164 - }
3.165 -
3.166 - level.set(s,n);
3.167 -
3.168 -
3.169 -
3.170 - /*The starting excess.*/
3.171 - if ( flow_type ) {
3.172 - for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
3.173 - if ( _flow.get(e) > 0 ) {
3.174 - T flo=_flow.get(e);
3.175 - NodeIt u=G.tail(e);
3.176 - NodeIt v=G.head(e);
3.177 - excess.set(u, excess.get(u)-flo);
3.178 - excess.set(v, excess.get(v)+flo);
3.179 - }
3.180 - }
3.181 -
3.182 - for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) {
3.183 - if ( excess.get(v) < 0 ) {
3.184 - std::cerr<<"It is not a pre_flow."<<std::endl;
3.185 - exit(1);
3.186 - } else {
3.187 - next.set(v,active[level.get(v)]);
3.188 - active[level.get(v)]=v;}
3.189 - }
3.190 - }
3.191 -
3.192 -
3.193 - /* Starting flow. It is everywhere 0 at the moment. */
3.194 - for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e)
3.195 - {
3.196 - T c=capacity.get(e)-_flow.get(e);
3.197 - if ( c == 0 ) continue;
3.198 - NodeIt w=G.head(e);
3.199 - if ( level.get(w) < n ) {
3.200 - if ( excess.get(w) == 0 && w!=t ) {
3.201 - next.set(w,active[level.get(w)]);
3.202 - active[level.get(w)]=w;
3.203 - }
3.204 - _flow.set(e, capacity.get(e));
3.205 - excess.set(w, excess.get(w)+c);
3.206 - }
3.207 - }
3.208 -
3.209 - /*
3.210 - End of preprocessing
3.211 - */
3.212 -
3.213 -
3.214 -
3.215 - /*
3.216 - Push/relabel on the highest level active nodes.
3.217 - */
3.218 - while ( true ) {
3.219 -
3.220 - if ( b == 0 ) {
3.221 - if ( phase ) break;
3.222 -
3.223 - if ( !what_heur && !end && k > 0 ) {
3.224 - b=k;
3.225 - end=true;
3.226 - } else {
3.227 - phase=1;
3.228 - time=currTime();
3.229 - level.set(s,0);
3.230 - std::queue<NodeIt> bfs_queue;
3.231 - bfs_queue.push(s);
3.232 -
3.233 - while (!bfs_queue.empty()) {
3.234 -
3.235 - NodeIt v=bfs_queue.front();
3.236 - bfs_queue.pop();
3.237 - int l=level.get(v)+1;
3.238 -
3.239 - for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
3.240 - if ( capacity.get(e) == _flow.get(e) ) continue;
3.241 - NodeIt u=G.tail(e);
3.242 - if ( level.get(u) >= n ) {
3.243 - bfs_queue.push(u);
3.244 - level.set(u, l);
3.245 - if ( excess.get(u) > 0 ) {
3.246 - next.set(u,active[l]);
3.247 - active[l]=u;
3.248 - }
3.249 - }
3.250 - }
3.251 -
3.252 - for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) {
3.253 - if ( 0 == _flow.get(e) ) continue;
3.254 - NodeIt u=G.head(e);
3.255 - if ( level.get(u) >= n ) {
3.256 - bfs_queue.push(u);
3.257 - level.set(u, l);
3.258 - if ( excess.get(u) > 0 ) {
3.259 - next.set(u,active[l]);
3.260 - active[l]=u;
3.261 - }
3.262 - }
3.263 - }
3.264 - }
3.265 - b=n-2;
3.266 - }
3.267 -
3.268 - }
3.269 -
3.270 -
3.271 - if ( active[b] == 0 ) --b;
3.272 - else {
3.273 - end=false;
3.274 -
3.275 - NodeIt w=active[b];
3.276 - active[b]=next.get(w);
3.277 - int lev=level.get(w);
3.278 - T exc=excess.get(w);
3.279 - int newlevel=n; //bound on the next level of w
3.280 -
3.281 - for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
3.282 -
3.283 - if ( _flow.get(e) == capacity.get(e) ) continue;
3.284 - NodeIt v=G.head(e);
3.285 - //e=wv
3.286 -
3.287 - if( lev > level.get(v) ) {
3.288 - /*Push is allowed now*/
3.289 -
3.290 - if ( excess.get(v)==0 && v!=t && v!=s ) {
3.291 - int lev_v=level.get(v);
3.292 - next.set(v,active[lev_v]);
3.293 - active[lev_v]=v;
3.294 - }
3.295 -
3.296 - T cap=capacity.get(e);
3.297 - T flo=_flow.get(e);
3.298 - T remcap=cap-flo;
3.299 -
3.300 - if ( remcap >= exc ) {
3.301 - /*A nonsaturating push.*/
3.302 -
3.303 - _flow.set(e, flo+exc);
3.304 - excess.set(v, excess.get(v)+exc);
3.305 - exc=0;
3.306 - break;
3.307 -
3.308 - } else {
3.309 - /*A saturating push.*/
3.310 -
3.311 - _flow.set(e, cap);
3.312 - excess.set(v, excess.get(v)+remcap);
3.313 - exc-=remcap;
3.314 - }
3.315 - } else if ( newlevel > level.get(v) ){
3.316 - newlevel = level.get(v);
3.317 - }
3.318 -
3.319 - } //for out edges wv
3.320 -
3.321 -
3.322 - if ( exc > 0 ) {
3.323 - for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
3.324 -
3.325 - if( _flow.get(e) == 0 ) continue;
3.326 - NodeIt v=G.tail(e);
3.327 - //e=vw
3.328 -
3.329 - if( lev > level.get(v) ) {
3.330 - /*Push is allowed now*/
3.331 -
3.332 - if ( excess.get(v)==0 && v!=t && v!=s ) {
3.333 - int lev_v=level.get(v);
3.334 - next.set(v,active[lev_v]);
3.335 - active[lev_v]=v;
3.336 - }
3.337 -
3.338 - T flo=_flow.get(e);
3.339 -
3.340 - if ( flo >= exc ) {
3.341 - /*A nonsaturating push.*/
3.342 -
3.343 - _flow.set(e, flo-exc);
3.344 - excess.set(v, excess.get(v)+exc);
3.345 - exc=0;
3.346 - break;
3.347 - } else {
3.348 - /*A saturating push.*/
3.349 -
3.350 - excess.set(v, excess.get(v)+flo);
3.351 - exc-=flo;
3.352 - _flow.set(e,0);
3.353 - }
3.354 - } else if ( newlevel > level.get(v) ) {
3.355 - newlevel = level.get(v);
3.356 - }
3.357 - } //for in edges vw
3.358 -
3.359 - } // if w still has excess after the out edge for cycle
3.360 -
3.361 - excess.set(w, exc);
3.362 -
3.363 - /*
3.364 - Relabel
3.365 - */
3.366 -
3.367 -
3.368 - if ( exc > 0 ) {
3.369 - //now 'lev' is the old level of w
3.370 -
3.371 - if ( phase ) {
3.372 - level.set(w,++newlevel);
3.373 - next.set(w,active[newlevel]);
3.374 - active[newlevel]=w;
3.375 - b=newlevel;
3.376 - } else {
3.377 - //unlacing starts
3.378 - NodeIt right_n=right.get(w);
3.379 - NodeIt left_n=left.get(w);
3.380 -
3.381 - if ( right_n != 0 ) {
3.382 - if ( left_n != 0 ) {
3.383 - right.set(left_n, right_n);
3.384 - left.set(right_n, left_n);
3.385 - } else {
3.386 - level_list[lev]=right_n;
3.387 - left.set(right_n, 0);
3.388 - }
3.389 - } else {
3.390 - if ( left_n != 0 ) {
3.391 - right.set(left_n, 0);
3.392 - } else {
3.393 - level_list[lev]=0;
3.394 -
3.395 - }
3.396 - }
3.397 - //unlacing ends
3.398 -
3.399 - //gapping starts
3.400 - if ( level_list[lev]==0 ) {
3.401 -
3.402 - for (int i=lev; i!=k ; ) {
3.403 - NodeIt v=level_list[++i];
3.404 - while ( v != 0 ) {
3.405 - level.set(v,n);
3.406 - v=right.get(v);
3.407 - }
3.408 - level_list[i]=0;
3.409 - if ( !what_heur ) active[i]=0;
3.410 - }
3.411 -
3.412 - level.set(w,n);
3.413 - b=lev-1;
3.414 - k=b;
3.415 - //gapping ends
3.416 - } else {
3.417 -
3.418 - if ( newlevel == n ) level.set(w,n);
3.419 - else {
3.420 - level.set(w,++newlevel);
3.421 - next.set(w,active[newlevel]);
3.422 - active[newlevel]=w;
3.423 - if ( what_heur ) b=newlevel;
3.424 - if ( k < newlevel ) ++k;
3.425 - NodeIt first=level_list[newlevel];
3.426 - if ( first != 0 ) left.set(first,w);
3.427 - right.set(w,first);
3.428 - left.set(w,0);
3.429 - level_list[newlevel]=w;
3.430 - }
3.431 - }
3.432 -
3.433 -
3.434 - ++relabel;
3.435 - if ( relabel >= heur ) {
3.436 - relabel=0;
3.437 - if ( what_heur ) {
3.438 - what_heur=0;
3.439 - heur=heur0;
3.440 - end=false;
3.441 - } else {
3.442 - what_heur=1;
3.443 - heur=heur1;
3.444 - b=k;
3.445 - }
3.446 - }
3.447 - } //phase 0
3.448 -
3.449 -
3.450 - } // if ( exc > 0 )
3.451 -
3.452 -
3.453 - } // if stack[b] is nonempty
3.454 -
3.455 - } // while(true)
3.456 -
3.457 -
3.458 - value = excess.get(t);
3.459 - /*Max flow value.*/
3.460 -
3.461 - } //void run()
3.462 -
3.463 -
3.464 -
3.465 -
3.466 -
3.467 - /*
3.468 - Returns the maximum value of a flow.
3.469 - */
3.470 -
3.471 - T maxFlow() {
3.472 - return value;
3.473 - }
3.474 -
3.475 -
3.476 -
3.477 - /*
3.478 - For the maximum flow x found by the algorithm,
3.479 - it returns the flow value on edge e, i.e. x(e).
3.480 - */
3.481 -
3.482 - T flow(EdgeIt e) {
3.483 - return _flow.get(e);
3.484 - }
3.485 -
3.486 -
3.487 -
3.488 - FlowMap flow() {
3.489 - return _flow;
3.490 - }
3.491 -
3.492 -
3.493 -
3.494 - void flow(FlowMap& __flow ) {
3.495 - for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v)
3.496 - __flow.set(v,_flow.get(v));
3.497 - }
3.498 -
3.499 -
3.500 -
3.501 - /*
3.502 - Returns the minimum min cut, by a bfs from s in the residual graph.
3.503 - */
3.504 -
3.505 - template<typename _CutMap>
3.506 - void minMinCut(_CutMap& M) {
3.507 -
3.508 - std::queue<NodeIt> queue;
3.509 -
3.510 - M.set(s,true);
3.511 - queue.push(s);
3.512 -
3.513 - while (!queue.empty()) {
3.514 - NodeIt w=queue.front();
3.515 - queue.pop();
3.516 -
3.517 - for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
3.518 - NodeIt v=G.head(e);
3.519 - if (!M.get(v) && _flow.get(e) < capacity.get(e) ) {
3.520 - queue.push(v);
3.521 - M.set(v, true);
3.522 - }
3.523 - }
3.524 -
3.525 - for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
3.526 - NodeIt v=G.tail(e);
3.527 - if (!M.get(v) && _flow.get(e) > 0 ) {
3.528 - queue.push(v);
3.529 - M.set(v, true);
3.530 - }
3.531 - }
3.532 - }
3.533 - }
3.534 -
3.535 -
3.536 -
3.537 - /*
3.538 - Returns the maximum min cut, by a reverse bfs
3.539 - from t in the residual graph.
3.540 - */
3.541 -
3.542 - template<typename _CutMap>
3.543 - void maxMinCut(_CutMap& M) {
3.544 -
3.545 - std::queue<NodeIt> queue;
3.546 -
3.547 - M.set(t,true);
3.548 - queue.push(t);
3.549 -
3.550 - while (!queue.empty()) {
3.551 - NodeIt w=queue.front();
3.552 - queue.pop();
3.553 -
3.554 - for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
3.555 - NodeIt v=G.tail(e);
3.556 - if (!M.get(v) && _flow.get(e) < capacity.get(e) ) {
3.557 - queue.push(v);
3.558 - M.set(v, true);
3.559 - }
3.560 - }
3.561 -
3.562 - for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
3.563 - NodeIt v=G.head(e);
3.564 - if (!M.get(v) && _flow.get(e) > 0 ) {
3.565 - queue.push(v);
3.566 - M.set(v, true);
3.567 - }
3.568 - }
3.569 - }
3.570 -
3.571 - for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v) {
3.572 - M.set(v, !M.get(v));
3.573 - }
3.574 -
3.575 - }
3.576 -
3.577 -
3.578 -
3.579 - template<typename CutMap>
3.580 - void minCut(CutMap& M) {
3.581 - minMinCut(M);
3.582 - }
3.583 -
3.584 -
3.585 - };
3.586 -}//namespace marci
3.587 -#endif
3.588 -
3.589 -
3.590 -
3.591 -
4.1 --- a/src/work/jacint/preflow_hl0.cc Mon Mar 01 17:24:34 2004 +0000
4.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
4.3 @@ -1,71 +0,0 @@
4.4 -#include <iostream>
4.5 -#include <fstream>
4.6 -
4.7 -#include <list_graph.hh>
4.8 -#include <dimacs.hh>
4.9 -#include <preflow_hl0.h>
4.10 -#include <time_measure.h>
4.11 -
4.12 -using namespace hugo;
4.13 -
4.14 -// Use a DIMACS max flow file as stdin.
4.15 -// read_dimacs_demo < dimacs_max_flow_file
4.16 -int main(int, char **) {
4.17 - typedef ListGraph::NodeIt NodeIt;
4.18 - typedef ListGraph::EachEdgeIt EachEdgeIt;
4.19 -
4.20 - ListGraph G;
4.21 - NodeIt s, t;
4.22 - ListGraph::EdgeMap<int> cap(G);
4.23 - readDimacsMaxFlow(std::cin, G, s, t, cap);
4.24 -
4.25 - std::cout << "preflow_hl0 demo ..." << std::endl;
4.26 -
4.27 - double mintime=1000000;
4.28 -
4.29 - for ( int i=1; i!=11; ++i ) {
4.30 - double pre_time=currTime();
4.31 - preflow_hl0<ListGraph, int> max_flow_test(G, s, t, cap);
4.32 - double post_time=currTime();
4.33 - if ( mintime > post_time-pre_time ) mintime = post_time-pre_time;
4.34 - }
4.35 -
4.36 - double pre_time=currTime();
4.37 - preflow_hl0<ListGraph, int> max_flow_test(G, s, t, cap);
4.38 - double post_time=currTime();
4.39 -
4.40 - ListGraph::NodeMap<bool> cut(G);
4.41 - max_flow_test.minCut(cut);
4.42 - int min_cut_value=0;
4.43 - for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
4.44 - if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);
4.45 - }
4.46 -
4.47 - ListGraph::NodeMap<bool> cut1(G);
4.48 - max_flow_test.minMinCut(cut1);
4.49 - int min_min_cut_value=0;
4.50 - for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
4.51 - if (cut.get(G.tail(e)) && !cut.get(G.head(e)))
4.52 - min_min_cut_value+=cap.get(e);
4.53 - }
4.54 -
4.55 - ListGraph::NodeMap<bool> cut2(G);
4.56 - max_flow_test.maxMinCut(cut2);
4.57 - int max_min_cut_value=0;
4.58 - for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
4.59 - if (cut2.get(G.tail(e)) && !cut2.get(G.head(e)))
4.60 - max_min_cut_value+=cap.get(e);
4.61 - }
4.62 -
4.63 - std::cout << "min time of 10 runs: " << mintime << " sec"<< std::endl;
4.64 - std::cout << "phase 0: " << max_flow_test.time-pre_time
4.65 - << " sec"<< std::endl;
4.66 - std::cout << "phase 1: " << post_time-max_flow_test.time
4.67 - << " sec"<< std::endl;
4.68 - std::cout << "flow value: "<< max_flow_test.maxFlow() << std::endl;
4.69 - std::cout << "min cut value: "<< min_cut_value << std::endl;
4.70 - std::cout << "min min cut value: "<< min_min_cut_value << std::endl;
4.71 - std::cout << "max min cut value: "<< max_min_cut_value << std::endl;
4.72 -
4.73 - return 0;
4.74 -}
5.1 --- a/src/work/jacint/preflow_hl0.h Mon Mar 01 17:24:34 2004 +0000
5.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
5.3 @@ -1,508 +0,0 @@
5.4 -// -*- C++ -*-
5.5 -/*
5.6 -preflow_hl0.h
5.7 -by jacint.
5.8 -Heuristics:
5.9 - 2 phase
5.10 - gap
5.11 - list 'level_list' on the nodes on level i implemented by hand
5.12 - stack 'active' on the active nodes on level i implemented by hand
5.13 - bound decrease
5.14 -
5.15 -The bound decrease heuristic behaves unexpectedly well.
5.16 -
5.17 -The constructor runs the algorithm.
5.18 -
5.19 -Members:
5.20 -
5.21 -T maxFlow() : returns the value of a maximum flow
5.22 -
5.23 -T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e)
5.24 -
5.25 -FlowMap Flow() : returns the fixed maximum flow x
5.26 -
5.27 -void minMinCut(CutMap& M) : sets M to the characteristic vector of the
5.28 - minimum min cut. M should be a map of bools initialized to false.
5.29 -
5.30 -void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
5.31 - maximum min cut. M should be a map of bools initialized to false.
5.32 -
5.33 -
5.34 -void minCut(CutMap& M) : sets M to the characteristic vector of
5.35 - a min cut. M should be a map of bools initialized to false.
5.36 -
5.37 -*/
5.38 -
5.39 -#ifndef PREFLOW_HL0_H
5.40 -#define PREFLOW_HL0_H
5.41 -
5.42 -#include <vector>
5.43 -#include <queue>
5.44 -
5.45 -#include <time_measure.h> //for test
5.46 -
5.47 -namespace hugo {
5.48 -
5.49 - template <typename Graph, typename T,
5.50 - typename FlowMap=typename Graph::EdgeMap<T>,
5.51 - typename CapMap=typename Graph::EdgeMap<T> >
5.52 - class preflow_hl0 {
5.53 -
5.54 - typedef typename Graph::NodeIt NodeIt;
5.55 - typedef typename Graph::EdgeIt EdgeIt;
5.56 - typedef typename Graph::EachNodeIt EachNodeIt;
5.57 - typedef typename Graph::OutEdgeIt OutEdgeIt;
5.58 - typedef typename Graph::InEdgeIt InEdgeIt;
5.59 -
5.60 - Graph& G;
5.61 - NodeIt s;
5.62 - NodeIt t;
5.63 - FlowMap flow;
5.64 - CapMap& capacity;
5.65 - T value;
5.66 -
5.67 - public:
5.68 - double time;
5.69 -
5.70 - preflow_hl0(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity ) :
5.71 - G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) {
5.72 -
5.73 - bool phase=0; //phase 0 is the 1st phase, phase 1 is the 2nd
5.74 - int n=G.nodeNum();
5.75 - bool end=false;
5.76 - /*
5.77 - 'true' means no active nodes are above bound b.
5.78 - */
5.79 - int k=n-2; //bound on the highest level under n containing a node
5.80 - int b=k; //bound on the highest level under n of an active node
5.81 - /*
5.82 - b is a bound on the highest level of the stack.
5.83 - k is a bound on the highest nonempty level i < n.
5.84 - */
5.85 -
5.86 - typename Graph::NodeMap<int> level(G,n);
5.87 - typename Graph::NodeMap<T> excess(G);
5.88 -
5.89 - std::vector<NodeIt> active(n);
5.90 - typename Graph::NodeMap<NodeIt> next(G);
5.91 - //Stack of the active nodes in level i < n.
5.92 - //We use it in both phases.
5.93 -
5.94 - typename Graph::NodeMap<NodeIt> left(G);
5.95 - typename Graph::NodeMap<NodeIt> right(G);
5.96 - std::vector<NodeIt> level_list(n);
5.97 - /*
5.98 - List of the nodes in level i<n.
5.99 - */
5.100 -
5.101 - /*Reverse_bfs from t, to find the starting level.*/
5.102 - level.set(t,0);
5.103 - std::queue<NodeIt> bfs_queue;
5.104 - bfs_queue.push(t);
5.105 -
5.106 - while (!bfs_queue.empty()) {
5.107 -
5.108 - NodeIt v=bfs_queue.front();
5.109 - bfs_queue.pop();
5.110 - int l=level.get(v)+1;
5.111 -
5.112 - for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
5.113 - NodeIt w=G.tail(e);
5.114 - if ( level.get(w) == n && w != s ) {
5.115 - bfs_queue.push(w);
5.116 - NodeIt first=level_list[l];
5.117 - if ( first != 0 ) left.set(first,w);
5.118 - right.set(w,first);
5.119 - level_list[l]=w;
5.120 - level.set(w, l);
5.121 - }
5.122 - }
5.123 - }
5.124 -
5.125 - level.set(s,n);
5.126 -
5.127 -
5.128 - /* Starting flow. It is everywhere 0 at the moment. */
5.129 - for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e)
5.130 - {
5.131 - T c=capacity.get(e);
5.132 - if ( c == 0 ) continue;
5.133 - NodeIt w=G.head(e);
5.134 - if ( level.get(w) < n ) {
5.135 - if ( excess.get(w) == 0 && w!=t ) {
5.136 - next.set(w,active[level.get(w)]);
5.137 - active[level.get(w)]=w;
5.138 - }
5.139 - flow.set(e, c);
5.140 - excess.set(w, excess.get(w)+c);
5.141 - }
5.142 - }
5.143 -
5.144 - /*
5.145 - End of preprocessing
5.146 - */
5.147 -
5.148 -
5.149 -
5.150 - /*
5.151 - Push/relabel on the highest level active nodes.
5.152 - */
5.153 - while ( true ) {
5.154 -
5.155 - if ( b == 0 ) {
5.156 - if ( phase ) break;
5.157 -
5.158 - if ( !end && k > 0 ) {
5.159 - b=k;
5.160 - end=true;
5.161 - } else {
5.162 - phase=1;
5.163 - time=currTime();
5.164 - level.set(s,0);
5.165 - std::queue<NodeIt> bfs_queue;
5.166 - bfs_queue.push(s);
5.167 -
5.168 - while (!bfs_queue.empty()) {
5.169 -
5.170 - NodeIt v=bfs_queue.front();
5.171 - bfs_queue.pop();
5.172 - int l=level.get(v)+1;
5.173 -
5.174 - for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
5.175 - if ( capacity.get(e) == flow.get(e) ) continue;
5.176 - NodeIt u=G.tail(e);
5.177 - if ( level.get(u) >= n ) {
5.178 - bfs_queue.push(u);
5.179 - level.set(u, l);
5.180 - if ( excess.get(u) > 0 ) {
5.181 - next.set(u,active[l]);
5.182 - active[l]=u;
5.183 - }
5.184 - }
5.185 - }
5.186 -
5.187 - for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) {
5.188 - if ( 0 == flow.get(e) ) continue;
5.189 - NodeIt u=G.head(e);
5.190 - if ( level.get(u) >= n ) {
5.191 - bfs_queue.push(u);
5.192 - level.set(u, l);
5.193 - if ( excess.get(u) > 0 ) {
5.194 - next.set(u,active[l]);
5.195 - active[l]=u;
5.196 - }
5.197 - }
5.198 - }
5.199 - }
5.200 - b=n-2;
5.201 - }
5.202 -
5.203 - }
5.204 -
5.205 -
5.206 - if ( active[b] == 0 ) --b;
5.207 - else {
5.208 - end=false;
5.209 -
5.210 - NodeIt w=active[b];
5.211 - active[b]=next.get(w);
5.212 - int lev=level.get(w);
5.213 - T exc=excess.get(w);
5.214 - int newlevel=n; //bound on the next level of w
5.215 -
5.216 - for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
5.217 -
5.218 - if ( flow.get(e) == capacity.get(e) ) continue;
5.219 - NodeIt v=G.head(e);
5.220 - //e=wv
5.221 -
5.222 - if( lev > level.get(v) ) {
5.223 - /*Push is allowed now*/
5.224 -
5.225 - if ( excess.get(v)==0 && v!=t && v!=s ) {
5.226 - int lev_v=level.get(v);
5.227 - next.set(v,active[lev_v]);
5.228 - active[lev_v]=v;
5.229 - }
5.230 -
5.231 - T cap=capacity.get(e);
5.232 - T flo=flow.get(e);
5.233 - T remcap=cap-flo;
5.234 -
5.235 - if ( remcap >= exc ) {
5.236 - /*A nonsaturating push.*/
5.237 -
5.238 - flow.set(e, flo+exc);
5.239 - excess.set(v, excess.get(v)+exc);
5.240 - exc=0;
5.241 - break;
5.242 -
5.243 - } else {
5.244 - /*A saturating push.*/
5.245 -
5.246 - flow.set(e, cap);
5.247 - excess.set(v, excess.get(v)+remcap);
5.248 - exc-=remcap;
5.249 - }
5.250 - } else if ( newlevel > level.get(v) ){
5.251 - newlevel = level.get(v);
5.252 - }
5.253 -
5.254 - } //for out edges wv
5.255 -
5.256 -
5.257 - if ( exc > 0 ) {
5.258 - for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
5.259 -
5.260 - if( flow.get(e) == 0 ) continue;
5.261 - NodeIt v=G.tail(e);
5.262 - //e=vw
5.263 -
5.264 - if( lev > level.get(v) ) {
5.265 - /*Push is allowed now*/
5.266 -
5.267 - if ( excess.get(v)==0 && v!=t && v!=s ) {
5.268 - int lev_v=level.get(v);
5.269 - next.set(v,active[lev_v]);
5.270 - active[lev_v]=v;
5.271 - }
5.272 -
5.273 - T flo=flow.get(e);
5.274 -
5.275 - if ( flo >= exc ) {
5.276 - /*A nonsaturating push.*/
5.277 -
5.278 - flow.set(e, flo-exc);
5.279 - excess.set(v, excess.get(v)+exc);
5.280 - exc=0;
5.281 - break;
5.282 - } else {
5.283 - /*A saturating push.*/
5.284 -
5.285 - excess.set(v, excess.get(v)+flo);
5.286 - exc-=flo;
5.287 - flow.set(e,0);
5.288 - }
5.289 - } else if ( newlevel > level.get(v) ) {
5.290 - newlevel = level.get(v);
5.291 - }
5.292 - } //for in edges vw
5.293 -
5.294 - } // if w still has excess after the out edge for cycle
5.295 -
5.296 - excess.set(w, exc);
5.297 -
5.298 - /*
5.299 - Relabel
5.300 - */
5.301 -
5.302 -
5.303 - if ( exc > 0 ) {
5.304 - //now 'lev' is the old level of w
5.305 -
5.306 - if ( phase ) {
5.307 - level.set(w,++newlevel);
5.308 - next.set(w,active[newlevel]);
5.309 - active[newlevel]=w;
5.310 - b=newlevel;
5.311 - } else {
5.312 - //unlacing starts
5.313 - NodeIt right_n=right.get(w);
5.314 - NodeIt left_n=left.get(w);
5.315 -
5.316 - if ( right_n != 0 ) {
5.317 - if ( left_n != 0 ) {
5.318 - right.set(left_n, right_n);
5.319 - left.set(right_n, left_n);
5.320 - } else {
5.321 - level_list[lev]=right_n;
5.322 - left.set(right_n, 0);
5.323 - }
5.324 - } else {
5.325 - if ( left_n != 0 ) {
5.326 - right.set(left_n, 0);
5.327 - } else {
5.328 - level_list[lev]=0;
5.329 -
5.330 - }
5.331 - }
5.332 - //unlacing ends
5.333 -
5.334 - //gapping starts
5.335 - if ( level_list[lev]==0 ) {
5.336 -
5.337 - for (int i=lev; i!=k ; ) {
5.338 - NodeIt v=level_list[++i];
5.339 - while ( v != 0 ) {
5.340 - level.set(v,n);
5.341 - v=right.get(v);
5.342 - }
5.343 - level_list[i]=0;
5.344 - active[i]=0;
5.345 - }
5.346 -
5.347 - level.set(w,n);
5.348 - b=lev-1;
5.349 - k=b;
5.350 - //gapping ends
5.351 - } else {
5.352 -
5.353 - if ( newlevel == n ) level.set(w,n);
5.354 - else {
5.355 - level.set(w,++newlevel);
5.356 - next.set(w,active[newlevel]);
5.357 - active[newlevel]=w;
5.358 - if ( k < newlevel ) ++k;
5.359 - NodeIt first=level_list[newlevel];
5.360 - if ( first != 0 ) left.set(first,w);
5.361 - right.set(w,first);
5.362 - left.set(w,0);
5.363 - level_list[newlevel]=w;
5.364 - }
5.365 - }
5.366 -
5.367 -
5.368 - } //phase 0
5.369 -
5.370 -
5.371 - } // if ( exc > 0 )
5.372 -
5.373 -
5.374 - } // if stack[b] is nonempty
5.375 -
5.376 - } // while(true)
5.377 -
5.378 -
5.379 - value = excess.get(t);
5.380 - /*Max flow value.*/
5.381 -
5.382 - } //void run()
5.383 -
5.384 -
5.385 -
5.386 -
5.387 -
5.388 - /*
5.389 - Returns the maximum value of a flow.
5.390 - */
5.391 -
5.392 - T maxFlow() {
5.393 - return value;
5.394 - }
5.395 -
5.396 -
5.397 -
5.398 - /*
5.399 - For the maximum flow x found by the algorithm,
5.400 - it returns the flow value on edge e, i.e. x(e).
5.401 - */
5.402 -
5.403 - T flowOnEdge(EdgeIt e) {
5.404 - return flow.get(e);
5.405 - }
5.406 -
5.407 -
5.408 -
5.409 - FlowMap Flow() {
5.410 - return flow;
5.411 - }
5.412 -
5.413 -
5.414 -
5.415 - void Flow(FlowMap& _flow ) {
5.416 - for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v)
5.417 - _flow.set(v,flow.get(v));
5.418 - }
5.419 -
5.420 -
5.421 -
5.422 - /*
5.423 - Returns the minimum min cut, by a bfs from s in the residual graph.
5.424 - */
5.425 -
5.426 - template<typename _CutMap>
5.427 - void minMinCut(_CutMap& M) {
5.428 -
5.429 - std::queue<NodeIt> queue;
5.430 -
5.431 - M.set(s,true);
5.432 - queue.push(s);
5.433 -
5.434 - while (!queue.empty()) {
5.435 - NodeIt w=queue.front();
5.436 - queue.pop();
5.437 -
5.438 - for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
5.439 - NodeIt v=G.head(e);
5.440 - if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
5.441 - queue.push(v);
5.442 - M.set(v, true);
5.443 - }
5.444 - }
5.445 -
5.446 - for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
5.447 - NodeIt v=G.tail(e);
5.448 - if (!M.get(v) && flow.get(e) > 0 ) {
5.449 - queue.push(v);
5.450 - M.set(v, true);
5.451 - }
5.452 - }
5.453 - }
5.454 - }
5.455 -
5.456 -
5.457 -
5.458 - /*
5.459 - Returns the maximum min cut, by a reverse bfs
5.460 - from t in the residual graph.
5.461 - */
5.462 -
5.463 - template<typename _CutMap>
5.464 - void maxMinCut(_CutMap& M) {
5.465 -
5.466 - std::queue<NodeIt> queue;
5.467 -
5.468 - M.set(t,true);
5.469 - queue.push(t);
5.470 -
5.471 - while (!queue.empty()) {
5.472 - NodeIt w=queue.front();
5.473 - queue.pop();
5.474 -
5.475 - for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
5.476 - NodeIt v=G.tail(e);
5.477 - if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
5.478 - queue.push(v);
5.479 - M.set(v, true);
5.480 - }
5.481 - }
5.482 -
5.483 - for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
5.484 - NodeIt v=G.head(e);
5.485 - if (!M.get(v) && flow.get(e) > 0 ) {
5.486 - queue.push(v);
5.487 - M.set(v, true);
5.488 - }
5.489 - }
5.490 - }
5.491 -
5.492 - for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v) {
5.493 - M.set(v, !M.get(v));
5.494 - }
5.495 -
5.496 - }
5.497 -
5.498 -
5.499 -
5.500 - template<typename _CutMap>
5.501 - void minCut(_CutMap& M) {
5.502 - minMinCut(M);
5.503 - }
5.504 -
5.505 - };
5.506 -}//namespace marci
5.507 -#endif
5.508 -
5.509 -
5.510 -
5.511 -
6.1 --- a/src/work/jacint/preflow_hl1.cc Mon Mar 01 17:24:34 2004 +0000
6.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
6.3 @@ -1,73 +0,0 @@
6.4 -#include <iostream>
6.5 -#include <fstream>
6.6 -
6.7 -#include <list_graph.hh>
6.8 -#include <dimacs.hh>
6.9 -#include <preflow_hl1.h>
6.10 -#include <time_measure.h>
6.11 -
6.12 -using namespace hugo;
6.13 -
6.14 -// Use a DIMACS max flow file as stdin.
6.15 -// read_dimacs_demo < dimacs_max_flow_file
6.16 -int main(int, char **) {
6.17 - typedef ListGraph::NodeIt NodeIt;
6.18 - typedef ListGraph::EachEdgeIt EachEdgeIt;
6.19 -
6.20 - ListGraph G;
6.21 - NodeIt s, t;
6.22 - ListGraph::EdgeMap<int> cap(G);
6.23 - readDimacsMaxFlow(std::cin, G, s, t, cap);
6.24 -
6.25 - std::cout << "preflow_hl1 demo ..." << std::endl;
6.26 -
6.27 - double mintime=1000000;
6.28 -
6.29 - for ( int i=1; i!=11; ++i ) {
6.30 - double pre_time=currTime();
6.31 - preflow_hl1<ListGraph, int> max_flow_test(G, s, t, cap);
6.32 - double post_time=currTime();
6.33 - if ( mintime > post_time-pre_time ) mintime = post_time-pre_time;
6.34 - }
6.35 -
6.36 - double pre_time=currTime();
6.37 - preflow_hl1<ListGraph, int> max_flow_test(G, s, t, cap);
6.38 - double post_time=currTime();
6.39 -
6.40 - ListGraph::NodeMap<bool> cut(G);
6.41 - max_flow_test.minCut(cut);
6.42 - int min_cut_value=0;
6.43 - for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
6.44 - if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);
6.45 - }
6.46 -
6.47 - ListGraph::NodeMap<bool> cut1(G);
6.48 - max_flow_test.minMinCut(cut1);
6.49 - int min_min_cut_value=0;
6.50 - for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
6.51 - if (cut.get(G.tail(e)) && !cut.get(G.head(e)))
6.52 - min_min_cut_value+=cap.get(e);
6.53 - }
6.54 -
6.55 - ListGraph::NodeMap<bool> cut2(G);
6.56 - max_flow_test.maxMinCut(cut2);
6.57 - int max_min_cut_value=0;
6.58 - for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
6.59 - if (cut2.get(G.tail(e)) && !cut2.get(G.head(e)))
6.60 - max_min_cut_value+=cap.get(e);
6.61 - }
6.62 -
6.63 - std::cout << "min time of 10 runs: " << mintime << " sec"<< std::endl;
6.64 - std::cout << "phase 0: " << max_flow_test.time-pre_time
6.65 - << " sec"<< std::endl;
6.66 - std::cout << "phase 1: " << post_time-max_flow_test.time
6.67 - << " sec"<< std::endl;
6.68 - std::cout << "flow value: "<< max_flow_test.maxFlow() << std::endl;
6.69 - std::cout << "min cut value: "<< min_cut_value << std::endl;
6.70 - std::cout << "min min cut value: "<< min_min_cut_value << std::endl;
6.71 - std::cout << "max min cut value: "<< max_min_cut_value <<
6.72 - std::endl<< std::endl;
6.73 -
6.74 -
6.75 - return 0;
6.76 -}
7.1 --- a/src/work/jacint/preflow_hl2.cc Mon Mar 01 17:24:34 2004 +0000
7.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
7.3 @@ -1,65 +0,0 @@
7.4 -#include <iostream>
7.5 -#include <fstream>
7.6 -
7.7 -#include <list_graph.hh>
7.8 -#include <dimacs.hh>
7.9 -#include <preflow_hl2.h>
7.10 -#include <time_measure.h>
7.11 -
7.12 -using namespace hugo;
7.13 -
7.14 -// Use a DIMACS max flow file as stdin.
7.15 -// read_dimacs_demo < dimacs_max_flow_file
7.16 -int main(int, char **) {
7.17 - typedef ListGraph::NodeIt NodeIt;
7.18 - typedef ListGraph::EachEdgeIt EachEdgeIt;
7.19 -
7.20 - ListGraph G;
7.21 - NodeIt s, t;
7.22 - ListGraph::EdgeMap<int> cap(G);
7.23 - readDimacsMaxFlow(std::cin, G, s, t, cap);
7.24 -
7.25 - std::cout << "preflow_hl2 demo ..." << std::endl;
7.26 -
7.27 - double mintime=1000000;
7.28 -
7.29 - for ( int i=1; i!=11; ++i ) {
7.30 - double pre_time=currTime();
7.31 - preflow_hl2<ListGraph, int> max_flow_test(G, s, t, cap);
7.32 - double post_time=currTime();
7.33 - if ( mintime > post_time-pre_time ) mintime = post_time-pre_time;
7.34 - }
7.35 -
7.36 - preflow_hl2<ListGraph, int> max_flow_test(G, s, t, cap);
7.37 -
7.38 - ListGraph::NodeMap<bool> cut(G);
7.39 - max_flow_test.minCut(cut);
7.40 - int min_cut_value=0;
7.41 - for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
7.42 - if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);
7.43 - }
7.44 -
7.45 - ListGraph::NodeMap<bool> cut1(G);
7.46 - max_flow_test.minMinCut(cut1);
7.47 - int min_min_cut_value=0;
7.48 - for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
7.49 - if (cut.get(G.tail(e)) && !cut.get(G.head(e)))
7.50 - min_min_cut_value+=cap.get(e);
7.51 - }
7.52 -
7.53 - ListGraph::NodeMap<bool> cut2(G);
7.54 - max_flow_test.maxMinCut(cut2);
7.55 - int max_min_cut_value=0;
7.56 - for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
7.57 - if (cut2.get(G.tail(e)) && !cut2.get(G.head(e)))
7.58 - max_min_cut_value+=cap.get(e);
7.59 - }
7.60 -
7.61 - std::cout << "min time of 10 runs: " << mintime << " sec"<< std::endl;
7.62 - std::cout << "flow value: "<< max_flow_test.maxFlow() << std::endl;
7.63 - std::cout << "min cut value: "<< min_cut_value << std::endl;
7.64 - std::cout << "min min cut value: "<< min_min_cut_value << std::endl;
7.65 - std::cout << "max min cut value: "<< max_min_cut_value << std::endl;
7.66 -
7.67 - return 0;
7.68 -}
8.1 --- a/src/work/jacint/preflow_hl2.h Mon Mar 01 17:24:34 2004 +0000
8.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
8.3 @@ -1,394 +0,0 @@
8.4 -// -*- C++ -*-
8.5 -/*
8.6 -preflow_hl2.h
8.7 -by jacint.
8.8 -Runs the highest label variant of the preflow push algorithm with
8.9 -running time O(n^2\sqrt(m)).
8.10 -
8.11 -Heuristics:
8.12 -
8.13 - gap: we iterate through the nodes for finding the nodes above
8.14 - the gap and under level n. So it is quite slow.
8.15 - numb: we maintain the number of nodes in level i.
8.16 - highest label
8.17 -
8.18 -'A' is a parameter for the gap, we only upgrade the nodes to level n,
8.19 - if the gap is under A*n.
8.20 -
8.21 -The constructor runs the algorithm.
8.22 -
8.23 -Members:
8.24 -
8.25 -T maxFlow() : returns the value of a maximum flow
8.26 -
8.27 -T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e)
8.28 -
8.29 -FlowMap Flow() : returns the fixed maximum flow x
8.30 -
8.31 -void minCut(CutMap& M) : sets M to the characteristic vector of a
8.32 - minimum cut. M should be a map of bools initialized to false.
8.33 -
8.34 -void minMinCut(CutMap& M) : sets M to the characteristic vector of the
8.35 - minimum min cut. M should be a map of bools initialized to false.
8.36 -
8.37 -void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
8.38 - maximum min cut. M should be a map of bools initialized to false.
8.39 -
8.40 -*/
8.41 -
8.42 -#ifndef PREFLOW_HL2_H
8.43 -#define PREFLOW_HL2_H
8.44 -
8.45 -#define A .9
8.46 -
8.47 -#include <vector>
8.48 -#include <stack>
8.49 -#include <queue>
8.50 -
8.51 -namespace hugo {
8.52 -
8.53 - template <typename Graph, typename T,
8.54 - typename FlowMap=typename Graph::EdgeMap<T>,
8.55 - typename CapMap=typename Graph::EdgeMap<T> >
8.56 - class preflow_hl2 {
8.57 -
8.58 - typedef typename Graph::NodeIt NodeIt;
8.59 - typedef typename Graph::EdgeIt EdgeIt;
8.60 - typedef typename Graph::EachNodeIt EachNodeIt;
8.61 - typedef typename Graph::OutEdgeIt OutEdgeIt;
8.62 - typedef typename Graph::InEdgeIt InEdgeIt;
8.63 -
8.64 - Graph& G;
8.65 - NodeIt s;
8.66 - NodeIt t;
8.67 - FlowMap flow;
8.68 - CapMap& capacity;
8.69 - T value;
8.70 -
8.71 - public:
8.72 -
8.73 - preflow_hl2(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) :
8.74 - G(_G), s(_s), t(_t), flow(_G), capacity(_capacity) {
8.75 -
8.76 - int n=G.nodeNum();
8.77 - int b=n-2;
8.78 - /*
8.79 - b is a bound on the highest level of an active node.
8.80 - */
8.81 -
8.82 - typename Graph::NodeMap<int> level(G,n);
8.83 - typename Graph::NodeMap<T> excess(G);
8.84 -
8.85 - std::vector<int> numb(n);
8.86 - /*
8.87 - The number of nodes on level i < n. It is
8.88 - initialized to n+1, because of the reverse_bfs-part.
8.89 - */
8.90 -
8.91 - std::vector<std::stack<NodeIt> > stack(2*n-1);
8.92 - //Stack of the active nodes in level i.
8.93 -
8.94 -
8.95 - /*Reverse_bfs from t, to find the starting level.*/
8.96 - level.set(t,0);
8.97 - std::queue<NodeIt> bfs_queue;
8.98 - bfs_queue.push(t);
8.99 -
8.100 - while (!bfs_queue.empty()) {
8.101 -
8.102 - NodeIt v=bfs_queue.front();
8.103 - bfs_queue.pop();
8.104 - int l=level.get(v)+1;
8.105 -
8.106 - for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
8.107 - NodeIt w=G.tail(e);
8.108 - if ( level.get(w) == n ) {
8.109 - bfs_queue.push(w);
8.110 - ++numb[l];
8.111 - level.set(w, l);
8.112 - }
8.113 - }
8.114 - }
8.115 -
8.116 - level.set(s,n);
8.117 -
8.118 -
8.119 -
8.120 - /* Starting flow. It is everywhere 0 at the moment. */
8.121 - for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e)
8.122 - {
8.123 - T c=capacity.get(e);
8.124 - if ( c == 0 ) continue;
8.125 - NodeIt w=G.head(e);
8.126 - if ( w!=s ) {
8.127 - if ( excess.get(w) == 0 && w!=t ) stack[level.get(w)].push(w);
8.128 - flow.set(e, c);
8.129 - excess.set(w, excess.get(w)+c);
8.130 - }
8.131 - }
8.132 -
8.133 - /*
8.134 - End of preprocessing
8.135 - */
8.136 -
8.137 -
8.138 - /*
8.139 - Push/relabel on the highest level active nodes.
8.140 - */
8.141 - /*While there exists an active node.*/
8.142 - while (b) {
8.143 - if ( stack[b].empty() ) {
8.144 - --b;
8.145 - continue;
8.146 - }
8.147 -
8.148 - NodeIt w=stack[b].top();
8.149 - stack[b].pop();
8.150 - int lev=level.get(w);
8.151 - T exc=excess.get(w);
8.152 - int newlevel=2*n; //In newlevel we bound the next level of w.
8.153 -
8.154 - for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
8.155 -
8.156 - if ( flow.get(e) == capacity.get(e) ) continue;
8.157 - NodeIt v=G.head(e);
8.158 - //e=wv
8.159 -
8.160 - if( lev > level.get(v) ) {
8.161 - /*Push is allowed now*/
8.162 -
8.163 - if ( excess.get(v)==0 && v != s && v !=t )
8.164 - stack[level.get(v)].push(v);
8.165 - /*v becomes active.*/
8.166 -
8.167 - T cap=capacity.get(e);
8.168 - T flo=flow.get(e);
8.169 - T remcap=cap-flo;
8.170 -
8.171 - if ( remcap >= exc ) {
8.172 - /*A nonsaturating push.*/
8.173 -
8.174 - flow.set(e, flo+exc);
8.175 - excess.set(v, excess.get(v)+exc);
8.176 - exc=0;
8.177 - break;
8.178 -
8.179 - } else {
8.180 - /*A saturating push.*/
8.181 -
8.182 - flow.set(e, cap );
8.183 - excess.set(v, excess.get(v)+remcap);
8.184 - exc-=remcap;
8.185 - }
8.186 - } else if ( newlevel > level.get(v) ) newlevel = level.get(v);
8.187 -
8.188 - } //for out edges wv
8.189 -
8.190 -
8.191 - if ( exc > 0 ) {
8.192 - for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
8.193 -
8.194 - if( flow.get(e) == 0 ) continue;
8.195 - NodeIt v=G.tail(e);
8.196 - //e=vw
8.197 -
8.198 - if( lev > level.get(v) ) {
8.199 - /*Push is allowed now*/
8.200 -
8.201 - if ( excess.get(v)==0 && v != s && v !=t)
8.202 - stack[level.get(v)].push(v);
8.203 - /*v becomes active.*/
8.204 -
8.205 - T flo=flow.get(e);
8.206 -
8.207 - if ( flo >= exc ) {
8.208 - /*A nonsaturating push.*/
8.209 -
8.210 - flow.set(e, flo-exc);
8.211 - excess.set(v, excess.get(v)+exc);
8.212 - exc=0;
8.213 - break;
8.214 - } else {
8.215 - /*A saturating push.*/
8.216 -
8.217 - excess.set(v, excess.get(v)+flo);
8.218 - exc-=flo;
8.219 - flow.set(e,0);
8.220 - }
8.221 - } else if ( newlevel > level.get(v) ) newlevel = level.get(v);
8.222 -
8.223 - } //for in edges vw
8.224 -
8.225 - } // if w still has excess after the out edge for cycle
8.226 -
8.227 - excess.set(w, exc);
8.228 -
8.229 -
8.230 -
8.231 -
8.232 - /*
8.233 - Relabel
8.234 - */
8.235 -
8.236 - if ( exc > 0 ) {
8.237 - //now 'lev' is the old level of w
8.238 - level.set(w,++newlevel);
8.239 -
8.240 - if ( lev < n ) {
8.241 - --numb[lev];
8.242 -
8.243 - if ( !numb[lev] && lev < A*n ) { //If the level of w gets empty.
8.244 -
8.245 - for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) {
8.246 - if (level.get(v) > lev && level.get(v) < n ) level.set(v,n);
8.247 - }
8.248 - for (int i=lev+1 ; i!=n ; ++i) numb[i]=0;
8.249 - if ( newlevel < n ) newlevel=n;
8.250 - } else {
8.251 - if ( newlevel < n ) ++numb[newlevel];
8.252 - }
8.253 - }
8.254 -
8.255 - stack[newlevel].push(w);
8.256 - b=newlevel;
8.257 -
8.258 - }
8.259 -
8.260 - } // while(b)
8.261 -
8.262 -
8.263 - value = excess.get(t);
8.264 - /*Max flow value.*/
8.265 -
8.266 -
8.267 - } //void run()
8.268 -
8.269 -
8.270 -
8.271 -
8.272 -
8.273 - /*
8.274 - Returns the maximum value of a flow.
8.275 - */
8.276 -
8.277 - T maxFlow() {
8.278 - return value;
8.279 - }
8.280 -
8.281 -
8.282 -
8.283 - /*
8.284 - For the maximum flow x found by the algorithm,
8.285 - it returns the flow value on edge e, i.e. x(e).
8.286 - */
8.287 -
8.288 - T flowOnEdge(const EdgeIt e) {
8.289 - return flow.get(e);
8.290 - }
8.291 -
8.292 -
8.293 -
8.294 - /*
8.295 - Returns the maximum flow x found by the algorithm.
8.296 - */
8.297 -
8.298 - FlowMap Flow() {
8.299 - return flow;
8.300 - }
8.301 -
8.302 -
8.303 -
8.304 -
8.305 - /*
8.306 - Returns the minimum min cut, by a bfs from s in the residual graph.
8.307 - */
8.308 -
8.309 - template<typename CutMap>
8.310 - void minCut(CutMap& M) {
8.311 -
8.312 - std::queue<NodeIt> queue;
8.313 -
8.314 - M.set(s,true);
8.315 - queue.push(s);
8.316 -
8.317 - while (!queue.empty()) {
8.318 - NodeIt w=queue.front();
8.319 - queue.pop();
8.320 -
8.321 - for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
8.322 - NodeIt v=G.head(e);
8.323 - if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
8.324 - queue.push(v);
8.325 - M.set(v, true);
8.326 - }
8.327 - }
8.328 -
8.329 - for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
8.330 - NodeIt v=G.tail(e);
8.331 - if (!M.get(v) && flow.get(e) > 0 ) {
8.332 - queue.push(v);
8.333 - M.set(v, true);
8.334 - }
8.335 - }
8.336 -
8.337 - }
8.338 - }
8.339 -
8.340 -
8.341 -
8.342 - /*
8.343 - Returns the maximum min cut, by a reverse bfs
8.344 - from t in the residual graph.
8.345 - */
8.346 -
8.347 - template<typename CutMap>
8.348 - void maxMinCut(CutMap& M) {
8.349 -
8.350 - std::queue<NodeIt> queue;
8.351 -
8.352 - M.set(t,true);
8.353 - queue.push(t);
8.354 -
8.355 - while (!queue.empty()) {
8.356 - NodeIt w=queue.front();
8.357 - queue.pop();
8.358 -
8.359 - for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
8.360 - NodeIt v=G.tail(e);
8.361 - if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
8.362 - queue.push(v);
8.363 - M.set(v, true);
8.364 - }
8.365 - }
8.366 -
8.367 - for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
8.368 - NodeIt v=G.head(e);
8.369 - if (!M.get(v) && flow.get(e) > 0 ) {
8.370 - queue.push(v);
8.371 - M.set(v, true);
8.372 - }
8.373 - }
8.374 - }
8.375 -
8.376 - for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v) {
8.377 - M.set(v, !M.get(v));
8.378 - }
8.379 -
8.380 - }
8.381 -
8.382 -
8.383 -
8.384 - template<typename CutMap>
8.385 - void minMinCut(CutMap& M) {
8.386 - minCut(M);
8.387 - }
8.388 -
8.389 -
8.390 -
8.391 - };
8.392 -}//namespace marci
8.393 -#endif
8.394 -
8.395 -
8.396 -
8.397 -
9.1 --- a/src/work/jacint/preflow_hl3.cc Mon Mar 01 17:24:34 2004 +0000
9.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
9.3 @@ -1,72 +0,0 @@
9.4 -#include <iostream>
9.5 -#include <fstream>
9.6 -
9.7 -#include <list_graph.hh>
9.8 -#include <dimacs.hh>
9.9 -#include <preflow_hl3.h>
9.10 -#include <time_measure.h>
9.11 -
9.12 -using namespace hugo;
9.13 -
9.14 -// Use a DIMACS max flow file as stdin.
9.15 -// read_dimacs_demo < dimacs_max_flow_file
9.16 -int main(int, char **) {
9.17 - typedef ListGraph::NodeIt NodeIt;
9.18 - typedef ListGraph::EachEdgeIt EachEdgeIt;
9.19 -
9.20 - ListGraph G;
9.21 - NodeIt s, t;
9.22 - ListGraph::EdgeMap<int> cap(G);
9.23 - readDimacsMaxFlow(std::cin, G, s, t, cap);
9.24 -
9.25 - std::cout << "preflow_hl3 demo ..." << std::endl;
9.26 -
9.27 - double mintime=1000000;
9.28 -
9.29 - for ( int i=1; i!=11; ++i ) {
9.30 - double pre_time=currTime();
9.31 - preflow_hl3<ListGraph, int> max_flow_test(G, s, t, cap);
9.32 - double post_time=currTime();
9.33 - if ( mintime > post_time-pre_time ) mintime = post_time-pre_time;
9.34 - }
9.35 -
9.36 - double pre_time=currTime();
9.37 - preflow_hl3<ListGraph, int> max_flow_test(G, s, t, cap);
9.38 - double post_time=currTime();
9.39 -
9.40 - ListGraph::NodeMap<bool> cut(G);
9.41 - max_flow_test.minCut(cut);
9.42 - int min_cut_value=0;
9.43 - for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
9.44 - if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);
9.45 - }
9.46 -
9.47 - ListGraph::NodeMap<bool> cut1(G);
9.48 - max_flow_test.minMinCut(cut1);
9.49 - int min_min_cut_value=0;
9.50 - for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
9.51 - if (cut.get(G.tail(e)) && !cut.get(G.head(e)))
9.52 - min_min_cut_value+=cap.get(e);
9.53 - }
9.54 -
9.55 - ListGraph::NodeMap<bool> cut2(G);
9.56 - max_flow_test.maxMinCut(cut2);
9.57 - int max_min_cut_value=0;
9.58 - for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
9.59 - if (cut2.get(G.tail(e)) && !cut2.get(G.head(e)))
9.60 - max_min_cut_value+=cap.get(e);
9.61 - }
9.62 -
9.63 - std::cout << "min time of 10 runs: " << mintime << " sec"<< std::endl;
9.64 - std::cout << "phase 0: " << max_flow_test.time-pre_time
9.65 - << " sec"<< std::endl;
9.66 - std::cout << "phase 1: " << post_time-max_flow_test.time
9.67 - << " sec"<< std::endl;
9.68 - std::cout << "flow value: "<< max_flow_test.maxFlow() << std::endl;
9.69 - std::cout << "min cut value: "<< min_cut_value << std::endl;
9.70 - std::cout << "min min cut value: "<< min_min_cut_value << std::endl;
9.71 - std::cout << "max min cut value: "<< max_min_cut_value <<
9.72 - std::endl<< std::endl;
9.73 -
9.74 - return 0;
9.75 -}
10.1 --- a/src/work/jacint/preflow_hl3.h Mon Mar 01 17:24:34 2004 +0000
10.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
10.3 @@ -1,469 +0,0 @@
10.4 -// -*- C++ -*-
10.5 -/*
10.6 -preflow_hl3.h
10.7 -by jacint.
10.8 -
10.9 -Heuristics:
10.10 -
10.11 - suck gap : if there is a gap, then we put all
10.12 - nodes reachable from the relabelled node to level n
10.13 - 2 phase
10.14 - highest label
10.15 -
10.16 -The constructor runs the algorithm.
10.17 -
10.18 -Members:
10.19 -
10.20 -T maxFlow() : returns the value of a maximum flow
10.21 -
10.22 -T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e)
10.23 -
10.24 -FlowMap Flow() : returns the fixed maximum flow x
10.25 -
10.26 -void minCut(CutMap& M) : sets M to the characteristic vector of a
10.27 - minimum cut. M should be a map of bools initialized to false.
10.28 -
10.29 -void minMinCut(CutMap& M) : sets M to the characteristic vector of the
10.30 - minimum min cut. M should be a map of bools initialized to false.
10.31 -
10.32 -void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
10.33 - maximum min cut. M should be a map of bools initialized to false.
10.34 -
10.35 -*/
10.36 -
10.37 -#ifndef PREFLOW_HL3_H
10.38 -#define PREFLOW_HL3_H
10.39 -
10.40 -#include <vector>
10.41 -#include <stack>
10.42 -#include <queue>
10.43 -
10.44 -#include <time_measure.h> //for test
10.45 -
10.46 -namespace hugo {
10.47 -
10.48 - template <typename Graph, typename T,
10.49 - typename FlowMap=typename Graph::EdgeMap<T>,
10.50 - typename CapMap=typename Graph::EdgeMap<T> >
10.51 - class preflow_hl3 {
10.52 -
10.53 - typedef typename Graph::NodeIt NodeIt;
10.54 - typedef typename Graph::EdgeIt EdgeIt;
10.55 - typedef typename Graph::EachNodeIt EachNodeIt;
10.56 - typedef typename Graph::OutEdgeIt OutEdgeIt;
10.57 - typedef typename Graph::InEdgeIt InEdgeIt;
10.58 -
10.59 - Graph& G;
10.60 - NodeIt s;
10.61 - NodeIt t;
10.62 - FlowMap flow;
10.63 - CapMap& capacity;
10.64 - T value;
10.65 -
10.66 - public:
10.67 -
10.68 - double time; //for test
10.69 -
10.70 - preflow_hl3(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) :
10.71 - G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) {
10.72 -
10.73 - bool phase=0;
10.74 - int n=G.nodeNum();
10.75 - int b=n-2;
10.76 - /*
10.77 - b is a bound on the highest level of the stack.
10.78 - In the beginning it is at most n-2.
10.79 - */
10.80 -
10.81 - typename Graph::NodeMap<int> level(G,n);
10.82 - typename Graph::NodeMap<T> excess(G);
10.83 -
10.84 - std::vector<int> numb(n);
10.85 - /*
10.86 - The number of nodes on level i < n. It is
10.87 - initialized to n+1, because of the reverse_bfs-part.
10.88 - Needed only in phase 0.
10.89 - */
10.90 -
10.91 - std::vector<std::stack<NodeIt> > stack(n);
10.92 - //Stack of the active nodes in level i < n.
10.93 - //We use it in both phases.
10.94 -
10.95 -
10.96 - /*Reverse_bfs from t, to find the starting level.*/
10.97 - level.set(t,0);
10.98 - std::queue<NodeIt> bfs_queue;
10.99 - bfs_queue.push(t);
10.100 -
10.101 - while (!bfs_queue.empty()) {
10.102 -
10.103 - NodeIt v=bfs_queue.front();
10.104 - bfs_queue.pop();
10.105 - int l=level.get(v)+1;
10.106 -
10.107 - for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
10.108 - NodeIt w=G.tail(e);
10.109 - if ( level.get(w) == n ) {
10.110 - bfs_queue.push(w);
10.111 - ++numb[l];
10.112 - level.set(w, l);
10.113 - }
10.114 - }
10.115 - }
10.116 -
10.117 - level.set(s,n);
10.118 -
10.119 -
10.120 -
10.121 - /* Starting flow. It is everywhere 0 at the moment. */
10.122 - for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e)
10.123 - {
10.124 - T c=capacity.get(e);
10.125 - if ( c == 0 ) continue;
10.126 - NodeIt w=G.head(e);
10.127 - if ( level.get(w) < n ) {
10.128 - if ( excess.get(w) == 0 && w!=t ) stack[level.get(w)].push(w);
10.129 - flow.set(e, c);
10.130 - excess.set(w, excess.get(w)+c);
10.131 - }
10.132 - }
10.133 -
10.134 - /*
10.135 - End of preprocessing
10.136 - */
10.137 -
10.138 -
10.139 -
10.140 - /*
10.141 - Push/relabel on the highest level active nodes.
10.142 - */
10.143 - /*While there exists an active node.*/
10.144 - while ( true ) {
10.145 -
10.146 - if ( b == 0 ) {
10.147 - if ( phase ) break;
10.148 - phase=1;
10.149 - time=currTime();
10.150 -
10.151 - level.set(s,0);
10.152 -
10.153 - std::queue<NodeIt> bfs_queue;
10.154 - bfs_queue.push(s);
10.155 -
10.156 - while (!bfs_queue.empty()) {
10.157 -
10.158 - NodeIt v=bfs_queue.front();
10.159 - bfs_queue.pop();
10.160 - int l=level.get(v)+1;
10.161 -
10.162 - for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
10.163 - if ( capacity.get(e) == flow.get(e) ) continue;
10.164 - NodeIt u=G.tail(e);
10.165 - if ( level.get(u) == n ) {
10.166 - bfs_queue.push(u);
10.167 - level.set(u, l);
10.168 - if ( excess.get(u) > 0 ) stack[l].push(u);
10.169 - }
10.170 - }
10.171 -
10.172 - for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) {
10.173 - if ( 0 == flow.get(e) ) continue;
10.174 - NodeIt u=G.head(e);
10.175 - if ( level.get(u) == n ) {
10.176 - bfs_queue.push(u);
10.177 - level.set(u, l);
10.178 - if ( excess.get(u) > 0 ) stack[l].push(u);
10.179 - }
10.180 - }
10.181 - }
10.182 -
10.183 - b=n-2;
10.184 - }
10.185 -
10.186 - if ( stack[b].empty() ) --b;
10.187 - else {
10.188 -
10.189 - NodeIt w=stack[b].top();
10.190 - stack[b].pop();
10.191 - int lev=level.get(w);
10.192 - T exc=excess.get(w);
10.193 - int newlevel=n; //bound on the next level of w.
10.194 -
10.195 - for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
10.196 -
10.197 - if ( flow.get(e) == capacity.get(e) ) continue;
10.198 - NodeIt v=G.head(e);
10.199 - //e=wv
10.200 -
10.201 - if( lev > level.get(v) ) {
10.202 - /*Push is allowed now*/
10.203 -
10.204 - if ( excess.get(v)==0 && v !=t && v!=s )
10.205 - stack[level.get(v)].push(v);
10.206 - /*v becomes active.*/
10.207 -
10.208 - T cap=capacity.get(e);
10.209 - T flo=flow.get(e);
10.210 - T remcap=cap-flo;
10.211 -
10.212 - if ( remcap >= exc ) {
10.213 - /*A nonsaturating push.*/
10.214 -
10.215 - flow.set(e, flo+exc);
10.216 - excess.set(v, excess.get(v)+exc);
10.217 - exc=0;
10.218 - break;
10.219 -
10.220 - } else {
10.221 - /*A saturating push.*/
10.222 -
10.223 - flow.set(e, cap );
10.224 - excess.set(v, excess.get(v)+remcap);
10.225 - exc-=remcap;
10.226 - }
10.227 - } else if ( newlevel > level.get(v) ) newlevel = level.get(v);
10.228 -
10.229 - } //for out edges wv
10.230 -
10.231 -
10.232 - if ( exc > 0 ) {
10.233 - for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
10.234 -
10.235 - if( flow.get(e) == 0 ) continue;
10.236 - NodeIt v=G.tail(e);
10.237 - //e=vw
10.238 -
10.239 - if( lev > level.get(v) ) {
10.240 - /*Push is allowed now*/
10.241 -
10.242 - if ( excess.get(v)==0 && v !=t && v!=s )
10.243 - stack[level.get(v)].push(v);
10.244 - /*v becomes active.*/
10.245 -
10.246 - T flo=flow.get(e);
10.247 -
10.248 - if ( flo >= exc ) {
10.249 - /*A nonsaturating push.*/
10.250 -
10.251 - flow.set(e, flo-exc);
10.252 - excess.set(v, excess.get(v)+exc);
10.253 - exc=0;
10.254 - break;
10.255 - } else {
10.256 - /*A saturating push.*/
10.257 -
10.258 - excess.set(v, excess.get(v)+flo);
10.259 - exc-=flo;
10.260 - flow.set(e,0);
10.261 - }
10.262 - } else if ( newlevel > level.get(v) ) newlevel = level.get(v);
10.263 -
10.264 - } //for in edges vw
10.265 -
10.266 - } // if w still has excess after the out edge for cycle
10.267 -
10.268 - excess.set(w, exc);
10.269 -
10.270 -
10.271 - /*
10.272 - Relabel
10.273 - */
10.274 -
10.275 - if ( exc > 0 ) {
10.276 - //now 'lev' is the old level of w
10.277 -
10.278 - if ( phase ) {
10.279 - level.set(w,++newlevel);
10.280 - stack[newlevel].push(w);
10.281 - b=newlevel;
10.282 - } else {
10.283 -
10.284 - if ( newlevel >= n-2 || --numb[lev] == 0 ) {
10.285 -
10.286 - level.set(w,n);
10.287 -
10.288 - if ( newlevel < n ) {
10.289 -
10.290 - std::queue<NodeIt> bfs_queue;
10.291 - bfs_queue.push(w);
10.292 -
10.293 - while (!bfs_queue.empty()) {
10.294 -
10.295 - NodeIt v=bfs_queue.front();
10.296 - bfs_queue.pop();
10.297 -
10.298 - for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) {
10.299 - if ( capacity.get(e) == flow.get(e) ) continue;
10.300 - NodeIt u=G.head(e);
10.301 - if ( level.get(u) < n ) {
10.302 - bfs_queue.push(u);
10.303 - --numb[level.get(u)];
10.304 - level.set(u, n);
10.305 - }
10.306 - }
10.307 -
10.308 - for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
10.309 - if ( 0 == flow.get(e) ) continue;
10.310 - NodeIt u=G.tail(e);
10.311 - if ( level.get(u) < n ) {
10.312 - bfs_queue.push(u);
10.313 - --numb[level.get(u)];
10.314 - level.set(u, n);
10.315 - }
10.316 - }
10.317 - }
10.318 - }
10.319 - b=n-1;
10.320 -
10.321 - } else {
10.322 - level.set(w,++newlevel);
10.323 - stack[newlevel].push(w);
10.324 - ++numb[newlevel];
10.325 - b=newlevel;
10.326 - }
10.327 - }
10.328 - }
10.329 -
10.330 -
10.331 -
10.332 - } // if stack[b] is nonempty
10.333 -
10.334 - } // while(true)
10.335 -
10.336 -
10.337 - value = excess.get(t);
10.338 - /*Max flow value.*/
10.339 -
10.340 -
10.341 - } //void run()
10.342 -
10.343 -
10.344 -
10.345 -
10.346 -
10.347 - /*
10.348 - Returns the maximum value of a flow.
10.349 - */
10.350 -
10.351 - T maxFlow() {
10.352 - return value;
10.353 - }
10.354 -
10.355 -
10.356 -
10.357 - /*
10.358 - For the maximum flow x found by the algorithm,
10.359 - it returns the flow value on edge e, i.e. x(e).
10.360 - */
10.361 -
10.362 - T flowOnEdge(EdgeIt e) {
10.363 - return flow.get(e);
10.364 - }
10.365 -
10.366 -
10.367 -
10.368 - /*
10.369 - Returns the maximum flow x found by the algorithm.
10.370 - */
10.371 -
10.372 - FlowMap Flow() {
10.373 - return flow;
10.374 - }
10.375 -
10.376 -
10.377 -
10.378 -
10.379 - /*
10.380 - Returns the minimum min cut, by a bfs from s in the residual graph.
10.381 - */
10.382 -
10.383 - template<typename CutMap>
10.384 - void minCut(CutMap& M) {
10.385 -
10.386 - std::queue<NodeIt> queue;
10.387 -
10.388 - M.set(s,true);
10.389 - queue.push(s);
10.390 -
10.391 - while (!queue.empty()) {
10.392 - NodeIt w=queue.front();
10.393 - queue.pop();
10.394 -
10.395 - for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
10.396 - NodeIt v=G.head(e);
10.397 - if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
10.398 - queue.push(v);
10.399 - M.set(v, true);
10.400 - }
10.401 - }
10.402 -
10.403 - for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
10.404 - NodeIt v=G.tail(e);
10.405 - if (!M.get(v) && flow.get(e) > 0 ) {
10.406 - queue.push(v);
10.407 - M.set(v, true);
10.408 - }
10.409 - }
10.410 -
10.411 - }
10.412 -
10.413 - }
10.414 -
10.415 -
10.416 -
10.417 - /*
10.418 - Returns the maximum min cut, by a reverse bfs
10.419 - from t in the residual graph.
10.420 - */
10.421 -
10.422 - template<typename CutMap>
10.423 - void maxMinCut(CutMap& M) {
10.424 -
10.425 - std::queue<NodeIt> queue;
10.426 -
10.427 - M.set(t,true);
10.428 - queue.push(t);
10.429 -
10.430 - while (!queue.empty()) {
10.431 - NodeIt w=queue.front();
10.432 - queue.pop();
10.433 -
10.434 - for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
10.435 - NodeIt v=G.tail(e);
10.436 - if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
10.437 - queue.push(v);
10.438 - M.set(v, true);
10.439 - }
10.440 - }
10.441 -
10.442 - for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
10.443 - NodeIt v=G.head(e);
10.444 - if (!M.get(v) && flow.get(e) > 0 ) {
10.445 - queue.push(v);
10.446 - M.set(v, true);
10.447 - }
10.448 - }
10.449 - }
10.450 -
10.451 - for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v) {
10.452 - M.set(v, !M.get(v));
10.453 - }
10.454 -
10.455 - }
10.456 -
10.457 -
10.458 -
10.459 - template<typename CutMap>
10.460 - void minMinCut(CutMap& M) {
10.461 - minCut(M);
10.462 - }
10.463 -
10.464 -
10.465 -
10.466 - };
10.467 -}//namespace
10.468 -#endif
10.469 -
10.470 -
10.471 -
10.472 -
11.1 --- a/src/work/jacint/preflow_hl4.cc Mon Mar 01 17:24:34 2004 +0000
11.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
11.3 @@ -1,76 +0,0 @@
11.4 -#include <iostream>
11.5 -#include <fstream>
11.6 -
11.7 -#include <list_graph.hh>
11.8 -#include <dimacs.hh>
11.9 -#include <preflow_hl4.h>
11.10 -#include <time_measure.h>
11.11 -
11.12 -using namespace hugo;
11.13 -
11.14 -//Note, that preflow_hl4.h has a member NodeMap<bool> cut,
11.15 -//the construction of which slowing the running time by 1-10%.
11.16 -
11.17 -// Use a DIMACS max flow file as stdin.
11.18 -// read_dimacs_demo < dimacs_max_flow_file
11.19 -int main(int, char **) {
11.20 - typedef ListGraph::NodeIt NodeIt;
11.21 - typedef ListGraph::EachEdgeIt EachEdgeIt;
11.22 -
11.23 - ListGraph G;
11.24 - NodeIt s, t;
11.25 - ListGraph::EdgeMap<int> cap(G);
11.26 - readDimacsMaxFlow(std::cin, G, s, t, cap);
11.27 -
11.28 - std::cout << "preflow_hl4 demo ..." << std::endl;
11.29 -
11.30 - double mintime=1000000;
11.31 -
11.32 - for ( int i=1; i!=11; ++i ) {
11.33 - double pre_time=currTime();
11.34 - preflow_hl4<ListGraph, int> max_flow_test(G, s, t, cap);
11.35 - double post_time=currTime();
11.36 - if ( mintime > post_time-pre_time ) mintime = post_time-pre_time;
11.37 - }
11.38 -
11.39 - double pre_time=currTime();
11.40 - preflow_hl4<ListGraph, int> max_flow_test(G, s, t, cap);
11.41 - double post_time=currTime();
11.42 -
11.43 - ListGraph::NodeMap<bool> cut(G);
11.44 - max_flow_test.minCut(cut);
11.45 - int min_cut_value=0;
11.46 - for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
11.47 - if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);
11.48 - }
11.49 -
11.50 - ListGraph::NodeMap<bool> cut1(G);
11.51 - max_flow_test.minMinCut(cut1);
11.52 - int min_min_cut_value=0;
11.53 - for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
11.54 - if (cut.get(G.tail(e)) && !cut.get(G.head(e)))
11.55 - min_min_cut_value+=cap.get(e);
11.56 - }
11.57 -
11.58 - ListGraph::NodeMap<bool> cut2(G);
11.59 - max_flow_test.maxMinCut(cut2);
11.60 - int max_min_cut_value=0;
11.61 - for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
11.62 - if (cut2.get(G.tail(e)) && !cut2.get(G.head(e)))
11.63 - max_min_cut_value+=cap.get(e);
11.64 - }
11.65 -
11.66 - std::cout << "min time of 10 runs: " << mintime << " sec"<< std::endl;
11.67 - std::cout << "phase 0: " << max_flow_test.time-pre_time
11.68 - << " sec"<< std::endl;
11.69 - std::cout << "phase 1: " << post_time-max_flow_test.time
11.70 - << " sec"<< std::endl;
11.71 - std::cout << "flow value: "<< max_flow_test.maxFlow() << std::endl;
11.72 - std::cout << "min cut value: "<< min_cut_value << std::endl;
11.73 - std::cout << "min min cut value: "<< min_min_cut_value << std::endl;
11.74 - std::cout << "max min cut value: "<< max_min_cut_value <<
11.75 - std::endl<< std::endl;
11.76 -
11.77 -
11.78 - return 0;
11.79 -}
12.1 --- a/src/work/jacint/preflow_hl4.h Mon Mar 01 17:24:34 2004 +0000
12.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
12.3 @@ -1,602 +0,0 @@
12.4 -// -*- C++ -*-
12.5 -/*
12.6 -preflow_h5.h
12.7 -by jacint.
12.8 -Heuristics:
12.9 - 2 phase
12.10 - gap
12.11 - list 'level_list' on the nodes on level i implemented by hand
12.12 - highest label
12.13 - relevel: in phase 0, after BFS*n relabels, it runs a reverse
12.14 - bfs from t in the res graph to relevel the nodes reachable from t.
12.15 - BFS is initialized to 20
12.16 -
12.17 -Due to the last heuristic, this algorithm is quite fast on very
12.18 -sparse graphs, but relatively bad on even the dense graphs.
12.19 -
12.20 -'NodeMap<bool> cut' is a member, in this way we can count it fast, after
12.21 -the algorithm was run.
12.22 -
12.23 -The constructor runs the algorithm.
12.24 -
12.25 -Members:
12.26 -
12.27 -T maxFlow() : returns the value of a maximum flow
12.28 -
12.29 -T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e)
12.30 -
12.31 -FlowMap Flow() : returns the fixed maximum flow x
12.32 -
12.33 -void Flow(FlowMap& _flow ) : returns the fixed maximum flow x
12.34 -
12.35 -void minMinCut(CutMap& M) : sets M to the characteristic vector of the
12.36 - minimum min cut. M should be a map of bools initialized to false.
12.37 -
12.38 -void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
12.39 - maximum min cut. M should be a map of bools initialized to false.
12.40 -
12.41 -void minCut(CutMap& M) : fast function, sets M to the characteristic
12.42 - vector of a minimum cut.
12.43 -
12.44 -Different member from the other preflow_hl-s (here we have a member
12.45 -'NodeMap<bool> cut').
12.46 -
12.47 -CutMap minCut() : fast function, giving the characteristic
12.48 - vector of a minimum cut.
12.49 -
12.50 -
12.51 -*/
12.52 -
12.53 -#ifndef PREFLOW_HL4_H
12.54 -#define PREFLOW_HL4_H
12.55 -
12.56 -#define BFS 20
12.57 -
12.58 -#include <vector>
12.59 -#include <queue>
12.60 -
12.61 -#include <time_measure.h> //for test
12.62 -
12.63 -namespace hugo {
12.64 -
12.65 - template <typename Graph, typename T,
12.66 - typename FlowMap=typename Graph::EdgeMap<T>,
12.67 - typename CutMap=typename Graph::NodeMap<bool>,
12.68 - typename CapMap=typename Graph::EdgeMap<T> >
12.69 - class preflow_hl4 {
12.70 -
12.71 - typedef typename Graph::NodeIt NodeIt;
12.72 - typedef typename Graph::EdgeIt EdgeIt;
12.73 - typedef typename Graph::EachNodeIt EachNodeIt;
12.74 - typedef typename Graph::OutEdgeIt OutEdgeIt;
12.75 - typedef typename Graph::InEdgeIt InEdgeIt;
12.76 -
12.77 - Graph& G;
12.78 - NodeIt s;
12.79 - NodeIt t;
12.80 - FlowMap flow;
12.81 - CapMap& capacity;
12.82 - CutMap cut;
12.83 - T value;
12.84 -
12.85 - public:
12.86 -
12.87 - double time;
12.88 -
12.89 - preflow_hl4(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) :
12.90 - G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity),
12.91 - cut(G, false) {
12.92 -
12.93 - bool phase=0; //phase 0 is the 1st phase, phase 1 is the 2nd
12.94 - int n=G.nodeNum();
12.95 - int relabel=0;
12.96 - int heur=(int)BFS*n;
12.97 - int k=n-2;
12.98 - int b=k;
12.99 - /*
12.100 - b is a bound on the highest level of the stack.
12.101 - k is a bound on the highest nonempty level i < n.
12.102 - */
12.103 -
12.104 - typename Graph::NodeMap<int> level(G,n);
12.105 - typename Graph::NodeMap<T> excess(G);
12.106 -
12.107 - std::vector<NodeIt> active(n);
12.108 - typename Graph::NodeMap<NodeIt> next(G);
12.109 - //Stack of the active nodes in level i < n.
12.110 - //We use it in both phases.
12.111 -
12.112 - typename Graph::NodeMap<NodeIt> left(G);
12.113 - typename Graph::NodeMap<NodeIt> right(G);
12.114 - std::vector<NodeIt> level_list(n);
12.115 - /*
12.116 - Needed for the list of the nodes in level i.
12.117 - */
12.118 -
12.119 - /*Reverse_bfs from t, to find the starting level.*/
12.120 - level.set(t,0);
12.121 - std::queue<NodeIt> bfs_queue;
12.122 - bfs_queue.push(t);
12.123 -
12.124 - while (!bfs_queue.empty()) {
12.125 -
12.126 - NodeIt v=bfs_queue.front();
12.127 - bfs_queue.pop();
12.128 - int l=level.get(v)+1;
12.129 -
12.130 - for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
12.131 - NodeIt w=G.tail(e);
12.132 - if ( level.get(w) == n && w !=s ) {
12.133 - bfs_queue.push(w);
12.134 - NodeIt first=level_list[l];
12.135 - if ( first != 0 ) left.set(first,w);
12.136 - right.set(w,first);
12.137 - level_list[l]=w;
12.138 - level.set(w, l);
12.139 - }
12.140 - }
12.141 - }
12.142 -
12.143 - level.set(s,n);
12.144 -
12.145 -
12.146 - /* Starting flow. It is everywhere 0 at the moment. */
12.147 - for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e)
12.148 - {
12.149 - T c=capacity.get(e);
12.150 - if ( c == 0 ) continue;
12.151 - NodeIt w=G.head(e);
12.152 - if ( level.get(w) < n ) {
12.153 - if ( excess.get(w) == 0 && w!=t ) {
12.154 - next.set(w,active[level.get(w)]);
12.155 - active[level.get(w)]=w;
12.156 - }
12.157 - flow.set(e, c);
12.158 - excess.set(w, excess.get(w)+c);
12.159 - }
12.160 - }
12.161 - /*
12.162 - End of preprocessing
12.163 - */
12.164 -
12.165 -
12.166 - /*
12.167 - Push/relabel on the highest level active nodes.
12.168 - */
12.169 - while ( true ) {
12.170 -
12.171 - if ( b == 0 ) {
12.172 - if ( phase ) break;
12.173 -
12.174 - /*
12.175 - In the end of phase 0 we apply a bfs from s in
12.176 - the residual graph.
12.177 - */
12.178 - phase=1;
12.179 -
12.180 - //Now have a min cut.
12.181 - for( EachNodeIt v=G.template first<EachNodeIt>();
12.182 - v.valid(); ++v)
12.183 - if (level.get(v) >= n ) cut.set(v,true);
12.184 -
12.185 - time=currTime();
12.186 - level.set(s,0);
12.187 - std::queue<NodeIt> bfs_queue;
12.188 - bfs_queue.push(s);
12.189 -
12.190 - while (!bfs_queue.empty()) {
12.191 -
12.192 - NodeIt v=bfs_queue.front();
12.193 - bfs_queue.pop();
12.194 - int l=level.get(v)+1;
12.195 -
12.196 - for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
12.197 - if ( capacity.get(e) == flow.get(e) ) continue;
12.198 - NodeIt u=G.tail(e);
12.199 - if ( level.get(u) >= n ) {
12.200 - bfs_queue.push(u);
12.201 - level.set(u, l);
12.202 - if ( excess.get(u) > 0 ) {
12.203 - next.set(u,active[l]);
12.204 - active[l]=u;
12.205 - }
12.206 - }
12.207 - }
12.208 -
12.209 - for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) {
12.210 - if ( 0 == flow.get(e) ) continue;
12.211 - NodeIt u=G.head(e);
12.212 - if ( level.get(u) >= n ) {
12.213 - bfs_queue.push(u);
12.214 - level.set(u, l);
12.215 - if ( excess.get(u) > 0 ) {
12.216 - next.set(u,active[l]);
12.217 - active[l]=u;
12.218 - }
12.219 - }
12.220 - }
12.221 - }
12.222 - b=n-2;
12.223 - }
12.224 -
12.225 -
12.226 - if ( active[b] == 0 ) --b;
12.227 - else {
12.228 -
12.229 - NodeIt w=active[b];
12.230 - active[b]=next.get(w);
12.231 - int lev=level.get(w);
12.232 - T exc=excess.get(w);
12.233 - int newlevel=n; //bound on the next level of w.
12.234 -
12.235 - for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
12.236 -
12.237 - if ( flow.get(e) == capacity.get(e) ) continue;
12.238 - NodeIt v=G.head(e);
12.239 - //e=wv
12.240 -
12.241 - if( lev > level.get(v) ) {
12.242 - /*Push is allowed now*/
12.243 -
12.244 - if ( excess.get(v)==0 && v!=t && v!=s ) {
12.245 - int lev_v=level.get(v);
12.246 - next.set(v,active[lev_v]);
12.247 - active[lev_v]=v;
12.248 - }
12.249 -
12.250 - T cap=capacity.get(e);
12.251 - T flo=flow.get(e);
12.252 - T remcap=cap-flo;
12.253 -
12.254 - if ( remcap >= exc ) {
12.255 - /*A nonsaturating push.*/
12.256 -
12.257 - flow.set(e, flo+exc);
12.258 - excess.set(v, excess.get(v)+exc);
12.259 - exc=0;
12.260 - break;
12.261 -
12.262 - } else {
12.263 - /*A saturating push.*/
12.264 -
12.265 - flow.set(e, cap);
12.266 - excess.set(v, excess.get(v)+remcap);
12.267 - exc-=remcap;
12.268 - }
12.269 - } else if ( newlevel > level.get(v) ){
12.270 - newlevel = level.get(v);
12.271 - }
12.272 -
12.273 - } //for out edges wv
12.274 -
12.275 -
12.276 - if ( exc > 0 ) {
12.277 - for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
12.278 -
12.279 - if( flow.get(e) == 0 ) continue;
12.280 - NodeIt v=G.tail(e);
12.281 - //e=vw
12.282 -
12.283 - if( lev > level.get(v) ) {
12.284 - /*Push is allowed now*/
12.285 -
12.286 - if ( excess.get(v)==0 && v!=t && v!=s ) {
12.287 - int lev_v=level.get(v);
12.288 - next.set(v,active[lev_v]);
12.289 - active[lev_v]=v;
12.290 - }
12.291 -
12.292 - T flo=flow.get(e);
12.293 -
12.294 - if ( flo >= exc ) {
12.295 - /*A nonsaturating push.*/
12.296 -
12.297 - flow.set(e, flo-exc);
12.298 - excess.set(v, excess.get(v)+exc);
12.299 - exc=0;
12.300 - break;
12.301 - } else {
12.302 - /*A saturating push.*/
12.303 -
12.304 - excess.set(v, excess.get(v)+flo);
12.305 - exc-=flo;
12.306 - flow.set(e,0);
12.307 - }
12.308 - } else if ( newlevel > level.get(v) ) {
12.309 - newlevel = level.get(v);
12.310 - }
12.311 - } //for in edges vw
12.312 -
12.313 - } // if w still has excess after the out edge for cycle
12.314 -
12.315 - excess.set(w, exc);
12.316 -
12.317 - /*
12.318 - Relabel
12.319 - */
12.320 -
12.321 - if ( exc > 0 ) {
12.322 - //now 'lev' is the old level of w
12.323 -
12.324 - if ( phase ) {
12.325 - level.set(w,++newlevel);
12.326 - next.set(w,active[newlevel]);
12.327 - active[newlevel]=w;
12.328 - b=newlevel;
12.329 - } else {
12.330 - //unlacing
12.331 - NodeIt right_n=right.get(w);
12.332 - NodeIt left_n=left.get(w);
12.333 -
12.334 - if ( right_n != 0 ) {
12.335 - if ( left_n != 0 ) {
12.336 - right.set(left_n, right_n);
12.337 - left.set(right_n, left_n);
12.338 - } else {
12.339 - level_list[lev]=right_n;
12.340 - left.set(right_n, 0);
12.341 - }
12.342 - } else {
12.343 - if ( left_n != 0 ) {
12.344 - right.set(left_n, 0);
12.345 - } else {
12.346 - level_list[lev]=0;
12.347 - }
12.348 - }
12.349 - //unlacing ends
12.350 -
12.351 -
12.352 - if ( level_list[lev]==0 ) {
12.353 -
12.354 - for (int i=lev; i!=k ; ) {
12.355 - NodeIt v=level_list[++i];
12.356 - while ( v != 0 ) {
12.357 - level.set(v,n);
12.358 - v=right.get(v);
12.359 - }
12.360 - level_list[i]=0;
12.361 - }
12.362 -
12.363 - level.set(w,n);
12.364 -
12.365 - b=--lev;
12.366 - k=b;
12.367 -
12.368 - } else {
12.369 -
12.370 - if ( newlevel == n ) {
12.371 - level.set(w,n);
12.372 - } else {
12.373 -
12.374 - level.set(w,++newlevel);
12.375 - next.set(w,active[newlevel]);
12.376 - active[newlevel]=w;
12.377 - b=newlevel;
12.378 - if ( k < newlevel ) ++k;
12.379 - NodeIt first=level_list[newlevel];
12.380 - if ( first != 0 ) left.set(first,w);
12.381 - right.set(w,first);
12.382 - left.set(w,0);
12.383 - level_list[newlevel]=w;
12.384 - }
12.385 - }
12.386 -
12.387 - ++relabel;
12.388 - if ( relabel >= heur ) {
12.389 - relabel=0;
12.390 - b=n-2;
12.391 - k=b;
12.392 -
12.393 - for ( int i=1; i!=n; ++i ) {
12.394 - active[i]=0;
12.395 - level_list[i]=0;
12.396 - }
12.397 -
12.398 - //bfs from t in the res graph to relevel the nodes
12.399 - for( EachNodeIt v=G.template first<EachNodeIt>();
12.400 - v.valid(); ++v) level.set(v,n);
12.401 -
12.402 - level.set(t,0);
12.403 - std::queue<NodeIt> bfs_queue;
12.404 - bfs_queue.push(t);
12.405 -
12.406 - while (!bfs_queue.empty()) {
12.407 -
12.408 - NodeIt v=bfs_queue.front();
12.409 - bfs_queue.pop();
12.410 - int l=level.get(v)+1;
12.411 -
12.412 - for(InEdgeIt e=G.template first<InEdgeIt>(v);
12.413 - e.valid(); ++e) {
12.414 - if ( capacity.get(e) == flow.get(e) ) continue;
12.415 - NodeIt u=G.tail(e);
12.416 - if ( level.get(u) == n ) {
12.417 - bfs_queue.push(u);
12.418 - level.set(u, l);
12.419 - if ( excess.get(u) > 0 ) {
12.420 - next.set(u,active[l]);
12.421 - active[l]=u;
12.422 - }
12.423 - NodeIt first=level_list[l];
12.424 - if ( first != 0 ) left.set(first,w);
12.425 - right.set(w,first);
12.426 - left.set(w,0);
12.427 - level_list[l]=w;
12.428 - }
12.429 - }
12.430 -
12.431 -
12.432 - for(OutEdgeIt e=G.template first<OutEdgeIt>(v);
12.433 - e.valid(); ++e) {
12.434 - if ( 0 == flow.get(e) ) continue;
12.435 - NodeIt u=G.head(e);
12.436 - if ( level.get(u) == n ) {
12.437 - bfs_queue.push(u);
12.438 - level.set(u, l);
12.439 - if ( excess.get(u) > 0 ) {
12.440 - next.set(u,active[l]);
12.441 - active[l]=u;
12.442 - }
12.443 - NodeIt first=level_list[l];
12.444 - if ( first != 0 ) left.set(first,w);
12.445 - right.set(w,first);
12.446 - left.set(w,0);
12.447 - level_list[l]=w;
12.448 - }
12.449 - }
12.450 - }
12.451 -
12.452 - level.set(s,n);
12.453 - }
12.454 -
12.455 - } //phase 0
12.456 - } // if ( exc > 0 )
12.457 -
12.458 -
12.459 - } // if stack[b] is nonempty
12.460 -
12.461 - } // while(true)
12.462 -
12.463 -
12.464 - value = excess.get(t);
12.465 - /*Max flow value.*/
12.466 -
12.467 -
12.468 - } //void run()
12.469 -
12.470 -
12.471 -
12.472 -
12.473 -
12.474 - /*
12.475 - Returns the maximum value of a flow.
12.476 - */
12.477 -
12.478 - T maxFlow() {
12.479 - return value;
12.480 - }
12.481 -
12.482 -
12.483 -
12.484 - /*
12.485 - For the maximum flow x found by the algorithm, it returns the flow value on Edge e, i.e. x(e).
12.486 - */
12.487 -
12.488 - T flowOnEdge(EdgeIt e) {
12.489 - return flow.get(e);
12.490 - }
12.491 -
12.492 -
12.493 -
12.494 - FlowMap Flow() {
12.495 - return flow;
12.496 - }
12.497 -
12.498 -
12.499 -
12.500 - void Flow(FlowMap& _flow ) {
12.501 - for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v)
12.502 - _flow.set(v,flow.get(v));
12.503 - }
12.504 -
12.505 -
12.506 -
12.507 - /*
12.508 - Returns the minimum min cut, by a bfs from s in the residual graph.
12.509 - */
12.510 -
12.511 - template<typename _CutMap>
12.512 - void minMinCut(_CutMap& M) {
12.513 -
12.514 - std::queue<NodeIt> queue;
12.515 -
12.516 - M.set(s,true);
12.517 - queue.push(s);
12.518 -
12.519 - while (!queue.empty()) {
12.520 - NodeIt w=queue.front();
12.521 - queue.pop();
12.522 -
12.523 - for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
12.524 - NodeIt v=G.head(e);
12.525 - if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
12.526 - queue.push(v);
12.527 - M.set(v, true);
12.528 - }
12.529 - }
12.530 -
12.531 - for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
12.532 - NodeIt v=G.tail(e);
12.533 - if (!M.get(v) && flow.get(e) > 0 ) {
12.534 - queue.push(v);
12.535 - M.set(v, true);
12.536 - }
12.537 - }
12.538 -
12.539 - }
12.540 -
12.541 - }
12.542 -
12.543 -
12.544 -
12.545 - /*
12.546 - Returns the maximum min cut, by a reverse bfs
12.547 - from t in the residual graph.
12.548 - */
12.549 -
12.550 - template<typename _CutMap>
12.551 - void maxMinCut(_CutMap& M) {
12.552 -
12.553 - std::queue<NodeIt> queue;
12.554 -
12.555 - M.set(t,true);
12.556 - queue.push(t);
12.557 -
12.558 - while (!queue.empty()) {
12.559 - NodeIt w=queue.front();
12.560 - queue.pop();
12.561 -
12.562 - for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
12.563 - NodeIt v=G.tail(e);
12.564 - if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
12.565 - queue.push(v);
12.566 - M.set(v, true);
12.567 - }
12.568 - }
12.569 -
12.570 - for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
12.571 - NodeIt v=G.head(e);
12.572 - if (!M.get(v) && flow.get(e) > 0 ) {
12.573 - queue.push(v);
12.574 - M.set(v, true);
12.575 - }
12.576 - }
12.577 - }
12.578 -
12.579 - for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v) {
12.580 - M.set(v, !M.get(v));
12.581 - }
12.582 -
12.583 - }
12.584 -
12.585 -
12.586 - template<typename _CutMap>
12.587 - void minCut(_CutMap& M) {
12.588 - for( EachNodeIt v=G.template first<EachNodeIt>();
12.589 - v.valid(); ++v)
12.590 - M.set(v, cut.get(v));
12.591 - }
12.592 -
12.593 -
12.594 - CutMap minCut() {
12.595 - return cut;
12.596 - }
12.597 -
12.598 -
12.599 - };
12.600 -}//namespace marci
12.601 -#endif
12.602 -
12.603 -
12.604 -
12.605 -
13.1 --- a/src/work/jacint/preflow_jgraph.cc Mon Mar 01 17:24:34 2004 +0000
13.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
13.3 @@ -1,72 +0,0 @@
13.4 -#include <iostream>
13.5 -#include <fstream>
13.6 -
13.7 -#include <j_graph.h>
13.8 -#include <dimacs_jgraph.hh>
13.9 -#include <preflow_jgraph.h>
13.10 -#include <time_measure.h>
13.11 -
13.12 -using namespace hugo;
13.13 -
13.14 -// Use a DIMACS max flow file as stdin.
13.15 -// read_dimacs_demo < dimacs_max_flow_file
13.16 -int main(int, char **) {
13.17 - typedef JGraph::TrivNodeIt TrivNodeIt;
13.18 - typedef JGraph::EdgeIt EdgeIt;
13.19 -
13.20 - JGraph G;
13.21 - TrivNodeIt s, t;
13.22 - JGraph::EdgeMap<int> cap(G);
13.23 - readDimacsMaxFlow(std::cin, G, s, t, cap);
13.24 -
13.25 - std::cout << "preflow demo jacint ..." << std::endl;
13.26 -
13.27 - double mintime=1000000;
13.28 -
13.29 - for ( int i=1; i!=11; ++i ) {
13.30 - double pre_time=currTime();
13.31 - preflow<JGraph, int> max_flow_test(G, s, t, cap);
13.32 - double post_time=currTime();
13.33 - if ( mintime > post_time-pre_time ) mintime = post_time-pre_time;
13.34 - }
13.35 -
13.36 - double pre_time=currTime();
13.37 - preflow<JGraph, int> max_flow_test(G, s, t, cap);
13.38 - double post_time=currTime();
13.39 -
13.40 - JGraph::NodeMap<bool> cut(G);
13.41 - max_flow_test.minCut(cut);
13.42 - int min_cut_value=0;
13.43 - for(EdgeIt e=G.firstEdge(); e; G.next(e)) {
13.44 - if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);
13.45 - }
13.46 -
13.47 - JGraph::NodeMap<bool> cut1(G);
13.48 - max_flow_test.minMinCut(cut1);
13.49 - int min_min_cut_value=0;
13.50 - for(EdgeIt e=G.firstEdge(); e; G.next(e)) {
13.51 - if (cut.get(G.tail(e)) && !cut.get(G.head(e)))
13.52 - min_min_cut_value+=cap.get(e);
13.53 - }
13.54 -
13.55 - JGraph::NodeMap<bool> cut2(G);
13.56 - max_flow_test.maxMinCut(cut2);
13.57 - int max_min_cut_value=0;
13.58 - for(EdgeIt e=G.firstEdge(); e; G.next(e)) {
13.59 - if (cut2.get(G.tail(e)) && !cut2.get(G.head(e)))
13.60 - max_min_cut_value+=cap.get(e);
13.61 - }
13.62 -
13.63 - std::cout << "min time of 10 runs: " << mintime << " sec"<< std::endl;
13.64 - std::cout << "phase 0: " << max_flow_test.time-pre_time
13.65 - << " sec"<< std::endl;
13.66 - std::cout << "phase 1: " << post_time-max_flow_test.time
13.67 - << " sec"<< std::endl;
13.68 - std::cout << "flow value: "<< max_flow_test.maxFlow() << std::endl;
13.69 - std::cout << "min cut value: "<< min_cut_value << std::endl;
13.70 - std::cout << "min min cut value: "<< min_min_cut_value << std::endl;
13.71 - std::cout << "max min cut value: "<< max_min_cut_value <<
13.72 - std::endl<< std::endl;
13.73 -
13.74 - return 0;
13.75 -}
14.1 --- a/src/work/jacint/preflow_jgraph.h Mon Mar 01 17:24:34 2004 +0000
14.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
14.3 @@ -1,536 +0,0 @@
14.4 -// -*- C++ -*-
14.5 -/*
14.6 -preflow.h with 'j_graph interface'
14.7 -by jacint.
14.8 -Heuristics:
14.9 - 2 phase
14.10 - gap
14.11 - list 'level_list' on the nodes on level i implemented by hand
14.12 - stack 'active' on the active nodes on level i implemented by hand
14.13 - runs heuristic 'highest label' for H1*n relabels
14.14 - runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label'
14.15 -
14.16 -Parameters H0 and H1 are initialized to 20 and 10.
14.17 -
14.18 -The best preflow I could ever write.
14.19 -
14.20 -The constructor runs the algorithm.
14.21 -
14.22 -Members:
14.23 -
14.24 -T maxFlow() : returns the value of a maximum flow
14.25 -
14.26 -T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e)
14.27 -
14.28 -FlowMap Flow() : returns the fixed maximum flow x
14.29 -
14.30 -void minMinCut(CutMap& M) : sets M to the characteristic vector of the
14.31 - minimum min cut. M should be a map of bools initialized to false.
14.32 -
14.33 -void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
14.34 - maximum min cut. M should be a map of bools initialized to false.
14.35 -
14.36 -void minCut(CutMap& M) : sets M to the characteristic vector of
14.37 - a min cut. M should be a map of bools initialized to false.
14.38 -
14.39 -*/
14.40 -
14.41 -#ifndef PREFLOW_H
14.42 -#define PREFLOW_H
14.43 -
14.44 -#define H0 20
14.45 -#define H1 1
14.46 -
14.47 -#include <vector>
14.48 -#include <queue>
14.49 -
14.50 -#include<iostream>
14.51 -
14.52 -#include <time_measure.h>
14.53 -
14.54 -namespace hugo {
14.55 -
14.56 - template <typename Graph, typename T,
14.57 - typename FlowMap=typename Graph::EdgeMap<T>,
14.58 - typename CapMap=typename Graph::EdgeMap<T> >
14.59 - class preflow {
14.60 -
14.61 - typedef typename Graph::TrivNodeIt NodeIt;
14.62 - typedef typename Graph::TrivEdgeIt EdgeIt;
14.63 - typedef typename Graph::NodeIt EachNodeIt;
14.64 - typedef typename Graph::OutEdgeIt OutEdgeIt;
14.65 - typedef typename Graph::InEdgeIt InEdgeIt;
14.66 -
14.67 - Graph& G;
14.68 - NodeIt s;
14.69 - NodeIt t;
14.70 - FlowMap flow;
14.71 - CapMap& capacity;
14.72 - T value;
14.73 -
14.74 - public:
14.75 - double time;
14.76 - preflow(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity ) :
14.77 - G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity)
14.78 - {
14.79 -
14.80 - bool phase=0; //phase 0 is the 1st phase, phase 1 is the 2nd
14.81 - int n=G.numNodes();
14.82 - int heur0=(int)(H0*n); //time while running 'bound decrease'
14.83 - int heur1=(int)(H1*n); //time while running 'highest label'
14.84 - int heur=heur1; //starting time interval (#of relabels)
14.85 - bool what_heur=1;
14.86 - /*
14.87 - what_heur is 0 in case 'bound decrease'
14.88 - and 1 in case 'highest label'
14.89 - */
14.90 - bool end=false;
14.91 - /*
14.92 - Needed for 'bound decrease', 'true'
14.93 - means no active nodes are above bound b.
14.94 - */
14.95 - int relabel=0;
14.96 - int k=n-2; //bound on the highest level under n containing a node
14.97 - int b=k; //bound on the highest level under n of an active node
14.98 -
14.99 - typename Graph::NodeMap<int> level(G,n);
14.100 - typename Graph::NodeMap<T> excess(G);
14.101 -
14.102 - std::vector<NodeIt> active(n);
14.103 - typename Graph::NodeMap<NodeIt> next(G);
14.104 - //Stack of the active nodes in level i < n.
14.105 - //We use it in both phases.
14.106 -
14.107 - typename Graph::NodeMap<NodeIt> left(G);
14.108 - typename Graph::NodeMap<NodeIt> right(G);
14.109 - std::vector<NodeIt> level_list(n);
14.110 - /*
14.111 - List of the nodes in level i<n.
14.112 - */
14.113 -
14.114 - /*Reverse_bfs from t, to find the starting level.*/
14.115 - level.set(t,0);
14.116 - std::queue<NodeIt> bfs_queue;
14.117 - bfs_queue.push(t);
14.118 -
14.119 - while (!bfs_queue.empty()) {
14.120 -
14.121 - NodeIt v=bfs_queue.front();
14.122 - bfs_queue.pop();
14.123 - int l=level.get(v)+1;
14.124 -
14.125 - for(InEdgeIt e=G.firstIn(v); e; G.next(e)) {
14.126 - NodeIt w=G.tail(e);
14.127 - if ( level.get(w) == n && w != s ) {
14.128 - bfs_queue.push(w);
14.129 - NodeIt first=level_list[l];
14.130 - if ( first ) left.set(first,w);
14.131 - right.set(w,first);
14.132 - level_list[l]=w;
14.133 - level.set(w, l);
14.134 - }
14.135 - }
14.136 - }
14.137 -
14.138 - level.set(s,n);
14.139 -
14.140 -
14.141 - /* Starting flow. It is everywhere 0 at the moment. */
14.142 - for(OutEdgeIt e=G.firstOut(s); e; G.next(e))
14.143 - {
14.144 - T c=capacity.get(e);
14.145 - if ( c == 0 ) continue;
14.146 - NodeIt w=G.head(e);
14.147 - if ( level.get(w) < n ) {
14.148 - if ( excess.get(w) == 0 && w!=t ) {
14.149 - next.set(w,active[level.get(w)]);
14.150 - active[level.get(w)]=w;
14.151 - }
14.152 - flow.set(e, c);
14.153 - excess.set(w, excess.get(w)+c);
14.154 - }
14.155 - }
14.156 -
14.157 - /*
14.158 - End of preprocessing
14.159 - */
14.160 -
14.161 -
14.162 -
14.163 - /*
14.164 - Push/relabel on the highest level active nodes.
14.165 - */
14.166 - while ( true ) {
14.167 -
14.168 - if ( b == 0 ) {
14.169 - if ( phase ) break;
14.170 -
14.171 - if ( !what_heur && !end && k > 0 ) {
14.172 - b=k;
14.173 - end=true;
14.174 - } else {
14.175 - phase=1;
14.176 - time=currTime();
14.177 - level.set(s,0);
14.178 - std::queue<NodeIt> bfs_queue;
14.179 - bfs_queue.push(s);
14.180 -
14.181 - while (!bfs_queue.empty()) {
14.182 -
14.183 - NodeIt v=bfs_queue.front();
14.184 - bfs_queue.pop();
14.185 - int l=level.get(v)+1;
14.186 -
14.187 - for(InEdgeIt e=G.firstIn(v); e; G.next(e)) {
14.188 - if ( capacity.get(e) == flow.get(e) ) continue;
14.189 - NodeIt u=G.tail(e);
14.190 - if ( level.get(u) >= n ) {
14.191 - bfs_queue.push(u);
14.192 - level.set(u, l);
14.193 - if ( excess.get(u) > 0 ) {
14.194 - next.set(u,active[l]);
14.195 - active[l]=u;
14.196 - }
14.197 - }
14.198 - }
14.199 -
14.200 - for(OutEdgeIt e=G.firstOut(v); e; G.next(e)) {
14.201 - if ( 0 == flow.get(e) ) continue;
14.202 - NodeIt u=G.head(e);
14.203 - if ( level.get(u) >= n ) {
14.204 - bfs_queue.push(u);
14.205 - level.set(u, l);
14.206 - if ( excess.get(u) > 0 ) {
14.207 - next.set(u,active[l]);
14.208 - active[l]=u;
14.209 - }
14.210 - }
14.211 - }
14.212 - }
14.213 - b=n-2;
14.214 - }
14.215 -
14.216 - }
14.217 -
14.218 -
14.219 - if ( !active[b] ) --b;
14.220 - else {
14.221 - end=false;
14.222 -
14.223 - NodeIt w=active[b];
14.224 - active[b]=next.get(w);
14.225 - int lev=level.get(w);
14.226 - T exc=excess.get(w);
14.227 - int newlevel=n; //bound on the next level of w
14.228 -
14.229 - for(OutEdgeIt e=G.firstOut(w); e; G.next(e)) {
14.230 -
14.231 - if ( flow.get(e) == capacity.get(e) ) continue;
14.232 - NodeIt v=G.head(e);
14.233 - //e=wv
14.234 -
14.235 - if( lev > level.get(v) ) {
14.236 - /*Push is allowed now*/
14.237 -
14.238 - if ( excess.get(v)==0 && v!=t && v!=s ) {
14.239 - int lev_v=level.get(v);
14.240 - next.set(v,active[lev_v]);
14.241 - active[lev_v]=v;
14.242 - }
14.243 -
14.244 - T cap=capacity.get(e);
14.245 - T flo=flow.get(e);
14.246 - T remcap=cap-flo;
14.247 -
14.248 - if ( remcap >= exc ) {
14.249 - /*A nonsaturating push.*/
14.250 -
14.251 - flow.set(e, flo+exc);
14.252 - excess.set(v, excess.get(v)+exc);
14.253 - exc=0;
14.254 - break;
14.255 -
14.256 - } else {
14.257 - /*A saturating push.*/
14.258 -
14.259 - flow.set(e, cap);
14.260 - excess.set(v, excess.get(v)+remcap);
14.261 - exc-=remcap;
14.262 - }
14.263 - } else if ( newlevel > level.get(v) ){
14.264 - newlevel = level.get(v);
14.265 - }
14.266 -
14.267 - } //for out edges wv
14.268 -
14.269 -
14.270 - if ( exc > 0 ) {
14.271 - for( InEdgeIt e=G.firstIn(w); e; G.next(e)) {
14.272 -
14.273 - if( flow.get(e) == 0 ) continue;
14.274 - NodeIt v=G.tail(e);
14.275 - //e=vw
14.276 -
14.277 - if( lev > level.get(v) ) {
14.278 - /*Push is allowed now*/
14.279 -
14.280 - if ( excess.get(v)==0 && v!=t && v!=s ) {
14.281 - int lev_v=level.get(v);
14.282 - next.set(v,active[lev_v]);
14.283 - active[lev_v]=v;
14.284 - }
14.285 -
14.286 - T flo=flow.get(e);
14.287 -
14.288 - if ( flo >= exc ) {
14.289 - /*A nonsaturating push.*/
14.290 -
14.291 - flow.set(e, flo-exc);
14.292 - excess.set(v, excess.get(v)+exc);
14.293 - exc=0;
14.294 - break;
14.295 - } else {
14.296 -/*A saturating push.*/
14.297 -
14.298 - excess.set(v, excess.get(v)+flo);
14.299 - exc-=flo;
14.300 - flow.set(e,0);
14.301 - }
14.302 - } else if ( newlevel > level.get(v) ) {
14.303 - newlevel = level.get(v);
14.304 - }
14.305 - } //for in edges vw
14.306 -
14.307 - } // if w still has excess after the out edge for cycle
14.308 -
14.309 - excess.set(w, exc);
14.310 -
14.311 - /*
14.312 - Relabel
14.313 - */
14.314 -
14.315 -
14.316 - if ( exc > 0 ) {
14.317 - //now 'lev' is the old level of w
14.318 -
14.319 - if ( phase ) {
14.320 - level.set(w,++newlevel);
14.321 - next.set(w,active[newlevel]);
14.322 - active[newlevel]=w;
14.323 - b=newlevel;
14.324 - } else {
14.325 - //unlacing starts
14.326 - NodeIt right_n=right.get(w);
14.327 - NodeIt left_n=left.get(w);
14.328 -
14.329 - if ( right_n ) {
14.330 - if ( left_n ) {
14.331 - right.set(left_n, right_n);
14.332 - left.set(right_n, left_n);
14.333 - } else {
14.334 - level_list[lev]=right_n;
14.335 - left.set(right_n, NodeIt());
14.336 - }
14.337 - } else {
14.338 - if ( left_n ) {
14.339 - right.set(left_n, NodeIt());
14.340 - } else {
14.341 - level_list[lev]=NodeIt();
14.342 -
14.343 - }
14.344 - }
14.345 - //unlacing ends
14.346 -
14.347 - //gapping starts
14.348 - if ( !level_list[lev] ) {
14.349 -
14.350 - for (int i=lev; i!=k ; ) {
14.351 - NodeIt v=level_list[++i];
14.352 - while ( v ) {
14.353 - level.set(v,n);
14.354 - v=right.get(v);
14.355 - }
14.356 - level_list[i]=NodeIt();
14.357 - if ( !what_heur ) active[i]=NodeIt();
14.358 - }
14.359 -
14.360 - level.set(w,n);
14.361 - b=lev-1;
14.362 - k=b;
14.363 - //gapping ends
14.364 - } else {
14.365 -
14.366 - if ( newlevel == n ) level.set(w,n);
14.367 - else {
14.368 - level.set(w,++newlevel);
14.369 - next.set(w,active[newlevel]);
14.370 - active[newlevel]=w;
14.371 - if ( what_heur ) b=newlevel;
14.372 - if ( k < newlevel ) ++k;
14.373 - NodeIt first=level_list[newlevel];
14.374 - if ( first ) left.set(first,w);
14.375 - right.set(w,first);
14.376 - left.set(w,NodeIt());
14.377 - level_list[newlevel]=w;
14.378 - }
14.379 - }
14.380 -
14.381 -
14.382 - ++relabel;
14.383 - if ( relabel >= heur ) {
14.384 - relabel=0;
14.385 - if ( what_heur ) {
14.386 - what_heur=0;
14.387 - heur=heur0;
14.388 - end=false;
14.389 - } else {
14.390 - what_heur=1;
14.391 - heur=heur1;
14.392 - b=k;
14.393 - }
14.394 - }
14.395 - } //phase 0
14.396 -
14.397 -
14.398 - } // if ( exc > 0 )
14.399 -
14.400 -
14.401 - } // if stack[b] is nonempty
14.402 -
14.403 - } // while(true)
14.404 -
14.405 -
14.406 - value = excess.get(t);
14.407 - /*Max flow value.*/
14.408 -
14.409 - } //void run()
14.410 -
14.411 -
14.412 -
14.413 -
14.414 -
14.415 - /*
14.416 - Returns the maximum value of a flow.
14.417 - */
14.418 -
14.419 - T maxFlow() {
14.420 - return value;
14.421 - }
14.422 -
14.423 -
14.424 -
14.425 - /*
14.426 - For the maximum flow x found by the algorithm,
14.427 - it returns the flow value on edge e, i.e. x(e).
14.428 - */
14.429 -
14.430 - T flowOnEdge(EdgeIt e) {
14.431 - return flow.get(e);
14.432 - }
14.433 -
14.434 -
14.435 -
14.436 - FlowMap Flow() {
14.437 - return flow;
14.438 - }
14.439 -
14.440 -
14.441 -
14.442 - void Flow(FlowMap& _flow ) {
14.443 - for(EachNodeIt v=G.firstNode() ; v; G.next(v))
14.444 - _flow.set(v,flow.get(v));
14.445 - }
14.446 -
14.447 -
14.448 -
14.449 - /*
14.450 - Returns the minimum min cut, by a bfs from s in the residual graph.
14.451 - */
14.452 -
14.453 - template<typename _CutMap>
14.454 - void minMinCut(_CutMap& M) {
14.455 -
14.456 - std::queue<NodeIt> queue;
14.457 -
14.458 - M.set(s,true);
14.459 - queue.push(s);
14.460 -
14.461 - while (!queue.empty()) {
14.462 - NodeIt w=queue.front();
14.463 - queue.pop();
14.464 -
14.465 - for(OutEdgeIt e=G.firstOut(w) ; e; G.next(e)) {
14.466 - NodeIt v=G.head(e);
14.467 - if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
14.468 - queue.push(v);
14.469 - M.set(v, true);
14.470 - }
14.471 - }
14.472 -
14.473 - for(InEdgeIt e=G.firstIn(w) ; e; G.next(e)) {
14.474 - NodeIt v=G.tail(e);
14.475 - if (!M.get(v) && flow.get(e) > 0 ) {
14.476 - queue.push(v);
14.477 - M.set(v, true);
14.478 - }
14.479 - }
14.480 - }
14.481 - }
14.482 -
14.483 -
14.484 -
14.485 - /*
14.486 - Returns the maximum min cut, by a reverse bfs
14.487 - from t in the residual graph.
14.488 - */
14.489 -
14.490 - template<typename _CutMap>
14.491 - void maxMinCut(_CutMap& M) {
14.492 -
14.493 - std::queue<NodeIt> queue;
14.494 -
14.495 - M.set(t,true);
14.496 - queue.push(t);
14.497 -
14.498 - while (!queue.empty()) {
14.499 - NodeIt w=queue.front();
14.500 - queue.pop();
14.501 -
14.502 - for(InEdgeIt e=G.firstIn(w) ; e; G.next(e)) {
14.503 - NodeIt v=G.tail(e);
14.504 - if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
14.505 - queue.push(v);
14.506 - M.set(v, true);
14.507 - }
14.508 - }
14.509 -
14.510 - for(OutEdgeIt e=G.firstOut(w) ; e; G.next(e)) {
14.511 - NodeIt v=G.head(e);
14.512 - if (!M.get(v) && flow.get(e) > 0 ) {
14.513 - queue.push(v);
14.514 - M.set(v, true);
14.515 - }
14.516 - }
14.517 - }
14.518 -
14.519 - for(EachNodeIt v=G.firstNode() ; v; G.next(v)) {
14.520 - M.set(v, !M.get(v));
14.521 - }
14.522 -
14.523 - }
14.524 -
14.525 -
14.526 -
14.527 - template<typename CutMap>
14.528 - void minCut(CutMap& M) {
14.529 - minMinCut(M);
14.530 - }
14.531 -
14.532 -
14.533 - };
14.534 -}//namespace marci
14.535 -#endif
14.536 -
14.537 -
14.538 -
14.539 -
15.1 --- a/src/work/jacint/preflow_max_flow.cc Mon Mar 01 17:24:34 2004 +0000
15.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
15.3 @@ -1,40 +0,0 @@
15.4 -#include <iostream>
15.5 -#include <fstream>
15.6 -
15.7 -#include <list_graph.hh>
15.8 -#include <dimacs.hh>
15.9 -#include <preflow_max_flow.h>
15.10 -#include <time_measure.h>
15.11 -
15.12 -using namespace hugo;
15.13 -
15.14 -// Use a DIMACS max flow file as stdin.
15.15 -// read_dimacs_demo < dimacs_max_flow_file
15.16 -int main(int, char **) {
15.17 - typedef ListGraph::NodeIt NodeIt;
15.18 - typedef ListGraph::EachEdgeIt EachEdgeIt;
15.19 -typedef ListGraph::EachNodeIt EachNodeIt;
15.20 -
15.21 - ListGraph G;
15.22 - NodeIt s, t;
15.23 - ListGraph::EdgeMap<int> cap(G);
15.24 - readDimacsMaxFlow(std::cin, G, s, t, cap);
15.25 -
15.26 - std::cout << "preflow_max_flow demo ..." << std::endl;
15.27 -
15.28 - double pre_time=currTime();
15.29 - preflow_max_flow<ListGraph, int> max_flow_test(G, s, t, cap);
15.30 - ListGraph::NodeMap<bool> cut=max_flow_test.minCut();
15.31 - double post_time=currTime();
15.32 -
15.33 - int cut_value=0;
15.34 - for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
15.35 - if (cut.get(G.tail(e)) && !cut.get(G.head(e))) cut_value+=cap.get(e);
15.36 - }
15.37 -
15.38 - std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl;
15.39 - std::cout << "flow value: "<< max_flow_test.maxFlow() << std::endl;
15.40 - std::cout << "cut value: "<< cut_value << std::endl;
15.41 -
15.42 - return 0;
15.43 -}
16.1 --- a/src/work/jacint/preflow_max_flow.h Mon Mar 01 17:24:34 2004 +0000
16.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
16.3 @@ -1,358 +0,0 @@
16.4 -// -*- C++ -*-
16.5 -/*
16.6 -preflow_max_flow.h
16.7 -by jacint.
16.8 -Runs the first phase of preflow.h
16.9 -
16.10 -The constructor runs the algorithm.
16.11 -
16.12 -Members:
16.13 -
16.14 -T maxFlow() : returns the value of a maximum flow
16.15 -
16.16 -CutMap minCut() : returns the characteristic vector of a min cut.
16.17 -*/
16.18 -
16.19 -#ifndef PREFLOW_MAX_FLOW_H
16.20 -#define PREFLOW_MAX_FLOW_H
16.21 -
16.22 -#define H0 20
16.23 -#define H1 1
16.24 -
16.25 -#include <vector>
16.26 -#include <queue>
16.27 -
16.28 -namespace hugo {
16.29 -
16.30 - template <typename Graph, typename T,
16.31 - typename FlowMap=typename Graph::EdgeMap<T>,
16.32 - typename CapMap=typename Graph::EdgeMap<T>,
16.33 - typename CutMap=typename Graph::NodeMap<bool> >
16.34 - class preflow_max_flow {
16.35 -
16.36 - typedef typename Graph::NodeIt NodeIt;
16.37 - typedef typename Graph::EdgeIt EdgeIt;
16.38 - typedef typename Graph::EachNodeIt EachNodeIt;
16.39 - typedef typename Graph::OutEdgeIt OutEdgeIt;
16.40 - typedef typename Graph::InEdgeIt InEdgeIt;
16.41 -
16.42 - Graph& G;
16.43 - NodeIt s;
16.44 - NodeIt t;
16.45 - FlowMap flow;
16.46 - CapMap& capacity;
16.47 - CutMap cut;
16.48 - T value;
16.49 -
16.50 - public:
16.51 -
16.52 - preflow_max_flow(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity ) :
16.53 - G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), cut(_G, false)
16.54 - {
16.55 -
16.56 - int n=G.nodeNum();
16.57 - int heur0=(int)(H0*n); //time while running 'bound decrease'
16.58 - int heur1=(int)(H1*n); //time while running 'highest label'
16.59 - int heur=heur1; //starting time interval (#of relabels)
16.60 - bool what_heur=1;
16.61 - /*
16.62 - what_heur is 0 in case 'bound decrease'
16.63 - and 1 in case 'highest label'
16.64 - */
16.65 - bool end=false;
16.66 - /*
16.67 - Needed for 'bound decrease', 'true'
16.68 - means no active nodes are above bound b.
16.69 - */
16.70 - int relabel=0;
16.71 - int k=n-2; //bound on the highest level under n containing a node
16.72 - int b=k; //bound on the highest level under n of an active node
16.73 -
16.74 - typename Graph::NodeMap<int> level(G,n);
16.75 - typename Graph::NodeMap<T> excess(G);
16.76 -
16.77 - std::vector<NodeIt> active(n);
16.78 - typename Graph::NodeMap<NodeIt> next(G);
16.79 - //Stack of the active nodes in level i < n.
16.80 - //We use it in both phases.
16.81 -
16.82 - typename Graph::NodeMap<NodeIt> left(G);
16.83 - typename Graph::NodeMap<NodeIt> right(G);
16.84 - std::vector<NodeIt> level_list(n);
16.85 - /*
16.86 - List of the nodes in level i<n.
16.87 - */
16.88 -
16.89 - /*Reverse_bfs from t, to find the starting level.*/
16.90 - level.set(t,0);
16.91 - std::queue<NodeIt> bfs_queue;
16.92 - bfs_queue.push(t);
16.93 -
16.94 - while (!bfs_queue.empty()) {
16.95 -
16.96 - NodeIt v=bfs_queue.front();
16.97 - bfs_queue.pop();
16.98 - int l=level.get(v)+1;
16.99 -
16.100 - for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
16.101 - NodeIt w=G.tail(e);
16.102 - if ( level.get(w) == n && w != s ) {
16.103 - bfs_queue.push(w);
16.104 - NodeIt first=level_list[l];
16.105 - if ( first != 0 ) left.set(first,w);
16.106 - right.set(w,first);
16.107 - level_list[l]=w;
16.108 - level.set(w, l);
16.109 - }
16.110 - }
16.111 - }
16.112 -
16.113 - level.set(s,n);
16.114 -
16.115 -
16.116 - /* Starting flow. It is everywhere 0 at the moment. */
16.117 - for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e)
16.118 - {
16.119 - T c=capacity.get(e);
16.120 - if ( c == 0 ) continue;
16.121 - NodeIt w=G.head(e);
16.122 - if ( level.get(w) < n ) {
16.123 - if ( excess.get(w) == 0 && w!=t ) {
16.124 - next.set(w,active[level.get(w)]);
16.125 - active[level.get(w)]=w;
16.126 - }
16.127 - flow.set(e, c);
16.128 - excess.set(w, excess.get(w)+c);
16.129 - }
16.130 - }
16.131 -
16.132 - /*
16.133 - End of preprocessing
16.134 - */
16.135 -
16.136 -
16.137 -
16.138 - /*
16.139 - Push/relabel on the highest level active nodes.
16.140 - */
16.141 - while ( true ) {
16.142 -
16.143 - if ( b == 0 ) {
16.144 - if ( !what_heur && !end && k > 0 ) {
16.145 - b=k;
16.146 - end=true;
16.147 - } else break;
16.148 - }
16.149 -
16.150 -
16.151 - if ( active[b] == 0 ) --b;
16.152 - else {
16.153 - end=false;
16.154 -
16.155 - NodeIt w=active[b];
16.156 - active[b]=next.get(w);
16.157 - int lev=level.get(w);
16.158 - T exc=excess.get(w);
16.159 - int newlevel=n; //bound on the next level of w
16.160 -
16.161 - for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
16.162 -
16.163 - if ( flow.get(e) == capacity.get(e) ) continue;
16.164 - NodeIt v=G.head(e);
16.165 - //e=wv
16.166 -
16.167 - if( lev > level.get(v) ) {
16.168 - /*Push is allowed now*/
16.169 -
16.170 - if ( excess.get(v)==0 && v!=t && v!=s ) {
16.171 - int lev_v=level.get(v);
16.172 - next.set(v,active[lev_v]);
16.173 - active[lev_v]=v;
16.174 - }
16.175 -
16.176 - T cap=capacity.get(e);
16.177 - T flo=flow.get(e);
16.178 - T remcap=cap-flo;
16.179 -
16.180 - if ( remcap >= exc ) {
16.181 - /*A nonsaturating push.*/
16.182 -
16.183 - flow.set(e, flo+exc);
16.184 - excess.set(v, excess.get(v)+exc);
16.185 - exc=0;
16.186 - break;
16.187 -
16.188 - } else {
16.189 - /*A saturating push.*/
16.190 -
16.191 - flow.set(e, cap);
16.192 - excess.set(v, excess.get(v)+remcap);
16.193 - exc-=remcap;
16.194 - }
16.195 - } else if ( newlevel > level.get(v) ){
16.196 - newlevel = level.get(v);
16.197 - }
16.198 -
16.199 - } //for out edges wv
16.200 -
16.201 -
16.202 - if ( exc > 0 ) {
16.203 - for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
16.204 -
16.205 - if( flow.get(e) == 0 ) continue;
16.206 - NodeIt v=G.tail(e);
16.207 - //e=vw
16.208 -
16.209 - if( lev > level.get(v) ) {
16.210 - /*Push is allowed now*/
16.211 -
16.212 - if ( excess.get(v)==0 && v!=t && v!=s ) {
16.213 - int lev_v=level.get(v);
16.214 - next.set(v,active[lev_v]);
16.215 - active[lev_v]=v;
16.216 - }
16.217 -
16.218 - T flo=flow.get(e);
16.219 -
16.220 - if ( flo >= exc ) {
16.221 - /*A nonsaturating push.*/
16.222 -
16.223 - flow.set(e, flo-exc);
16.224 - excess.set(v, excess.get(v)+exc);
16.225 - exc=0;
16.226 - break;
16.227 - } else {
16.228 - /*A saturating push.*/
16.229 -
16.230 - excess.set(v, excess.get(v)+flo);
16.231 - exc-=flo;
16.232 - flow.set(e,0);
16.233 - }
16.234 - } else if ( newlevel > level.get(v) ) {
16.235 - newlevel = level.get(v);
16.236 - }
16.237 - } //for in edges vw
16.238 -
16.239 - } // if w still has excess after the out edge for cycle
16.240 -
16.241 - excess.set(w, exc);
16.242 -
16.243 - /*
16.244 - Relabel
16.245 - */
16.246 -
16.247 -
16.248 - if ( exc > 0 ) {
16.249 - //now 'lev' is the old level of w
16.250 -
16.251 - //unlacing starts
16.252 - NodeIt right_n=right.get(w);
16.253 - NodeIt left_n=left.get(w);
16.254 -
16.255 - if ( right_n != 0 ) {
16.256 - if ( left_n != 0 ) {
16.257 - right.set(left_n, right_n);
16.258 - left.set(right_n, left_n);
16.259 - } else {
16.260 - level_list[lev]=right_n;
16.261 - left.set(right_n, 0);
16.262 - }
16.263 - } else {
16.264 - if ( left_n != 0 ) {
16.265 - right.set(left_n, 0);
16.266 - } else {
16.267 - level_list[lev]=0;
16.268 -
16.269 - }
16.270 - }
16.271 - //unlacing ends
16.272 -
16.273 - //gapping starts
16.274 - if ( level_list[lev]==0 ) {
16.275 -
16.276 - for (int i=lev; i!=k ; ) {
16.277 - NodeIt v=level_list[++i];
16.278 - while ( v != 0 ) {
16.279 - level.set(v,n);
16.280 - v=right.get(v);
16.281 - }
16.282 - level_list[i]=0;
16.283 - if ( !what_heur ) active[i]=0;
16.284 - }
16.285 -
16.286 - level.set(w,n);
16.287 - b=lev-1;
16.288 - k=b;
16.289 - //gapping ends
16.290 - } else {
16.291 -
16.292 - if ( newlevel == n ) level.set(w,n);
16.293 - else {
16.294 - level.set(w,++newlevel);
16.295 - next.set(w,active[newlevel]);
16.296 - active[newlevel]=w;
16.297 - if ( what_heur ) b=newlevel;
16.298 - if ( k < newlevel ) ++k;
16.299 - NodeIt first=level_list[newlevel];
16.300 - if ( first != 0 ) left.set(first,w);
16.301 - right.set(w,first);
16.302 - left.set(w,0);
16.303 - level_list[newlevel]=w;
16.304 - }
16.305 - }
16.306 -
16.307 -
16.308 - ++relabel;
16.309 - if ( relabel >= heur ) {
16.310 - relabel=0;
16.311 - if ( what_heur ) {
16.312 - what_heur=0;
16.313 - heur=heur0;
16.314 - end=false;
16.315 - } else {
16.316 - what_heur=1;
16.317 - heur=heur1;
16.318 - b=k;
16.319 - }
16.320 - }
16.321 -
16.322 -
16.323 - } // if ( exc > 0 )
16.324 -
16.325 -
16.326 - } // if stack[b] is nonempty
16.327 -
16.328 - } // while(true)
16.329 -
16.330 -
16.331 -
16.332 - for( EachNodeIt v=G.template first<EachNodeIt>();
16.333 - v.valid(); ++v)
16.334 - if (level.get(v) >= n ) cut.set(v,true);
16.335 -
16.336 - value = excess.get(t);
16.337 - /*Max flow value.*/
16.338 -
16.339 - } //void run()
16.340 -
16.341 -
16.342 -
16.343 -
16.344 - T maxFlow() {
16.345 - return value;
16.346 - }
16.347 -
16.348 -
16.349 -
16.350 - CutMap minCut() {
16.351 - return cut;
16.352 - }
16.353 -
16.354 -
16.355 - };
16.356 -}//namespace
16.357 -#endif
16.358 -
16.359 -
16.360 -
16.361 -
17.1 --- a/src/work/jacint/preflow_param.cc Mon Mar 01 17:24:34 2004 +0000
17.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
17.3 @@ -1,47 +0,0 @@
17.4 -#include <iostream>
17.5 -#include <fstream>
17.6 -
17.7 -#include <list_graph.hh>
17.8 -#include <dimacs.hh>
17.9 -#include <preflow_param.h>
17.10 -#include <time_measure.h>
17.11 -
17.12 -using namespace hugo;
17.13 -
17.14 -// Use a DIMACS max flow file as stdin.
17.15 -// read_dimacs_demo < dimacs_max_flow_file
17.16 -int main(int, char **) {
17.17 - typedef ListGraph::NodeIt NodeIt;
17.18 - typedef ListGraph::EachEdgeIt EachEdgeIt;
17.19 -
17.20 - ListGraph G;
17.21 - NodeIt s, t;
17.22 - ListGraph::EdgeMap<int> cap(G);
17.23 - readDimacsMaxFlow(std::cin, G, s, t, cap);
17.24 -
17.25 - std::cout << "preflow parameters test ..." << std::endl;
17.26 -
17.27 - double min=1000000;
17.28 -
17.29 - int _j=0;
17.30 - int _k=0;
17.31 -
17.32 - for (int j=1; j!=40; ++j ){
17.33 - for (int k=1; k!=j; ++k ){
17.34 -
17.35 - double mintime=1000000;
17.36 -
17.37 - for ( int i=1; i!=4; ++i ) {
17.38 - double pre_time=currTime();
17.39 - preflow_param<ListGraph, int> max_flow_test(G, s, t, cap, j, k);
17.40 - double post_time=currTime();
17.41 - if ( mintime > post_time-pre_time ) mintime = post_time-pre_time;
17.42 - }
17.43 - if (min > mintime ) {min=mintime; _j=j; _k=k;}
17.44 - }
17.45 - }
17.46 -
17.47 - std::cout<<"Min. at ("<<_j<<","<<_k<<") in time "<<min<<std::endl;
17.48 -
17.49 - return 0;
17.50 -}
18.1 --- a/src/work/jacint/preflow_param.h Mon Mar 01 17:24:34 2004 +0000
18.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
18.3 @@ -1,541 +0,0 @@
18.4 -// -*- C++ -*-
18.5 -/*
18.6 -preflow_param.h
18.7 -by jacint.
18.8 -
18.9 -For testing the parameters H0, H1 of preflow.h
18.10 -
18.11 -The constructor runs the algorithm.
18.12 -
18.13 -Members:
18.14 -
18.15 -T maxFlow() : returns the value of a maximum flow
18.16 -
18.17 -T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e)
18.18 -
18.19 -FlowMap Flow() : returns the fixed maximum flow x
18.20 -
18.21 -void minMinCut(CutMap& M) : sets M to the characteristic vector of the
18.22 - minimum min cut. M should be a map of bools initialized to false.
18.23 -
18.24 -void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
18.25 - maximum min cut. M should be a map of bools initialized to false.
18.26 -
18.27 -void minCut(CutMap& M) : fast function, sets M to the characteristic
18.28 - vector of a minimum cut.
18.29 -
18.30 -Different member from the other preflow_hl-s (here we have a member
18.31 -'NodeMap<bool> cut').
18.32 -
18.33 -CutMap minCut() : fast function, giving the characteristic
18.34 - vector of a minimum cut.
18.35 -
18.36 -
18.37 -*/
18.38 -
18.39 -#ifndef PREFLOW_PARAM_H
18.40 -#define PREFLOW_PARAM_H
18.41 -
18.42 -#include <vector>
18.43 -#include <queue>
18.44 -
18.45 -#include <time_measure.h> //for test
18.46 -
18.47 -namespace hugo {
18.48 -
18.49 - template <typename Graph, typename T,
18.50 - typename FlowMap=typename Graph::EdgeMap<T>,
18.51 - typename CapMap=typename Graph::EdgeMap<T> >
18.52 - class preflow_param {
18.53 -
18.54 - typedef typename Graph::NodeIt NodeIt;
18.55 - typedef typename Graph::EdgeIt EdgeIt;
18.56 - typedef typename Graph::EachNodeIt EachNodeIt;
18.57 - typedef typename Graph::OutEdgeIt OutEdgeIt;
18.58 - typedef typename Graph::InEdgeIt InEdgeIt;
18.59 -
18.60 - Graph& G;
18.61 - NodeIt s;
18.62 - NodeIt t;
18.63 - FlowMap flow;
18.64 - CapMap& capacity;
18.65 - T value;
18.66 - int H0;
18.67 - int H1;
18.68 -
18.69 - public:
18.70 - double time;
18.71 -
18.72 - preflow_param(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity,
18.73 - int _H0, int _H1) :
18.74 - G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), H0(_H0), H1(_H1) {
18.75 -
18.76 - bool phase=0; //phase 0 is the 1st phase, phase 1 is the 2nd
18.77 - int n=G.nodeNum();
18.78 - int heur0=(int)(H0*n); //time while running 'bound decrease'
18.79 - int heur1=(int)(H1*n); //time while running 'highest label'
18.80 - int heur=heur1; //starting time interval (#of relabels)
18.81 - bool what_heur=1;
18.82 - /*
18.83 - what_heur is 0 in case 'bound decrease'
18.84 - and 1 in case 'highest label'
18.85 - */
18.86 - bool end=false; //for the 0 case
18.87 - /*
18.88 - Needed for 'bound decrease', 'true'
18.89 - means no active nodes are above bound b.
18.90 - */
18.91 - int relabel=0;
18.92 - int k=n-2;
18.93 - int b=k;
18.94 - /*
18.95 - b is a bound on the highest level of the stack.
18.96 - k is a bound on the highest nonempty level i < n.
18.97 - */
18.98 -
18.99 - typename Graph::NodeMap<int> level(G,n);
18.100 - typename Graph::NodeMap<T> excess(G);
18.101 -
18.102 - std::vector<NodeIt> active(n);
18.103 - typename Graph::NodeMap<NodeIt> next(G);
18.104 - //Stack of the active nodes in level i < n.
18.105 - //We use it in both phases.
18.106 -
18.107 - typename Graph::NodeMap<NodeIt> left(G);
18.108 - typename Graph::NodeMap<NodeIt> right(G);
18.109 - std::vector<NodeIt> level_list(n);
18.110 - /*
18.111 - Needed for the list of the nodes in level i.
18.112 - */
18.113 -
18.114 - /*Reverse_bfs from t, to find the starting level.*/
18.115 - level.set(t,0);
18.116 - std::queue<NodeIt> bfs_queue;
18.117 - bfs_queue.push(t);
18.118 -
18.119 - while (!bfs_queue.empty()) {
18.120 -
18.121 - NodeIt v=bfs_queue.front();
18.122 - bfs_queue.pop();
18.123 - int l=level.get(v)+1;
18.124 -
18.125 - for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
18.126 - NodeIt w=G.tail(e);
18.127 - if ( level.get(w) == n && w != s ) {
18.128 - bfs_queue.push(w);
18.129 - NodeIt first=level_list[l];
18.130 - if ( first != 0 ) left.set(first,w);
18.131 - right.set(w,first);
18.132 - level_list[l]=w;
18.133 - level.set(w, l);
18.134 - }
18.135 - }
18.136 - }
18.137 -
18.138 - level.set(s,n);
18.139 -
18.140 -
18.141 - /* Starting flow. It is everywhere 0 at the moment. */
18.142 - for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e)
18.143 - {
18.144 - T c=capacity.get(e);
18.145 - if ( c == 0 ) continue;
18.146 - NodeIt w=G.head(e);
18.147 - if ( level.get(w) < n ) {
18.148 - if ( excess.get(w) == 0 && w!=t ) {
18.149 - next.set(w,active[level.get(w)]);
18.150 - active[level.get(w)]=w;
18.151 - }
18.152 - flow.set(e, c);
18.153 - excess.set(w, excess.get(w)+c);
18.154 - }
18.155 - }
18.156 -
18.157 - /*
18.158 - End of preprocessing
18.159 - */
18.160 -
18.161 -
18.162 -
18.163 - /*
18.164 - Push/relabel on the highest level active nodes.
18.165 - */
18.166 - while ( true ) {
18.167 -
18.168 - if ( b == 0 ) {
18.169 - if ( phase ) break;
18.170 -
18.171 - if ( !what_heur && !end && k > 0 ) {
18.172 - b=k;
18.173 - end=true;
18.174 - } else {
18.175 - time=currTime();
18.176 - phase=1;
18.177 - level.set(s,0);
18.178 -
18.179 - std::queue<NodeIt> bfs_queue;
18.180 - bfs_queue.push(s);
18.181 -
18.182 - while (!bfs_queue.empty()) {
18.183 -
18.184 - NodeIt v=bfs_queue.front();
18.185 - bfs_queue.pop();
18.186 - int l=level.get(v)+1;
18.187 -
18.188 - for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
18.189 - if ( capacity.get(e) == flow.get(e) ) continue;
18.190 - NodeIt u=G.tail(e);
18.191 - if ( level.get(u) >= n ) {
18.192 - bfs_queue.push(u);
18.193 - level.set(u, l);
18.194 - if ( excess.get(u) > 0 ) {
18.195 - next.set(u,active[l]);
18.196 - active[l]=u;
18.197 - }
18.198 - }
18.199 - }
18.200 -
18.201 -
18.202 - for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) {
18.203 - if ( 0 == flow.get(e) ) continue;
18.204 - NodeIt u=G.head(e);
18.205 - if ( level.get(u) >= n ) {
18.206 - bfs_queue.push(u);
18.207 - level.set(u, l);
18.208 - if ( excess.get(u) > 0 ) {
18.209 - next.set(u,active[l]);
18.210 - active[l]=u;
18.211 - }
18.212 - }
18.213 - }
18.214 - }
18.215 - b=n-2;
18.216 - }
18.217 -
18.218 - }
18.219 -
18.220 -
18.221 - if ( active[b] == 0 ) --b;
18.222 - else {
18.223 - end=false; //needed only for phase 0, case hl2
18.224 -
18.225 - NodeIt w=active[b]; //w is a highest label active node.
18.226 - active[b]=next.get(w);
18.227 - int lev=level.get(w);
18.228 - T exc=excess.get(w);
18.229 - int newlevel=n; //In newlevel we bound the next level of w.
18.230 -
18.231 - for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
18.232 -
18.233 - if ( flow.get(e) == capacity.get(e) ) continue;
18.234 - NodeIt v=G.head(e);
18.235 - //e=wv
18.236 -
18.237 - if( lev > level.get(v) ) {
18.238 - /*Push is allowed now*/
18.239 -
18.240 - if ( excess.get(v)==0 && v!=t && v!=s ) {
18.241 - int lev_v=level.get(v);
18.242 - next.set(v,active[lev_v]);
18.243 - active[lev_v]=v;
18.244 - }
18.245 - /*v becomes active.*/
18.246 -
18.247 - T cap=capacity.get(e);
18.248 - T flo=flow.get(e);
18.249 - T remcap=cap-flo;
18.250 -
18.251 - if ( remcap >= exc ) {
18.252 - /*A nonsaturating push.*/
18.253 -
18.254 - flow.set(e, flo+exc);
18.255 - excess.set(v, excess.get(v)+exc);
18.256 - exc=0;
18.257 - break;
18.258 -
18.259 - } else {
18.260 - /*A saturating push.*/
18.261 -
18.262 - flow.set(e, cap);
18.263 - excess.set(v, excess.get(v)+remcap);
18.264 - exc-=remcap;
18.265 - }
18.266 - } else if ( newlevel > level.get(v) ){
18.267 - newlevel = level.get(v);
18.268 - }
18.269 -
18.270 - } //for out edges wv
18.271 -
18.272 -
18.273 - if ( exc > 0 ) {
18.274 - for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
18.275 -
18.276 - if( flow.get(e) == 0 ) continue;
18.277 - NodeIt v=G.tail(e);
18.278 - //e=vw
18.279 -
18.280 - if( lev > level.get(v) ) {
18.281 - /*Push is allowed now*/
18.282 -
18.283 - if ( excess.get(v)==0 && v!=t && v!=s ) {
18.284 - int lev_v=level.get(v);
18.285 - next.set(v,active[lev_v]);
18.286 - active[lev_v]=v;
18.287 - /*v becomes active.*/
18.288 - }
18.289 -
18.290 - T flo=flow.get(e);
18.291 -
18.292 - if ( flo >= exc ) {
18.293 - /*A nonsaturating push.*/
18.294 -
18.295 - flow.set(e, flo-exc);
18.296 - excess.set(v, excess.get(v)+exc);
18.297 - exc=0;
18.298 - break;
18.299 - } else {
18.300 - /*A saturating push.*/
18.301 -
18.302 - excess.set(v, excess.get(v)+flo);
18.303 - exc-=flo;
18.304 - flow.set(e,0);
18.305 - }
18.306 - } else if ( newlevel > level.get(v) ) {
18.307 - newlevel = level.get(v);
18.308 - }
18.309 - } //for in edges vw
18.310 -
18.311 - } // if w still has excess after the out edge for cycle
18.312 -
18.313 - excess.set(w, exc);
18.314 -
18.315 - /*
18.316 - Relabel
18.317 - */
18.318 -
18.319 -
18.320 - if ( exc > 0 ) {
18.321 - //now 'lev' is the old level of w
18.322 -
18.323 - if ( phase ) {
18.324 - level.set(w,++newlevel);
18.325 - next.set(w,active[newlevel]);
18.326 - active[newlevel]=w;
18.327 - b=newlevel;
18.328 - } else {
18.329 - //unlacing
18.330 - NodeIt right_n=right.get(w);
18.331 - NodeIt left_n=left.get(w);
18.332 -
18.333 - if ( right_n != 0 ) {
18.334 - if ( left_n != 0 ) {
18.335 - right.set(left_n, right_n);
18.336 - left.set(right_n, left_n);
18.337 - } else {
18.338 - level_list[lev]=right_n;
18.339 - left.set(right_n, 0);
18.340 - }
18.341 - } else {
18.342 - if ( left_n != 0 ) {
18.343 - right.set(left_n, 0);
18.344 - } else {
18.345 - level_list[lev]=0;
18.346 -
18.347 - }
18.348 - }
18.349 -
18.350 - if ( level_list[lev]==0 ) {
18.351 -
18.352 - for (int i=lev; i!=k ; ) {
18.353 - NodeIt v=level_list[++i];
18.354 - while ( v != 0 ) {
18.355 - level.set(v,n);
18.356 - v=right.get(v);
18.357 - }
18.358 - level_list[i]=0;
18.359 - if ( !what_heur ) active[i]=0;
18.360 - }
18.361 -
18.362 - level.set(w,n);
18.363 - b=lev-1;
18.364 - k=b;
18.365 -
18.366 - } else {
18.367 -
18.368 - if ( newlevel == n ) level.set(w,n);
18.369 - else {
18.370 - level.set(w,++newlevel);
18.371 - next.set(w,active[newlevel]);
18.372 - active[newlevel]=w;
18.373 - if ( what_heur ) b=newlevel;
18.374 - if ( k < newlevel ) ++k;
18.375 - NodeIt first=level_list[newlevel];
18.376 - if ( first != 0 ) left.set(first,w);
18.377 - right.set(w,first);
18.378 - left.set(w,0);
18.379 - level_list[newlevel]=w;
18.380 - }
18.381 - }
18.382 -
18.383 -
18.384 - ++relabel;
18.385 - if ( relabel >= heur ) {
18.386 - relabel=0;
18.387 - if ( what_heur ) {
18.388 - what_heur=0;
18.389 - heur=heur0;
18.390 - end=false;
18.391 - } else {
18.392 - what_heur=1;
18.393 - heur=heur1;
18.394 - b=k;
18.395 - }
18.396 - }
18.397 - } //phase 0
18.398 -
18.399 -
18.400 - } // if ( exc > 0 )
18.401 -
18.402 -
18.403 - } // if stack[b] is nonempty
18.404 -
18.405 - } // while(true)
18.406 -
18.407 -
18.408 - value = excess.get(t);
18.409 - /*Max flow value.*/
18.410 -
18.411 - } //void run()
18.412 -
18.413 -
18.414 -
18.415 -
18.416 -
18.417 - /*
18.418 - Returns the maximum value of a flow.
18.419 - */
18.420 -
18.421 - T maxFlow() {
18.422 - return value;
18.423 - }
18.424 -
18.425 -
18.426 -
18.427 - /*
18.428 - For the maximum flow x found by the algorithm,
18.429 - it returns the flow value on edge e, i.e. x(e).
18.430 - */
18.431 -
18.432 - T flowOnEdge(EdgeIt e) {
18.433 - return flow.get(e);
18.434 - }
18.435 -
18.436 -
18.437 -
18.438 - FlowMap Flow() {
18.439 - return flow;
18.440 - }
18.441 -
18.442 -
18.443 -
18.444 - void Flow(FlowMap& _flow ) {
18.445 - for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v)
18.446 - _flow.set(v,flow.get(v));
18.447 - }
18.448 -
18.449 -
18.450 -
18.451 - /*
18.452 - Returns the minimum min cut, by a bfs from s in the residual graph.
18.453 - */
18.454 -
18.455 - template<typename CutMap>
18.456 - void minCut(CutMap& M) {
18.457 -
18.458 - std::queue<NodeIt> queue;
18.459 -
18.460 - M.set(s,true);
18.461 - queue.push(s);
18.462 -
18.463 - while (!queue.empty()) {
18.464 - NodeIt w=queue.front();
18.465 - queue.pop();
18.466 -
18.467 - for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
18.468 - NodeIt v=G.head(e);
18.469 - if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
18.470 - queue.push(v);
18.471 - M.set(v, true);
18.472 - }
18.473 - }
18.474 -
18.475 - for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
18.476 - NodeIt v=G.tail(e);
18.477 - if (!M.get(v) && flow.get(e) > 0 ) {
18.478 - queue.push(v);
18.479 - M.set(v, true);
18.480 - }
18.481 - }
18.482 -
18.483 - }
18.484 -
18.485 - }
18.486 -
18.487 -
18.488 -
18.489 - /*
18.490 - Returns the maximum min cut, by a reverse bfs
18.491 - from t in the residual graph.
18.492 - */
18.493 -
18.494 - template<typename CutMap>
18.495 - void maxMinCut(CutMap& M) {
18.496 -
18.497 - std::queue<NodeIt> queue;
18.498 -
18.499 - M.set(t,true);
18.500 - queue.push(t);
18.501 -
18.502 - while (!queue.empty()) {
18.503 - NodeIt w=queue.front();
18.504 - queue.pop();
18.505 -
18.506 - for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
18.507 - NodeIt v=G.tail(e);
18.508 - if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
18.509 - queue.push(v);
18.510 - M.set(v, true);
18.511 - }
18.512 - }
18.513 -
18.514 - for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
18.515 - NodeIt v=G.head(e);
18.516 - if (!M.get(v) && flow.get(e) > 0 ) {
18.517 - queue.push(v);
18.518 - M.set(v, true);
18.519 - }
18.520 - }
18.521 - }
18.522 -
18.523 - for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v) {
18.524 - M.set(v, !M.get(v));
18.525 - }
18.526 -
18.527 - }
18.528 -
18.529 -
18.530 -
18.531 - template<typename CutMap>
18.532 - void minMinCut(CutMap& M) {
18.533 - minCut(M);
18.534 - }
18.535 -
18.536 -
18.537 -
18.538 - };
18.539 -}//namespace
18.540 -#endif
18.541 -
18.542 -
18.543 -
18.544 -
19.1 --- a/src/work/jacint/reverse_bfs.h Mon Mar 01 17:24:34 2004 +0000
19.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
19.3 @@ -1,89 +0,0 @@
19.4 -/*
19.5 -reverse_bfs
19.6 -by jacint
19.7 -Performs a bfs on the out Edges. It does not count predecessors,
19.8 -only the distances, but one can easily modify it to know the pred as well.
19.9 -
19.10 -Constructor:
19.11 -
19.12 -reverse_bfs(Graph& G, NodeIt t)
19.13 -
19.14 -
19.15 -
19.16 -Member functions:
19.17 -
19.18 -void run(): runs a reverse bfs from t
19.19 -
19.20 - The following function should be used after run() was already run.
19.21 -
19.22 -int dist(NodeIt v) : returns the distance from v to t. It is the number of nodes if t is not reachable from v.
19.23 -
19.24 -*/
19.25 -#ifndef REVERSE_BFS_H
19.26 -#define REVERSE_BFS_H
19.27 -
19.28 -#include <queue>
19.29 -#include <list_graph.hh>
19.30 -
19.31 -
19.32 -namespace marci {
19.33 -
19.34 - template <typename Graph>
19.35 - class reverse_bfs {
19.36 - typedef typename Graph::NodeIt NodeIt;
19.37 - typedef typename Graph::EachNodeIt EachNodeIt;
19.38 - typedef typename Graph::InEdgeIt InEdgeIt;
19.39 -
19.40 -
19.41 - Graph& G;
19.42 - NodeIt t;
19.43 - typename Graph::NodeMap<int> distance;
19.44 -
19.45 -
19.46 - public :
19.47 -
19.48 - /*
19.49 - The distance of the Nodes is n, except t for which it is 0.
19.50 - */
19.51 - reverse_bfs(Graph& _G, NodeIt _t) : G(_G), t(_t), distance(G, G.nodeNum()) {
19.52 - distance.set(t,0);
19.53 - }
19.54 -
19.55 - void run() {
19.56 -
19.57 - typename Graph::NodeMap<bool> reached(G, false);
19.58 - reached.set(t, true);
19.59 -
19.60 - std::queue<NodeIt> bfs_queue;
19.61 - bfs_queue.push(t);
19.62 -
19.63 - while (!bfs_queue.empty()) {
19.64 -
19.65 - NodeIt v=bfs_queue.front();
19.66 - bfs_queue.pop();
19.67 -
19.68 - for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
19.69 - NodeIt w=G.tail(e);
19.70 - if (!reached.get(w)) {
19.71 - bfs_queue.push(w);
19.72 - distance.set(w, distance.get(v)+1);
19.73 - reached.set(w, true);
19.74 - }
19.75 - }
19.76 - }
19.77 - }
19.78 -
19.79 -
19.80 -
19.81 - int dist(NodeIt v) {
19.82 - return distance.get(v);
19.83 - }
19.84 -
19.85 -
19.86 - };
19.87 -
19.88 -} // namespace hugo
19.89 -
19.90 -#endif //REVERSE_BFS_HH
19.91 -
19.92 -
20.1 --- a/src/work/jacint/reverse_bfs.hh Mon Mar 01 17:24:34 2004 +0000
20.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
20.3 @@ -1,94 +0,0 @@
20.4 -/*
20.5 -reverse_bfs
20.6 -by jacint
20.7 -Performs a bfs on the out Edges. It does not count predecessors,
20.8 -only the distances, but one can easily modify it to know the pred as well.
20.9 -
20.10 -Constructor:
20.11 -
20.12 -reverse_bfs(graph_type& G, NodeIt t)
20.13 -
20.14 -
20.15 -
20.16 -Member functions:
20.17 -
20.18 -void run(): runs a reverse bfs from t
20.19 -
20.20 - The following function should be used after run() was already run.
20.21 -
20.22 -int dist(NodeIt v) : returns the distance from v to t. It is the number of Nodes if t is not reachable from v.
20.23 -
20.24 -*/
20.25 -#ifndef REVERSE_BFS_HH
20.26 -#define REVERSE_BFS_HH
20.27 -
20.28 -#include <queue>
20.29 -
20.30 -#include <marci_graph_traits.hh>
20.31 -#include <marciMap.hh>
20.32 -
20.33 -
20.34 -
20.35 -namespace marci {
20.36 -
20.37 - template <typename graph_type>
20.38 - class reverse_bfs {
20.39 - typedef typename graph_traits<graph_type>::NodeIt NodeIt;
20.40 - //typedef typename graph_traits<graph_type>::EdgeIt EdgeIt;
20.41 - typedef typename graph_traits<graph_type>::EachNodeIt EachNodeIt;
20.42 - typedef typename graph_traits<graph_type>::InEdgeIt InEdgeIt;
20.43 -
20.44 -
20.45 - graph_type& G;
20.46 - NodeIt t;
20.47 -// NodeMap<graph_type, EdgeIt> pred;
20.48 - NodeMap<graph_type, int> distance;
20.49 -
20.50 -
20.51 - public :
20.52 -
20.53 - /*
20.54 - The distance of the Nodes is n, except t for which it is 0.
20.55 - */
20.56 - reverse_bfs(graph_type& _G, NodeIt _t) : G(_G), t(_t), distance(G, number_of(G.first_Node())) {
20.57 - distance.put(t,0);
20.58 - }
20.59 -
20.60 - void run() {
20.61 -
20.62 - NodeMap<graph_type, bool> reached(G, false);
20.63 - reached.put(t, true);
20.64 -
20.65 - std::queue<NodeIt> bfs_queue;
20.66 - bfs_queue.push(t);
20.67 -
20.68 - while (!bfs_queue.empty()) {
20.69 -
20.70 - NodeIt v=bfs_queue.front();
20.71 - bfs_queue.pop();
20.72 -
20.73 - for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
20.74 - NodeIt w=G.tail(e);
20.75 - if (!reached.get(w)) {
20.76 - bfs_queue.push(w);
20.77 - distance.put(w, distance.get(v)+1);
20.78 - reached.put(w, true);
20.79 - }
20.80 - }
20.81 - }
20.82 - }
20.83 -
20.84 -
20.85 -
20.86 - int dist(NodeIt v) {
20.87 - return distance.get(v);
20.88 - }
20.89 -
20.90 -
20.91 - };
20.92 -
20.93 -} // namespace hugo
20.94 -
20.95 -#endif //REVERSE_BFS_HH
20.96 -
20.97 -