COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/preflow_push.hh @ 48:55fa34646895

Last change on this file since 48:55fa34646895 was 36:7d539ea6ad26, checked in by athos, 18 years ago

preflow_push.hh: Preflow-push valtozat by athos
A tesztfile: pf_demo.cc
Kulon makefile is van.

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