src/work/athos/preflow_push.hh
changeset 315 7b97540cd743
parent 105 a3c73e9b9b2e
child 331 f5461f8bc59b
equal deleted inserted replaced
2:0384862e9765 3:a5d7290d6004
     6 #include <vector>
     6 #include <vector>
     7 //#include "pf_hiba.hh"
     7 //#include "pf_hiba.hh"
     8 //#include <marci_list_graph.hh>
     8 //#include <marci_list_graph.hh>
     9 //#include <marci_graph_traits.hh>
     9 //#include <marci_graph_traits.hh>
    10 
    10 
    11 #include "reverse_bfs.hh"
    11 #include <reverse_bfs.hh>
    12 
    12 
    13 using namespace std;
    13 using namespace std;
    14 
    14 
    15 namespace hugo {
    15 namespace hugo {
    16 
    16 
   173     }
   173     }
   174 
   174 
   175     //Gives the active node to work with 
   175     //Gives the active node to work with 
   176     //(depending on the implementation to be used)
   176     //(depending on the implementation to be used)
   177     NodeIt get_active_node(){
   177     NodeIt get_active_node(){
   178       //cout<<highest_active<<endl;
   178       
   179 
   179 
   180       switch(implementation) {
   180       switch(implementation) {
   181       case impl_highest_label : {
   181       case impl_highest_label : {
   182 
   182 
   183 	//First need to find the highest label for which there"s an active node
   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() ){ 
   184 	while( highest_active>=0 && active_nodes[highest_active].empty() ){ 
   185 	  --highest_active;
   185 	  --highest_active;
   186 	}
   186 	}
   187 
   187 
   188 	if( highest_active>=0) {
   188 	if( highest_active>=0) {
       
   189 	  
       
   190 
   189 	  NodeIt a=active_nodes[highest_active].front();
   191 	  NodeIt a=active_nodes[highest_active].front();
   190 	  active_nodes[highest_active].pop_front();
   192 	  active_nodes[highest_active].pop_front();
       
   193 	  
   191 	  return a;
   194 	  return a;
   192 	}
   195 	}
   193 	else {
   196 	else {
   194 	  return NodeIt();
   197 	  return NodeIt();
   195 	}
   198 	}
   302 
   305 
   303     
   306     
   304     //If the preflow is less than the capacity on the given edge
   307     //If the preflow is less than the capacity on the given edge
   305     //then it is an edge in the residual graph
   308     //then it is an edge in the residual graph
   306     bool is_admissible_forward_edge(OutEdgeIt j, int& new_level){
   309     bool is_admissible_forward_edge(OutEdgeIt j, int& new_level){
       
   310 
   307       if (capacity.get(j)>preflow.get(j)){
   311       if (capacity.get(j)>preflow.get(j)){
   308 	if(level.get(G.tail(j))==level.get(G.head(j))+1){
   312 	if(level.get(G.tail(j))==level.get(G.head(j))+1){
   309 	  return true;
   313 	  return true;
   310 	}
   314 	}
   311 	else{
   315 	else{
   317     }
   321     }
   318 
   322 
   319     //If the preflow is greater than 0 on the given edge
   323     //If the preflow is greater than 0 on the given edge
   320     //then the edge reversd is an edge in the residual graph
   324     //then the edge reversd is an edge in the residual graph
   321     bool is_admissible_backward_edge(InEdgeIt j, int& new_level){
   325     bool is_admissible_backward_edge(InEdgeIt j, int& new_level){
       
   326       
   322       if (0<preflow.get(j)){
   327       if (0<preflow.get(j)){
   323 	if(level.get(G.tail(j))==level.get(G.head(j))-1){
   328 	if(level.get(G.tail(j))==level.get(G.head(j))-1){
       
   329 	 
   324 	  return true;
   330 	  return true;
   325 	}
   331 	}
   326 	else{
   332 	else{
   327 	  if (level.get(G.tail(j)) < new_level)
   333 	  if (level.get(G.tail(j)) < new_level)
   328 	    new_level=level.get(G.tail(j));
   334 	    new_level=level.get(G.tail(j));
   337 
   343 
   338   template<typename graph_type, typename T>
   344   template<typename graph_type, typename T>
   339     T preflow_push<graph_type, T>::run() {
   345     T preflow_push<graph_type, T>::run() {
   340     
   346     
   341     preprocess();
   347     preprocess();
   342     
   348     //write_property_vector(level,"level");
   343     T e,v;
   349     T e,v;
   344     NodeIt a;
   350     NodeIt a;
   345     while (a=get_active_node(), a.valid()){
   351     while (a=get_active_node(), a.valid()){
       
   352       
   346       //cout<<G.id(a)<<endl;
   353       //cout<<G.id(a)<<endl;
   347       //write_property_vector(excess,"excess");
   354       //write_property_vector(excess,"excess");
   348       //write_property_vector(level,"level");
   355       //write_property_vector(level,"level");
   349 
   356 
   350 
   357 
   351       bool go_to_next_node=false;
   358       bool go_to_next_node=false;
   352       e = excess.get(a);
   359       e = excess.get(a);
   353       while (!go_to_next_node){
   360       while (!go_to_next_node){
   354 
       
   355 	//Initial value for the new level for the active node we are dealing with
   361 	//Initial value for the new level for the active node we are dealing with
   356 	int new_level=2*number_of_nodes;
   362 	int new_level=2*number_of_nodes;
   357 	//write_property_vector(excess,"excess");
   363 	//write_property_vector(excess,"excess");
   358 	//write_property_vector(level,"level");
   364 	//write_property_vector(level,"level");
   359 	//cout<<G.id(a)<<endl;
   365 	//cout<<G.id(a)<<endl;
   389 	    }
   395 	    }
   390 	    ++j;
   396 	    ++j;
   391 	  }
   397 	  }
   392 	}
   398 	}
   393 
   399 
       
   400 	//if (G.id(a)==999)
       
   401 	//cout<<new_level<<" e: "<<e<<endl;
   394 	//cout<<G.id(a)<<" "<<new_level<<endl;
   402 	//cout<<G.id(a)<<" "<<new_level<<endl;
   395 
   403 
   396 	if (0==e){
   404 	if (0==e){
   397 	  //Saturating push
   405 	  //Saturating push
   398 	  go_to_next_node=true;
   406 	  go_to_next_node=true;