COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/preflow_push_max_flow.h @ 84:56e879edcca6

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

debuggolt valtozatok

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