COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/preflow_push.hh @ 294:f0ff6981d4fd

Last change on this file since 294:f0ff6981d4fd was 119:9b3345f9d8ed, checked in by athos, 21 years ago

Alpar, nezz bele

File size: 11.1 KB
Line 
1#ifndef PREFLOW_PUSH_HH
2#define PREFLOW_PUSH_HH
3
4#include <algorithm>
5#include <list>
6#include <vector>
7//#include "pf_hiba.hh"
8//#include <marci_list_graph.hh>
9//#include <marci_graph_traits.hh>
10
11#include <reverse_bfs.hh>
12
13using namespace std;
14
15namespace hugo {
16
17  template <typename graph_type, typename T>
18  class preflow_push {
19
20    //Hasznos typedef-ek
21    typedef typename graph_type::NodeIt NodeIt;
22    typedef typename graph_type::EdgeIt EdgeIt;
23    typedef typename graph_type::EachNodeIt EachNodeIt;
24    typedef typename graph_type::EachEdgeIt EachEdgeIt;
25    typedef typename graph_type::OutEdgeIt OutEdgeIt;
26    typedef typename graph_type::InEdgeIt InEdgeIt;
27    typedef typename graph_type::SymEdgeIt SymEdgeIt;
28
29
30
31    /*
32    typedef graph_traits<graph_type>::node_iterator node_iterator;
33    typedef graph_traits<graph_type>::EdgeIt EdgeIt;
34    typedef graph_traits<graph_type>::each_node_iterator each_node_iterator;
35    typedef graph_traits<graph_type>::each_EdgeIt each_EdgeIt;
36    typedef graph_traits<graph_type>::out_EdgeIt out_EdgeIt;
37    typedef graph_traits<graph_type>::InEdgeIt InEdgeIt;
38    typedef graph_traits<graph_type>::sym_EdgeIt sym_EdgeIt;
39    */
40
41    //---------------------------------------------
42    //Parameters of the algorithm
43    //---------------------------------------------
44    //Fully examine an active node until excess becomes 0
45    enum node_examination_t {examine_full, examine_to_relabel};
46    //No more implemented yet:, examine_only_one_edge};
47    node_examination_t node_examination;
48    //Which implementation to be used
49    enum implementation_t {impl_fifo, impl_highest_label};
50    //No more implemented yet:};
51    implementation_t implementation;
52    //---------------------------------------------
53    //Parameters of the algorithm
54    //---------------------------------------------
55 
56  private:
57    //input
58    graph_type& G;
59    NodeIt s;
60    NodeIt t;
61    typename graph_type::EdgeMap<T> &capacity;
62    //typename graph_type::EdgeMap<T>  &capacity;
63    //output
64    //typename graph_type::EdgeMap<T> 
65    typename graph_type::EdgeMap<T> preflow;
66    T maxflow_value;
67 
68    //auxiliary variables for computation
69    int number_of_nodes;
70   
71   
72    typename graph_type::NodeMap<int> level;
73    typename graph_type::NodeMap<T> excess;
74    //node_property_vector<graph_type, int> level;
75    //node_property_vector<graph_type, T> excess;
76   
77    //Number of nodes on each level
78    vector<int> num_of_nodes_on_level;
79   
80    //For the FIFO implementation
81    list<NodeIt> fifo_nodes;
82    //For 'highest label' implementation
83    int highest_active;
84    //int second_highest_active;
85    vector< list<NodeIt> > active_nodes;
86
87  public:
88 
89    //Constructing the object using the graph, source, sink and capacity vector
90    preflow_push(
91                      graph_type& _G,
92                      NodeIt _s,
93                      NodeIt _t,
94                      typename graph_type::EdgeMap<T> & _capacity)
95      : G(_G), s(_s), t(_t),
96        capacity(_capacity),
97        preflow(_G),
98        //Counting the number of nodes
99        //number_of_nodes(count(G.first<EachNodeIt>())),
100        number_of_nodes(G.nodeNum()),
101
102        level(_G),
103        excess(_G)//,
104        // Default constructor: active_nodes()
105    {
106      //Simplest parameter settings
107      node_examination = examine_full;//examine_to_relabel;//
108      //Which implementation to be usedexamine_full
109      implementation = impl_highest_label;//impl_fifo;
110 
111      //
112      num_of_nodes_on_level.resize(2*number_of_nodes-1);
113      num_of_nodes_on_level.clear();
114
115      switch(implementation){
116      case impl_highest_label :{
117        active_nodes.resize(2*number_of_nodes-1);
118        active_nodes.clear();
119        break;
120      }
121      default:
122        break;
123      }
124
125    }
126
127    //Returns the value of a maximal flow
128    T run();
129 
130    typename graph_type::EdgeMap<T>  getmaxflow(){
131      return preflow;
132    }
133
134
135  private:
136    //For testing purposes only
137    //Lists the node_properties
138    void write_property_vector(typename graph_type::NodeMap<T> a,
139                               //node_property_vector<graph_type, T> a,
140                               char* prop_name="property"){
141      for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
142        cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a.get(i)<<endl;
143      }
144      cout<<endl;
145    }
146
147    //Modifies the excess of the node and makes sufficient changes
148    void modify_excess(const NodeIt& a ,T v){
149        T old_value=excess.get(a);
150        excess.set(a,old_value+v);
151    }
152 
153    //This private procedure is supposed to modify the preflow on edge j
154    //by value v (which can be positive or negative as well)
155    //and maintain the excess on the head and tail
156    //Here we do not check whether this is possible or not
157    void modify_preflow(EdgeIt j, const T& v){
158
159      //Auxiliary variable
160      T old_value;
161       
162      //Modifiyng the edge
163      old_value=preflow.get(j);
164      preflow.set(j,old_value+v);
165
166
167      //Modifiyng the head
168      modify_excess(G.head(j),v);
169       
170      //Modifiyng the tail
171      modify_excess(G.tail(j),-v);
172
173    }
174
175    //Gives the active node to work with
176    //(depending on the implementation to be used)
177    NodeIt get_active_node(){
178     
179
180      switch(implementation) {
181      case impl_highest_label : {
182
183        //First need to find the highest label for which there"s an active node
184        while( highest_active>=0 && active_nodes[highest_active].empty() ){
185          --highest_active;
186        }
187
188        if( highest_active>=0) {
189         
190
191          NodeIt a=active_nodes[highest_active].front();
192          active_nodes[highest_active].pop_front();
193         
194          return a;
195        }
196        else {
197          return NodeIt();
198        }
199       
200        break;
201       
202      }
203      case impl_fifo : {
204
205        if( ! fifo_nodes.empty() ) {
206          NodeIt a=fifo_nodes.front();
207          fifo_nodes.pop_front();
208          return a;
209        }
210        else {
211          return NodeIt();
212        }
213        break;
214      }
215      }
216      //
217      return NodeIt();
218    }
219
220    //Puts node 'a' among the active nodes
221    void make_active(const NodeIt& a){
222      //s and t never become active
223      if (a!=s && a!= t){
224        switch(implementation){
225        case impl_highest_label :
226          active_nodes[level.get(a)].push_back(a);
227          break;
228        case impl_fifo :
229          fifo_nodes.push_back(a);
230          break;
231        }
232
233      }
234
235      //Update highest_active label
236      if (highest_active<level.get(a)){
237        highest_active=level.get(a);
238      }
239
240    }
241
242    //Changes the level of node a and make sufficent changes
243    void change_level_to(NodeIt a, int new_value){
244      int seged = level.get(a);
245      level.set(a,new_value);
246      --num_of_nodes_on_level[seged];
247      ++num_of_nodes_on_level[new_value];
248    }
249
250    //Collection of things useful (or necessary) to do before running
251
252    void preprocess(){
253
254      //---------------------------------------
255      //Initialize parameters
256      //---------------------------------------
257
258      //Setting starting preflow, level and excess values to zero
259      //This can be important, if the algorithm is run more then once
260      for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
261        level.set(i,0);
262        excess.set(i,0);
263        for(OutEdgeIt j=G.template first<OutEdgeIt>(i); j.valid(); ++j)
264          preflow.set(j, 0);
265      }
266      num_of_nodes_on_level[0]=number_of_nodes;
267      highest_active=0;
268      //---------------------------------------
269      //Initialize parameters
270      //---------------------------------------
271
272     
273      //------------------------------------
274      //This is the only part that uses BFS
275      //------------------------------------
276      //Setting starting level values using reverse bfs
277      reverse_bfs<graph_type> rev_bfs(G,t);
278      rev_bfs.run();
279      //write_property_vector(rev_bfs.dist,"rev_bfs");
280      for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
281        change_level_to(i,rev_bfs.dist(i));
282        //level.put(i,rev_bfs.dist.get(i));
283      }
284      //------------------------------------
285      //This is the only part that uses BFS
286      //------------------------------------
287     
288     
289      //Starting level of s
290      change_level_to(s,number_of_nodes);
291      //level.put(s,number_of_nodes);
292     
293     
294      //we push as much preflow from s as possible to start with
295      for(OutEdgeIt j=G.template first<OutEdgeIt>(s); j.valid(); ++j){
296        modify_preflow(j,capacity.get(j) );
297        make_active(G.head(j));
298        int lev=level.get(G.head(j));
299        if(highest_active<lev){
300          highest_active=lev;
301        }
302      }
303      //cout<<highest_active<<endl;
304    }
305
306   
307    //If the preflow is less than the capacity on the given edge
308    //then it is an edge in the residual graph
309    bool is_admissible_forward_edge(OutEdgeIt j, int& new_level){
310
311      if (capacity.get(j)>preflow.get(j)){
312        if(level.get(G.tail(j))==level.get(G.head(j))+1){
313          return true;
314        }
315        else{
316          if (level.get(G.head(j)) < new_level)
317            new_level=level.get(G.head(j));
318        }
319      }
320      return false;
321    }
322
323    //If the preflow is greater than 0 on the given edge
324    //then the edge reversd is an edge in the residual graph
325    bool is_admissible_backward_edge(InEdgeIt j, int& new_level){
326     
327      if (0<preflow.get(j)){
328        if(level.get(G.tail(j))==level.get(G.head(j))-1){
329         
330          return true;
331        }
332        else{
333          if (level.get(G.tail(j)) < new_level)
334            new_level=level.get(G.tail(j));
335        }
336       
337      }
338      return false;
339    }
340
341 
342  };  //class preflow_push 
343
344  template<typename graph_type, typename T>
345    T preflow_push<graph_type, T>::run() {
346   
347    preprocess();
348    //write_property_vector(level,"level");
349    T e,v;
350    NodeIt a;
351    while (a=get_active_node(), a.valid()){
352     
353      //cout<<G.id(a)<<endl;
354      //write_property_vector(excess,"excess");
355      //write_property_vector(level,"level");
356
357
358      bool go_to_next_node=false;
359      e = excess.get(a);
360      while (!go_to_next_node){
361        //Initial value for the new level for the active node we are dealing with
362        int new_level=2*number_of_nodes;
363        //write_property_vector(excess,"excess");
364        //write_property_vector(level,"level");
365        //cout<<G.id(a)<<endl;
366        //Out edges from node a
367        {
368          OutEdgeIt j=G.template first<OutEdgeIt>(a);
369          while (j.valid() && e){
370
371            if (is_admissible_forward_edge(j,new_level)){
372              v=min(e,capacity.get(j) - preflow.get(j));
373              e -= v;
374              //New node might become active
375              if (excess.get(G.head(j))==0){
376                make_active(G.head(j));
377              }
378              modify_preflow(j,v);
379            }
380            ++j;
381          }
382        }
383        //In edges to node a
384        {
385          InEdgeIt j=G.template first<InEdgeIt>(a);
386          while (j.valid() && e){
387            if (is_admissible_backward_edge(j,new_level)){
388              v=min(e,preflow.get(j));
389              e -= v;
390              //New node might become active
391              if (excess.get(G.tail(j))==0){
392                make_active(G.tail(j));
393              }
394              modify_preflow(j,-v);
395            }
396            ++j;
397          }
398        }
399
400        //if (G.id(a)==999)
401        //cout<<new_level<<" e: "<<e<<endl;
402        //cout<<G.id(a)<<" "<<new_level<<endl;
403
404        if (0==e){
405          //Saturating push
406          go_to_next_node=true;
407        }
408        else{//If there is still excess in node a
409         
410          //change_level_to(a,new_level+1);
411         
412          //Level remains empty
413          if (num_of_nodes_on_level[level.get(a)]==1){
414            change_level_to(a,number_of_nodes);
415            //go_to_next_node=True;
416          }
417          else{
418            change_level_to(a,new_level+1);
419            //increase_level(a);
420          }
421         
422   
423         
424
425          switch(node_examination){
426          case examine_to_relabel:
427            make_active(a);
428
429            go_to_next_node = true;
430            break;
431          default:
432            break;
433          }
434         
435   
436       
437        }//if (0==e)
438      }
439    }
440    maxflow_value = excess.get(t);
441    return maxflow_value;
442  }//run
443
444
445}//namespace hugo
446
447#endif //PREFLOW_PUSH_HH
Note: See TracBrowser for help on using the repository browser.