COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/preflow_push.hh @ 105:a3c73e9b9b2e

Last change on this file since 105:a3c73e9b9b2e was 105:a3c73e9b9b2e, checked in by Alpar Juttner, 17 years ago

marci -> hugo replacements
resize -> update replacements

File size: 11.0 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      //cout<<highest_active<<endl;
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          NodeIt a=active_nodes[highest_active].front();
190          active_nodes[highest_active].pop_front();
191          return a;
192        }
193        else {
194          return NodeIt();
195        }
196       
197        break;
198       
199      }
200      case impl_fifo : {
201
202        if( ! fifo_nodes.empty() ) {
203          NodeIt a=fifo_nodes.front();
204          fifo_nodes.pop_front();
205          return a;
206        }
207        else {
208          return NodeIt();
209        }
210        break;
211      }
212      }
213      //
214      return NodeIt();
215    }
216
217    //Puts node 'a' among the active nodes
218    void make_active(const NodeIt& a){
219      //s and t never become active
220      if (a!=s && a!= t){
221        switch(implementation){
222        case impl_highest_label :
223          active_nodes[level.get(a)].push_back(a);
224          break;
225        case impl_fifo :
226          fifo_nodes.push_back(a);
227          break;
228        }
229
230      }
231
232      //Update highest_active label
233      if (highest_active<level.get(a)){
234        highest_active=level.get(a);
235      }
236
237    }
238
239    //Changes the level of node a and make sufficent changes
240    void change_level_to(NodeIt a, int new_value){
241      int seged = level.get(a);
242      level.set(a,new_value);
243      --num_of_nodes_on_level[seged];
244      ++num_of_nodes_on_level[new_value];
245    }
246
247    //Collection of things useful (or necessary) to do before running
248
249    void preprocess(){
250
251      //---------------------------------------
252      //Initialize parameters
253      //---------------------------------------
254
255      //Setting starting preflow, level and excess values to zero
256      //This can be important, if the algorithm is run more then once
257      for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
258        level.set(i,0);
259        excess.set(i,0);
260        for(OutEdgeIt j=G.template first<OutEdgeIt>(i); j.valid(); ++j)
261          preflow.set(j, 0);
262      }
263      num_of_nodes_on_level[0]=number_of_nodes;
264      highest_active=0;
265      //---------------------------------------
266      //Initialize parameters
267      //---------------------------------------
268
269     
270      //------------------------------------
271      //This is the only part that uses BFS
272      //------------------------------------
273      //Setting starting level values using reverse bfs
274      reverse_bfs<graph_type> rev_bfs(G,t);
275      rev_bfs.run();
276      //write_property_vector(rev_bfs.dist,"rev_bfs");
277      for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
278        change_level_to(i,rev_bfs.dist(i));
279        //level.put(i,rev_bfs.dist.get(i));
280      }
281      //------------------------------------
282      //This is the only part that uses BFS
283      //------------------------------------
284     
285     
286      //Starting level of s
287      change_level_to(s,number_of_nodes);
288      //level.put(s,number_of_nodes);
289     
290     
291      //we push as much preflow from s as possible to start with
292      for(OutEdgeIt j=G.template first<OutEdgeIt>(s); j.valid(); ++j){
293        modify_preflow(j,capacity.get(j) );
294        make_active(G.head(j));
295        int lev=level.get(G.head(j));
296        if(highest_active<lev){
297          highest_active=lev;
298        }
299      }
300      //cout<<highest_active<<endl;
301    }
302
303   
304    //If the preflow is less than the capacity on the given edge
305    //then it is an edge in the residual graph
306    bool is_admissible_forward_edge(OutEdgeIt j, int& new_level){
307      if (capacity.get(j)>preflow.get(j)){
308        if(level.get(G.tail(j))==level.get(G.head(j))+1){
309          return true;
310        }
311        else{
312          if (level.get(G.head(j)) < new_level)
313            new_level=level.get(G.head(j));
314        }
315      }
316      return false;
317    }
318
319    //If the preflow is greater than 0 on the given edge
320    //then the edge reversd is an edge in the residual graph
321    bool is_admissible_backward_edge(InEdgeIt j, int& new_level){
322      if (0<preflow.get(j)){
323        if(level.get(G.tail(j))==level.get(G.head(j))-1){
324          return true;
325        }
326        else{
327          if (level.get(G.tail(j)) < new_level)
328            new_level=level.get(G.tail(j));
329        }
330       
331      }
332      return false;
333    }
334
335 
336  };  //class preflow_push 
337
338  template<typename graph_type, typename T>
339    T preflow_push<graph_type, T>::run() {
340   
341    preprocess();
342   
343    T e,v;
344    NodeIt a;
345    while (a=get_active_node(), a.valid()){
346      //cout<<G.id(a)<<endl;
347      //write_property_vector(excess,"excess");
348      //write_property_vector(level,"level");
349
350
351      bool go_to_next_node=false;
352      e = excess.get(a);
353      while (!go_to_next_node){
354
355        //Initial value for the new level for the active node we are dealing with
356        int new_level=2*number_of_nodes;
357        //write_property_vector(excess,"excess");
358        //write_property_vector(level,"level");
359        //cout<<G.id(a)<<endl;
360        //Out edges from node a
361        {
362          OutEdgeIt j=G.template first<OutEdgeIt>(a);
363          while (j.valid() && e){
364
365            if (is_admissible_forward_edge(j,new_level)){
366              v=min(e,capacity.get(j) - preflow.get(j));
367              e -= v;
368              //New node might become active
369              if (excess.get(G.head(j))==0){
370                make_active(G.head(j));
371              }
372              modify_preflow(j,v);
373            }
374            ++j;
375          }
376        }
377        //In edges to node a
378        {
379          InEdgeIt j=G.template first<InEdgeIt>(a);
380          while (j.valid() && e){
381            if (is_admissible_backward_edge(j,new_level)){
382              v=min(e,preflow.get(j));
383              e -= v;
384              //New node might become active
385              if (excess.get(G.tail(j))==0){
386                make_active(G.tail(j));
387              }
388              modify_preflow(j,-v);
389            }
390            ++j;
391          }
392        }
393
394        //cout<<G.id(a)<<" "<<new_level<<endl;
395
396        if (0==e){
397          //Saturating push
398          go_to_next_node=true;
399        }
400        else{//If there is still excess in node a
401         
402          //change_level_to(a,new_level+1);
403         
404          //Level remains empty
405          if (num_of_nodes_on_level[level.get(a)]==1){
406            change_level_to(a,number_of_nodes);
407            //go_to_next_node=True;
408          }
409          else{
410            change_level_to(a,new_level+1);
411            //increase_level(a);
412          }
413         
414   
415         
416
417          switch(node_examination){
418          case examine_to_relabel:
419            make_active(a);
420
421            go_to_next_node = true;
422            break;
423          default:
424            break;
425          }
426         
427   
428       
429        }//if (0==e)
430      }
431    }
432    maxflow_value = excess.get(t);
433    return maxflow_value;
434  }//run
435
436
437}//namespace hugo
438
439#endif //PREFLOW_PUSH_HH
Note: See TracBrowser for help on using the repository browser.