COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/preflow_push.hh @ 334:63703ea7d02f

Last change on this file since 334:63703ea7d02f was 331:f5461f8bc59b, checked in by athos, 21 years ago

Elkezdtem atirni a preflow_push-t. Csinaltam egy backupot graph wrapper nelkul (without gw, azaz wogw)

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