COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/preflow_push_hl.h @ 83:efafe79a88d3

Last change on this file since 83:efafe79a88d3 was 83:efafe79a88d3, checked in by jacint, 17 years ago

debuggolt valtozatok

File size: 7.5 KB
Line 
1// -*- C++ -*-
2/*
3preflow_push_hl.h
4by jacint.
5Runs the highest label variant of the preflow push algorithm with
6running time O(n^2\sqrt(m)).
7
8Member functions:
9
10void run() : runs the algorithm
11
12 The following functions should be used after run() was already run.
13
14T maxflow() : returns the value of a maximum flow
15
16T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e)
17
18Graph::EdgeMap<T> allflow() : returns the fixed maximum flow x
19
20Graph::NodeMap<bool> mincut() : returns a
21     characteristic vector of a minimum cut. (An empty level
22     in the algorithm gives a minimum cut.)
23*/
24
25#ifndef PREFLOW_PUSH_HL_H
26#define PREFLOW_PUSH_HL_H
27
28#include <algorithm>
29#include <vector>
30#include <stack>
31
32#include <list_graph.hh>
33#include <reverse_bfs.h>
34
35namespace marci {
36
37  template <typename Graph, typename T>
38  class preflow_push_hl {
39   
40    typedef typename Graph::NodeIt NodeIt;
41    typedef typename Graph::EdgeIt EdgeIt;
42    typedef typename Graph::EachNodeIt EachNodeIt;
43    typedef typename Graph::OutEdgeIt OutEdgeIt;
44    typedef typename Graph::InEdgeIt InEdgeIt;
45   
46    Graph& G;
47    NodeIt s;
48    NodeIt t;
49    typename Graph::EdgeMap<T> flow;
50    typename Graph::EdgeMap<T> capacity;
51    T value;
52    typename Graph::NodeMap<bool> mincutvector;
53
54  public:
55
56    preflow_push_hl(Graph& _G, NodeIt _s, NodeIt _t,
57                    typename Graph::EdgeMap<T>& _capacity) :
58      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity),
59      mincutvector(_G, true) { }
60
61
62    /*
63      The run() function runs the highest label preflow-push,
64      running time: O(n^2\sqrt(m))
65    */
66    void run() {
67 
68      int i=0;//DELME
69
70      typename Graph::NodeMap<int> level(G);     
71      typename Graph::NodeMap<T> excess(G);     
72           
73      int n=G.nodeNum();   
74      int b=n-2;
75      /*
76        b is a bound on the highest level of an active node.
77        In the beginning it is at most n-2.
78      */
79
80      std::vector<std::stack<NodeIt> > stack(2*n-1);   
81      //Stack of the active nodes in level i.
82
83
84      /*Reverse_bfs from t, to find the starting level.*/
85      reverse_bfs<Graph> bfs(G, t);
86      bfs.run();
87      for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v)
88        {
89          level.set(v, bfs.dist(v));
90        }
91
92      std::cout << "the level of t is " << bfs.dist(t);//delme
93
94      level.set(s,n);
95
96
97      /* Starting flow. It is everywhere 0 at the moment. */     
98      for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e)
99        {
100          if ( capacity.get(e) > 0 ) {
101            NodeIt w=G.head(e);
102            flow.set(e, capacity.get(e));
103            stack[level.get(w)].push(w);
104            excess.set(w, excess.get(w)+capacity.get(e));
105          }
106        }
107
108
109      /*
110         End of preprocessing
111      */
112
113
114
115      /*
116        Push/relabel on the highest level active Nodes.
117      */
118       
119      /*While there exists active Node.*/
120      while (b) {
121
122        /*We decrease the bound if there is no active Node of level b.*/
123        if (stack[b].empty()) {
124          --b;
125        } else {
126
127          NodeIt w=stack[b].top();    //w is the highest label active Node.
128          stack[b].pop();                    //We delete w from the stack.
129       
130          int newlevel=2*n-2;                   //In newlevel we maintain the next level of w.
131       
132          for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
133            NodeIt v=G.head(e);
134            /*e is the Edge wv.*/
135
136            if (flow.get(e)<capacity.get(e)) {             
137              /*e is an Edge of the residual graph */
138
139              if(level.get(w)==level.get(v)+1) {     
140                /*Push is allowed now*/
141
142                if (capacity.get(e)-flow.get(e) > excess.get(w)) {       
143                  /*A nonsaturating push.*/
144                 
145                  if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
146                  /*v becomes active.*/
147
148                  //std::cout<<++i;
149                 
150                  flow.set(e, flow.get(e)+excess.get(w));
151                  excess.set(v, excess.get(v)+excess.get(w));
152                  excess.set(w,0);
153                  //std::cout << w << " " << v <<" elore elen nonsat pump "  << std::endl;
154                  break;
155                } else {
156                  /*A saturating push.*/
157
158                  if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
159                  /*v becomes active.*/
160
161                  excess.set(v, excess.get(v)+capacity.get(e)-flow.get(e));
162                  excess.set(w, excess.get(w)-capacity.get(e)+flow.get(e));
163                  flow.set(e, capacity.get(e));
164                  //std::cout << w<<" " <<v<<" elore elen sat pump "   << std::endl;
165                  if (excess.get(w)==0) break;
166                  /*If w is not active any more, then we go on to the next Node.*/
167                 
168                  //std::cout<<++i;
169                 
170                } // if (capacity.get(e)-flow.get(e) > excess.get(w))
171              } // if(level.get(w)==level.get(v)+1)
172           
173              else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
174           
175            } //if (flow.get(e)<capacity.get(e))
176         
177          } //for(OutEdgeIt e=G.first_OutEdge(w); e.valid(); ++e)
178         
179
180
181          for(InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
182            NodeIt v=G.tail(e);
183            /*e is the Edge vw.*/
184
185            if (excess.get(w)==0) break;
186            /*It may happen, that w became inactive in the first for cycle.*/           
187            if(flow.get(e)>0) {             
188              /*e is an Edge of the residual graph */
189
190              if(level.get(w)==level.get(v)+1) { 
191                /*Push is allowed now*/
192               
193                if (flow.get(e) > excess.get(w)) {
194                  /*A nonsaturating push.*/
195                 
196                  if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
197                  /*v becomes active.*/
198
199                  flow.set(e, flow.get(e)-excess.get(w));
200                  excess.set(v, excess.get(v)+excess.get(w));
201                  excess.set(w,0);
202                  //std::cout << v << " " << w << " vissza elen nonsat pump "     << std::endl;
203                  break;
204                } else {                                               
205                  /*A saturating push.*/
206                 
207                  if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
208                  /*v becomes active.*/
209                 
210                  excess.set(v, excess.get(v)+flow.get(e));
211                  excess.set(w, excess.get(w)-flow.get(e));
212                  flow.set(e,0);
213                  //std::cout << v <<" " << w << " vissza elen sat pump "     << std::endl;
214                  if (excess.get(w)==0) { break;}
215                } //if (flow.get(e) > excess.get(v))
216              } //if(level.get(w)==level.get(v)+1)
217             
218              else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
219             
220
221            } //if (flow.get(e)>0)
222
223          } //for
224
225
226          if (excess.get(w)>0) {
227            level.set(w,++newlevel);
228            stack[newlevel].push(w);
229            b=newlevel;
230            //std::cout << "The new level of " << w << " is "<< newlevel <<std::endl;
231          }
232
233
234        } //else
235       
236      } //while(b)
237
238      value = excess.get(t);
239      /*Max flow value.*/
240
241
242
243
244    } //void run()
245
246
247
248
249
250    /*
251      Returns the maximum value of a flow.
252     */
253
254    T maxflow() {
255      return value;
256    }
257
258
259
260    /*
261      For the maximum flow x found by the algorithm, it returns the flow value on Edge e, i.e. x(e).
262    */
263
264    T flowonEdge(EdgeIt e) {
265      return flow.get(e);
266    }
267
268
269
270    /*
271      Returns the maximum flow x found by the algorithm.
272    */
273
274    typename Graph::EdgeMap<T> allflow() {
275      return flow;
276    }
277
278
279
280    /*
281      Returns a minimum cut by using a reverse bfs from t in the residual graph.
282    */
283   
284    typename Graph::NodeMap<bool> mincut() {
285   
286      std::queue<NodeIt> queue;
287     
288      mincutvector.set(t,false);     
289      queue.push(t);
290
291      while (!queue.empty()) {
292        NodeIt w=queue.front();
293        queue.pop();
294
295        for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
296          NodeIt v=G.tail(e);
297          if (mincutvector.get(v) && flow.get(e) < capacity.get(e) ) {
298            queue.push(v);
299            mincutvector.set(v, false);
300          }
301        } // for
302
303        for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
304          NodeIt v=G.head(e);
305          if (mincutvector.get(v) && flow.get(e) > 0 ) {
306            queue.push(v);
307            mincutvector.set(v, false);
308          }
309        } // for
310
311      }
312
313      return mincutvector;
314   
315    }
316  };
317}//namespace marci
318#endif
319
320
321
322
Note: See TracBrowser for help on using the repository browser.