COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/preflow_max_flow.h @ 109:fc5982b39e10

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

Flows with test files. The best is preflow.h

File size: 7.3 KB
Line 
1// -*- C++ -*-
2/*
3preflow_max_flow.h
4by jacint.
5Runs the first phase of preflow.h
6
7The constructor runs the algorithm.
8
9Members:
10
11T maxFlow() : returns the value of a maximum flow
12
13CutMap minCut() : returns the characteristic vector of a min cut.
14*/
15
16#ifndef PREFLOW_MAX_FLOW_H
17#define PREFLOW_MAX_FLOW_H
18
19#define H0 20
20#define H1 1
21
22#include <vector>
23#include <queue>
24
25namespace hugo {
26
27  template <typename Graph, typename T,
28    typename FlowMap=typename Graph::EdgeMap<T>,
29    typename CapMap=typename Graph::EdgeMap<T>,
30    typename CutMap=typename Graph::NodeMap<bool> >
31  class preflow_max_flow {
32   
33    typedef typename Graph::NodeIt NodeIt;
34    typedef typename Graph::EdgeIt EdgeIt;
35    typedef typename Graph::EachNodeIt EachNodeIt;
36    typedef typename Graph::OutEdgeIt OutEdgeIt;
37    typedef typename Graph::InEdgeIt InEdgeIt;
38   
39    Graph& G;
40    NodeIt s;
41    NodeIt t;
42    FlowMap flow;
43    CapMap& capacity; 
44    CutMap cut;
45    T value;
46
47  public:
48   
49    preflow_max_flow(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity ) :
50      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), cut(_G, false)
51    {
52
53      int n=G.nodeNum();
54      int heur0=(int)(H0*n);  //time while running 'bound decrease'
55      int heur1=(int)(H1*n);  //time while running 'highest label'
56      int heur=heur1;         //starting time interval (#of relabels)
57      bool what_heur=1;       
58      /*
59        what_heur is 0 in case 'bound decrease'
60        and 1 in case 'highest label'
61      */
62      bool end=false;     
63      /*
64        Needed for 'bound decrease', 'true'
65        means no active nodes are above bound b.
66      */
67      int relabel=0;
68      int k=n-2;  //bound on the highest level under n containing a node
69      int b=k;    //bound on the highest level under n of an active node
70     
71      typename Graph::NodeMap<int> level(G,n);     
72      typename Graph::NodeMap<T> excess(G);
73
74      std::vector<NodeIt> active(n);
75      typename Graph::NodeMap<NodeIt> next(G);
76      //Stack of the active nodes in level i < n.
77      //We use it in both phases.
78
79      typename Graph::NodeMap<NodeIt> left(G);
80      typename Graph::NodeMap<NodeIt> right(G);
81      std::vector<NodeIt> level_list(n);
82      /*
83        List of the nodes in level i<n.
84      */
85
86      /*Reverse_bfs from t, to find the starting level.*/
87      level.set(t,0);
88      std::queue<NodeIt> bfs_queue;
89      bfs_queue.push(t);
90
91      while (!bfs_queue.empty()) {
92
93        NodeIt v=bfs_queue.front();     
94        bfs_queue.pop();
95        int l=level.get(v)+1;
96
97        for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
98          NodeIt w=G.tail(e);
99          if ( level.get(w) == n && w != s ) {
100            bfs_queue.push(w);
101            NodeIt first=level_list[l];
102            if ( first != 0 ) left.set(first,w);
103            right.set(w,first);
104            level_list[l]=w;
105            level.set(w, l);
106          }
107        }
108      }
109     
110      level.set(s,n);
111     
112
113      /* Starting flow. It is everywhere 0 at the moment. */     
114      for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e)
115        {
116          T c=capacity.get(e);
117          if ( c == 0 ) continue;
118          NodeIt w=G.head(e);
119          if ( level.get(w) < n ) {       
120            if ( excess.get(w) == 0 && w!=t ) {
121              next.set(w,active[level.get(w)]);
122              active[level.get(w)]=w;
123            }
124            flow.set(e, c);
125            excess.set(w, excess.get(w)+c);
126          }
127        }
128
129      /*
130         End of preprocessing
131      */
132
133
134
135      /*
136        Push/relabel on the highest level active nodes.
137      */       
138      while ( true ) {
139       
140        if ( b == 0 ) {
141          if ( !what_heur && !end && k > 0 ) {
142            b=k;
143            end=true;
144          } else break;
145        }
146         
147         
148        if ( active[b] == 0 ) --b;
149        else {
150          end=false; 
151
152          NodeIt w=active[b];
153          active[b]=next.get(w);
154          int lev=level.get(w);
155          T exc=excess.get(w);
156          int newlevel=n;       //bound on the next level of w
157         
158          for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
159           
160            if ( flow.get(e) == capacity.get(e) ) continue;
161            NodeIt v=G.head(e);           
162            //e=wv         
163           
164            if( lev > level.get(v) ) {     
165              /*Push is allowed now*/
166             
167              if ( excess.get(v)==0 && v!=t && v!=s ) {
168                int lev_v=level.get(v);
169                next.set(v,active[lev_v]);
170                active[lev_v]=v;
171              }
172             
173              T cap=capacity.get(e);
174              T flo=flow.get(e);
175              T remcap=cap-flo;
176             
177              if ( remcap >= exc ) {       
178                /*A nonsaturating push.*/
179               
180                flow.set(e, flo+exc);
181                excess.set(v, excess.get(v)+exc);
182                exc=0;
183                break;
184               
185              } else {
186                /*A saturating push.*/
187               
188                flow.set(e, cap);
189                excess.set(v, excess.get(v)+remcap);
190                exc-=remcap;
191              }
192            } else if ( newlevel > level.get(v) ){
193              newlevel = level.get(v);
194            }       
195           
196          } //for out edges wv
197       
198       
199        if ( exc > 0 ) {       
200          for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
201           
202            if( flow.get(e) == 0 ) continue;
203            NodeIt v=G.tail(e); 
204            //e=vw
205           
206            if( lev > level.get(v) ) { 
207              /*Push is allowed now*/
208             
209              if ( excess.get(v)==0 && v!=t && v!=s ) {
210                int lev_v=level.get(v);
211                next.set(v,active[lev_v]);
212                active[lev_v]=v;
213              }
214             
215              T flo=flow.get(e);
216             
217              if ( flo >= exc ) {
218                /*A nonsaturating push.*/
219               
220                flow.set(e, flo-exc);
221                excess.set(v, excess.get(v)+exc);
222                exc=0;
223                break;
224              } else {                                               
225                /*A saturating push.*/
226               
227                excess.set(v, excess.get(v)+flo);
228                exc-=flo;
229                flow.set(e,0);
230              } 
231            } else if ( newlevel > level.get(v) ) {
232              newlevel = level.get(v);
233            }       
234          } //for in edges vw
235         
236        } // if w still has excess after the out edge for cycle
237       
238        excess.set(w, exc);
239         
240        /*
241          Relabel
242        */
243       
244
245        if ( exc > 0 ) {
246          //now 'lev' is the old level of w
247       
248          //unlacing starts
249          NodeIt right_n=right.get(w);
250          NodeIt left_n=left.get(w);
251         
252          if ( right_n != 0 ) {
253            if ( left_n != 0 ) {
254              right.set(left_n, right_n);
255              left.set(right_n, left_n);
256            } else {
257              level_list[lev]=right_n;   
258              left.set(right_n, 0);
259            }
260          } else {
261            if ( left_n != 0 ) {
262              right.set(left_n, 0);
263            } else {
264              level_list[lev]=0;   
265             
266            }
267          }
268          //unlacing ends
269         
270          //gapping starts
271          if ( level_list[lev]==0 ) {
272           
273            for (int i=lev; i!=k ; ) {
274              NodeIt v=level_list[++i];
275              while ( v != 0 ) {
276                level.set(v,n);
277                v=right.get(v);
278              }
279              level_list[i]=0;
280              if ( !what_heur ) active[i]=0;
281            }       
282           
283            level.set(w,n);
284            b=lev-1;
285            k=b;
286            //gapping ends
287          } else {
288           
289            if ( newlevel == n ) level.set(w,n);
290            else {
291              level.set(w,++newlevel);
292              next.set(w,active[newlevel]);
293              active[newlevel]=w;
294              if ( what_heur ) b=newlevel;
295              if ( k < newlevel ) ++k;
296              NodeIt first=level_list[newlevel];
297              if ( first != 0 ) left.set(first,w);
298              right.set(w,first);
299              left.set(w,0);
300              level_list[newlevel]=w;
301            }
302          }
303         
304         
305          ++relabel;
306          if ( relabel >= heur ) {
307            relabel=0;
308            if ( what_heur ) {
309              what_heur=0;
310              heur=heur0;
311              end=false;
312            } else {
313              what_heur=1;
314              heur=heur1;
315              b=k;
316            }
317          }
318         
319 
320        } // if ( exc > 0 )
321       
322       
323        }  // if stack[b] is nonempty
324       
325      } // while(true)
326
327
328     
329      for( EachNodeIt v=G.template first<EachNodeIt>();
330           v.valid(); ++v)
331        if (level.get(v) >= n ) cut.set(v,true);
332     
333      value = excess.get(t);
334      /*Max flow value.*/
335     
336    } //void run()
337
338
339
340
341    T maxFlow() {
342      return value;
343    }
344
345
346
347    CutMap minCut() {
348      return cut;
349    }
350
351
352  };
353}//namespace
354#endif
355
356
357
358
Note: See TracBrowser for help on using the repository browser.