src/work/athos/preflow_push.hh
changeset 42 3ee2187d6342
child 77 69b2d279c8f0
equal deleted inserted replaced
-1:000000000000 0:5a721b2fe626
       
     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 
       
    12 using namespace std;
       
    13 
       
    14 namespace 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