COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/preflow_push_max_flow.h @ 97:a5127ecb2914

Last change on this file since 97:a5127ecb2914 was 97:a5127ecb2914, checked in by jacint, 16 years ago

javitott valtozat

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