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