1.1 --- a/src/work/jacint/preflow_push_hl.h Mon Feb 16 18:15:31 2004 +0000
1.2 +++ b/src/work/jacint/preflow_push_hl.h Tue Feb 17 08:59:49 2004 +0000
1.3 @@ -1,6 +1,6 @@
1.4 // -*- C++ -*-
1.5 /*
1.6 -preflow_push_hl.hh
1.7 +preflow_push_hl.h
1.8 by jacint.
1.9 Runs the highest label variant of the preflow push algorithm with
1.10 running time O(n^2\sqrt(m)).
1.11 @@ -13,11 +13,11 @@
1.12
1.13 T maxflow() : returns the value of a maximum flow
1.14
1.15 -T flowonEdge(Edge_iterator e) : for a fixed maximum flow x it returns x(e)
1.16 +T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e)
1.17
1.18 -EdgeMap<graph_type, T> allflow() : returns the fixed maximum flow x
1.19 +Graph::EdgeMap<T> allflow() : returns the fixed maximum flow x
1.20
1.21 -NodeMap<graph_type, bool> mincut() : returns a
1.22 +Graph::NodeMap<bool> mincut() : returns a
1.23 characteristic vector of a minimum cut. (An empty level
1.24 in the algorithm gives a minimum cut.)
1.25 */
1.26 @@ -29,6 +29,7 @@
1.27 #include <vector>
1.28 #include <stack>
1.29
1.30 +#include <list_graph.hh>
1.31 #include <reverse_bfs.h>
1.32
1.33 namespace marci {
1.34 @@ -41,9 +42,7 @@
1.35 typedef typename Graph::EachNodeIt EachNodeIt;
1.36 typedef typename Graph::OutEdgeIt OutEdgeIt;
1.37 typedef typename Graph::InEdgeIt InEdgeIt;
1.38 - typedef typename Graph::EachEdgeIt EachEdgeIt;
1.39
1.40 -
1.41 Graph& G;
1.42 NodeIt s;
1.43 NodeIt t;
1.44 @@ -52,14 +51,12 @@
1.45 T value;
1.46 typename Graph::NodeMap<bool> mincutvector;
1.47
1.48 -
1.49 public:
1.50
1.51 preflow_push_hl(Graph& _G, NodeIt _s, NodeIt _t,
1.52 typename Graph::EdgeMap<T>& _capacity) :
1.53 - G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), mincutvector(_G, true) { }
1.54 -
1.55 -
1.56 + G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity),
1.57 + mincutvector(_G, true) { }
1.58
1.59
1.60 /*
1.61 @@ -68,42 +65,44 @@
1.62 */
1.63 void run() {
1.64
1.65 - typename Graph::NodeMap<int> level(G); //level of Node
1.66 - typename Graph::NodeMap<T> excess(G); //excess of Node
1.67 + int i=0;//DELME
1.68 +
1.69 + typename Graph::NodeMap<int> level(G);
1.70 + typename Graph::NodeMap<T> excess(G);
1.71
1.72 - int n=G.nodeNum(); //number of Nodes
1.73 - int b=n;
1.74 - /*b is a bound on the highest level of an active Node. In the beginning it is at most n-2.*/
1.75 + int n=G.nodeNum();
1.76 + int b=n-2;
1.77 + /*
1.78 + b is a bound on the highest level of an active node.
1.79 + In the beginning it is at most n-2.
1.80 + */
1.81
1.82 - std::vector<std::stack<NodeIt> > stack(2*n-1); //Stack of the active Nodes in level i.
1.83 -
1.84 -
1.85 + std::vector<std::stack<NodeIt> > stack(2*n-1);
1.86 + //Stack of the active nodes in level i.
1.87
1.88
1.89 /*Reverse_bfs from t, to find the starting level.*/
1.90 -
1.91 reverse_bfs<Graph> bfs(G, t);
1.92 bfs.run();
1.93 - for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) {
1.94 - level.set(v, bfs.dist(v));
1.95 - //std::cout << "the level of " << v << " is " << bfs.dist(v);
1.96 - }
1.97 + for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v)
1.98 + {
1.99 + level.set(v, bfs.dist(v));
1.100 + }
1.101
1.102 - /*The level of s is fixed to n*/
1.103 + std::cout << "the level of t is " << bfs.dist(t);//delme
1.104 +
1.105 level.set(s,n);
1.106
1.107
1.108 -
1.109 -
1.110 -
1.111 - /* Starting flow. It is everywhere 0 at the moment. */
1.112 -
1.113 - for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i)
1.114 + /* Starting flow. It is everywhere 0 at the moment. */
1.115 + for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e)
1.116 {
1.117 - NodeIt w=G.head(i);
1.118 - flow.set(i, capacity.get(i));
1.119 - stack[bfs.dist(w)].push(w);
1.120 - excess.set(w, capacity.get(i));
1.121 + if ( capacity.get(e) > 0 ) {
1.122 + NodeIt w=G.head(e);
1.123 + flow.set(e, capacity.get(e));
1.124 + stack[level.get(w)].push(w);
1.125 + excess.set(w, excess.get(w)+capacity.get(e));
1.126 + }
1.127 }
1.128
1.129
1.130 @@ -145,6 +144,8 @@
1.131
1.132 if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
1.133 /*v becomes active.*/
1.134 +
1.135 + //std::cout<<++i;
1.136
1.137 flow.set(e, flow.get(e)+excess.get(w));
1.138 excess.set(v, excess.get(v)+excess.get(w));
1.139 @@ -164,6 +165,8 @@
1.140 if (excess.get(w)==0) break;
1.141 /*If w is not active any more, then we go on to the next Node.*/
1.142
1.143 + //std::cout<<++i;
1.144 +
1.145 } // if (capacity.get(e)-flow.get(e) > excess.get(w))
1.146 } // if(level.get(w)==level.get(v)+1)
1.147
2.1 --- a/src/work/jacint/preflow_push_max_flow.h Mon Feb 16 18:15:31 2004 +0000
2.2 +++ b/src/work/jacint/preflow_push_max_flow.h Tue Feb 17 08:59:49 2004 +0000
2.3 @@ -2,8 +2,8 @@
2.4 preflow_push_max_flow_h
2.5 by jacint.
2.6 Runs a preflow push algorithm with the modification,
2.7 -that we do not push on Nodes with level at least n.
2.8 -Moreover, if a level gets empty, we.set all Nodes above that
2.9 +that we do not push on nodes with level at least n.
2.10 +Moreover, if a level gets empty, we set all nodes above that
2.11 level to level n. Hence, in the end, we arrive at a maximum preflow
2.12 with value of a max flow value. An empty level gives a minimum cut.
2.13
2.14 @@ -15,7 +15,7 @@
2.15
2.16 T maxflow() : returns the value of a maximum flow
2.17
2.18 -NodeMap<Graph, bool> mincut(): returns a
2.19 +NodeMap<bool> mincut(): returns a
2.20 characteristic vector of a minimum cut.
2.21 */
2.22
2.23 @@ -51,31 +51,34 @@
2.24
2.25 public:
2.26
2.27 - preflow_push_max_flow(Graph& _G, NodeIt _s, NodeIt _t, typename Graph::EdgeMap<T>& _capacity) : G(_G), s(_s), t(_t), capacity(_capacity), mincutvector(_G, false) { }
2.28 + preflow_push_max_flow ( Graph& _G, NodeIt _s, NodeIt _t,
2.29 + typename Graph::EdgeMap<T>& _capacity) :
2.30 + G(_G), s(_s), t(_t), capacity(_capacity), mincutvector(_G, false) { }
2.31
2.32
2.33 /*
2.34 - The run() function runs a modified version of the highest label preflow-push, which only
2.35 + The run() function runs a modified version of the
2.36 + highest label preflow-push, which only
2.37 finds a maximum preflow, hence giving the value of a maximum flow.
2.38 */
2.39 void run() {
2.40
2.41 - typename Graph::EdgeMap<T> flow(G, 0); //the flow value, 0 everywhere
2.42 - typename Graph::NodeMap<int> level(G); //level of Node
2.43 - typename Graph::NodeMap<T> excess(G); //excess of Node
2.44 + typename Graph::EdgeMap<T> flow(G, 0);
2.45 + typename Graph::NodeMap<int> level(G);
2.46 + typename Graph::NodeMap<T> excess(G);
2.47
2.48 - int n=G.nodeNum(); //number of Nodes
2.49 + int n=G.nodeNum();
2.50 int b=n-2;
2.51 - /*b is a bound on the highest level of an active Node. In the beginning it is at most n-2.*/
2.52 + /*
2.53 + b is a bound on the highest level of an active Node.
2.54 + In the beginning it is at most n-2.
2.55 + */
2.56
2.57 - std::vector<int> numb(n); //The number of Nodes on level i < n.
2.58 -
2.59 - std::vector<std::stack<NodeIt> > stack(2*n-1); //Stack of the active Nodes in level i.
2.60 -
2.61 -
2.62 + std::vector<int> numb(n); //The number of Nodes on level i < n.
2.63 + std::vector<std::stack<NodeIt> > stack(2*n-1);
2.64 + //Stack of the active Nodes in level i.
2.65
2.66 /*Reverse_bfs from t, to find the starting level.*/
2.67 -
2.68 reverse_bfs<Graph> bfs(G, t);
2.69 bfs.run();
2.70 for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v)
2.71 @@ -85,28 +88,25 @@
2.72 ++numb[dist];
2.73 }
2.74
2.75 - /*The level of s is fixed to n*/
2.76 level.set(s,n);
2.77
2.78 -
2.79 /* Starting flow. It is everywhere 0 at the moment. */
2.80 -
2.81 - for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i)
2.82 + for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e)
2.83 {
2.84 - NodeIt w=G.head(i);
2.85 - flow.set(i, capacity.get(i));
2.86 - stack[bfs.dist(w)].push(w);
2.87 - excess.set(w, capacity.get(i));
2.88 + if ( capacity.get(e) > 0 ) {
2.89 + NodeIt w=G.head(e);
2.90 + flow.set(e, capacity.get(e));
2.91 + stack[level.get(w)].push(w);
2.92 + excess.set(w, excess.get(w)+capacity.get(e));
2.93 + }
2.94 }
2.95
2.96 -
2.97 /*
2.98 End of preprocessing
2.99 */
2.100
2.101
2.102
2.103 -
2.104 /*
2.105 Push/relabel on the highest level active Nodes.
2.106 */
2.107 @@ -114,7 +114,7 @@
2.108 /*While there exists an active Node.*/
2.109 while (b) {
2.110
2.111 - /*We decrease the bound if there is no active Node of level b.*/
2.112 + /*We decrease the bound if there is no active node of level b.*/
2.113 if (stack[b].empty()) {
2.114 --b;
2.115 } else {