# HG changeset patch
# User athos
# Date 1075220631 0
# Node ID 7d539ea6ad267d7ca53483ebf41d9486aabd2b03
# Parent  65dca0f43fbada3b9cd35308f8fce62a31fb7d60
preflow_push.hh: Preflow-push valtozat by athos
A tesztfile: pf_demo.cc
Kulon makefile is van.

diff -r 65dca0f43fba -r 7d539ea6ad26 src/work/athos/makefile
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/athos/makefile	Tue Jan 27 16:23:51 2004 +0000
@@ -0,0 +1,7 @@
+CXXFLAGS = -Wall -ansi -g
+CXX = g++-3.0
+
+pf_demo: pf_demo.cc ../marci_graph_traits.hh ../marci_list_graph.hh ../marci_property_vector.hh preflow_push.hh ../reverse_bfs.hh
+	$(CXX) $(CXXFLAGS) -I. -I.. pf_demo.cc -o pf_demo 
+
+
diff -r 65dca0f43fba -r 7d539ea6ad26 src/work/athos/pf_demo.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/athos/pf_demo.cc	Tue Jan 27 16:23:51 2004 +0000
@@ -0,0 +1,172 @@
+#include <iostream>
+#include <vector>
+#include <string>
+
+#include "marci_list_graph.hh"
+#include "marci_graph_traits.hh"
+#include "marci_property_vector.hh"
+#include "preflow_push.hh"
+
+using namespace marci;
+
+
+int main (int, char*[])
+{
+  typedef graph_traits<list_graph>::node_iterator node_iterator;
+  typedef graph_traits<list_graph>::edge_iterator edge_iterator;
+  typedef graph_traits<list_graph>::each_node_iterator each_node_iterator;
+  typedef graph_traits<list_graph>::each_edge_iterator each_edge_iterator;
+  typedef graph_traits<list_graph>::out_edge_iterator out_edge_iterator;
+  typedef graph_traits<list_graph>::in_edge_iterator in_edge_iterator;
+  typedef graph_traits<list_graph>::sym_edge_iterator sym_edge_iterator;
+
+  list_graph flow_test;
+ 
+  
+  //Ahuja könyv példája
+  node_iterator s=flow_test.add_node();
+  node_iterator v2=flow_test.add_node();
+  node_iterator v3=flow_test.add_node();
+  node_iterator v4=flow_test.add_node();
+  node_iterator v5=flow_test.add_node();
+  node_iterator t=flow_test.add_node();
+  
+  node_property_vector<list_graph, std::string> node_name(flow_test);
+  node_name.put(s, "s");  
+  node_name.put(v2, "v2");
+  node_name.put(v3, "v3");
+  node_name.put(v4, "v4");
+  node_name.put(v5, "v5");
+  node_name.put(t, "t");
+
+  
+  edge_iterator s_v2=flow_test.add_edge(s, v2);
+  edge_iterator s_v3=flow_test.add_edge(s, v3);
+  
+  edge_iterator v2_v4=flow_test.add_edge(v2, v4);
+  edge_iterator v2_v5=flow_test.add_edge(v2, v5);
+
+  edge_iterator v3_v5=flow_test.add_edge(v3, v5);
+
+  edge_iterator v4_t=flow_test.add_edge(v4, t);
+  edge_iterator v5_t=flow_test.add_edge(v5, t);
+  
+  //Kis modositas
+  edge_iterator v2_s=flow_test.add_edge(v2, s);
+
+  edge_property_vector<list_graph, int> cap(flow_test);  
+  cap.put(s_v2, 10);
+  cap.put(s_v3, 10);
+  cap.put(v2_v4, 5);
+  cap.put(v2_v5, 8);
+  cap.put(v3_v5, 5);
+  cap.put(v4_t, 8);
+  cap.put(v5_t, 8);
+
+  //Kis modositas
+  cap.put(v2_s, 100);
+
+  //Kis modositas
+  //edge_iterator t_s=flow_test.add_edge(t, s);
+  //cap.put(t_s, 20);
+
+  
+  /*
+  //Marci példája
+  node_iterator s=flow_test.add_node();
+  node_iterator v1=flow_test.add_node();
+  node_iterator v2=flow_test.add_node();
+  node_iterator v3=flow_test.add_node();
+  node_iterator v4=flow_test.add_node();
+  node_iterator t=flow_test.add_node();
+  
+  node_property_vector<list_graph, std::string> node_name(flow_test);
+  node_name.put(s, "s");
+  node_name.put(v1, "v1");
+  node_name.put(v2, "v2");
+  node_name.put(v3, "v3");
+  node_name.put(v4, "v4");
+  node_name.put(t, "t");
+
+  edge_iterator s_v1=flow_test.add_edge(s, v1);
+  edge_iterator s_v2=flow_test.add_edge(s, v2);
+  edge_iterator v1_v2=flow_test.add_edge(v1, v2);
+  edge_iterator v2_v1=flow_test.add_edge(v2, v1);
+  edge_iterator v1_v3=flow_test.add_edge(v1, v3);
+  edge_iterator v3_v2=flow_test.add_edge(v3, v2);
+  edge_iterator v2_v4=flow_test.add_edge(v2, v4);
+  edge_iterator v4_v3=flow_test.add_edge(v4, v3);
+  edge_iterator v3_t=flow_test.add_edge(v3, t);
+  edge_iterator v4_t=flow_test.add_edge(v4, t);
+  
+  edge_property_vector<list_graph, int> cap(flow_test);  
+  cap.put(s_v1, 16);
+  cap.put(s_v2, 13);
+  cap.put(v1_v2, 10);
+  cap.put(v2_v1, 4);
+  cap.put(v1_v3, 12);
+  cap.put(v3_v2, 9);
+  cap.put(v2_v4, 14);
+  cap.put(v4_v3, 7);
+  cap.put(v3_t, 20);
+  cap.put(v4_t, 4);
+  */ 
+  /*Egyszerű példa
+  node_iterator s=flow_test.add_node();
+  node_iterator v1=flow_test.add_node();
+  node_iterator v2=flow_test.add_node();
+  node_iterator t=flow_test.add_node();
+  
+  node_property_vector<list_graph, std::string> node_name(flow_test);
+  node_name.put(s, "s");
+  node_name.put(v1, "v1");
+  node_name.put(v2, "v2");
+  node_name.put(t, "t");
+
+  edge_iterator s_v1=flow_test.add_edge(s, v1);
+  edge_iterator v1_v2=flow_test.add_edge(v1, v2);
+  edge_iterator v2_t=flow_test.add_edge(v2, t);
+
+  edge_property_vector<list_graph, int> cap(flow_test); 
+    
+  cap.put(s_v1, 16);
+  cap.put(v1_v2, 10);
+  cap.put(v2_t, 4);
+  */
+
+  std::cout << "preflow-push algorithm test..." << std::endl;
+  std::cout << "on directed graph graph" << std::endl; //<< flow_test;
+  std::cout << "names and capacity values" << std::endl; 
+  for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) { 
+    std::cout << node_name.get(i) << ": ";
+    std::cout << "out edges: ";
+    for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j) 
+      std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
+    std::cout << "in edges: ";
+    for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j) 
+      std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
+    std::cout << std::endl;
+  }
+
+  
+  //for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) { 
+  //  std::cout << i << " ";
+  //}
+  
+  preflow_push<list_graph, int> preflow_push_test(flow_test, s, t, cap);
+  cout << preflow_push_test.run()<<endl;
+
+  //cap.put(v5_t, 9);
+  //cout << preflow_push_test.run()<<endl;
+
+  return 0;
+}
+
+
+
+
+
+
+
+
+
diff -r 65dca0f43fba -r 7d539ea6ad26 src/work/athos/preflow_push.hh
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/athos/preflow_push.hh	Tue Jan 27 16:23:51 2004 +0000
@@ -0,0 +1,411 @@
+#ifndef PREFLOW_PUSH_HH
+#define PREFLOW_PUSH_HH
+
+#include <algorithm>
+#include <list>
+#include <vector>
+//#include "pf_hiba.hh"
+//#include <marci_list_graph.hh>
+#include <marci_graph_traits.hh>
+#include "reverse_bfs.hh"
+
+using namespace std;
+
+namespace marci {
+
+  template <typename graph_type, typename T>
+  class preflow_push {
+
+    //Hasznos typedef-ek
+    typedef graph_traits<graph_type>::node_iterator node_iterator;
+    typedef graph_traits<graph_type>::edge_iterator edge_iterator;
+    typedef graph_traits<graph_type>::each_node_iterator each_node_iterator;
+    typedef graph_traits<graph_type>::each_edge_iterator each_edge_iterator;
+    typedef graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
+    typedef graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
+    typedef graph_traits<graph_type>::sym_edge_iterator sym_edge_iterator;
+
+    //---------------------------------------------
+    //Parameters of the algorithm
+    //---------------------------------------------
+    //Fully examine an active node until excess becomes 0
+    enum node_examination_t {examine_full, examine_to_relabel};
+    //No more implemented yet:, examine_only_one_edge};
+    node_examination_t node_examination;
+    //Which implementation to be used
+    enum implementation_t {impl_fifo, impl_highest_label};
+    //No more implemented yet:};
+    implementation_t implementation;
+    //---------------------------------------------
+    //Parameters of the algorithm
+    //---------------------------------------------
+ 
+  private:
+    //input
+    graph_type& G;
+    node_iterator s;
+    node_iterator t;
+    edge_property_vector<graph_type, T> &capacity;
+    //output
+    edge_property_vector<graph_type, T> preflow;
+    T maxflow_value;
+  
+    //auxiliary variables for computation
+    int number_of_nodes;
+    node_property_vector<graph_type, int> level;
+    node_property_vector<graph_type, T> excess;
+    
+    //Number of nodes on each level
+    vector<int> num_of_nodes_on_level;
+    
+    //For the FIFO implementation
+    list<node_iterator> fifo_nodes;
+    //For 'highest label' implementation
+    int highest_active;
+    //int second_highest_active;
+    vector< list<node_iterator> > active_nodes;
+
+  public:
+  
+    //Constructing the object using the graph, source, sink and capacity vector
+    preflow_push(
+		      graph_type& _G, 
+		      node_iterator _s, 
+		      node_iterator _t, 
+		      edge_property_vector<graph_type, T>& _capacity)
+      : G(_G), s(_s), t(_t), 
+	capacity(_capacity), 
+	preflow(_G),
+	//Counting the number of nodes
+	number_of_nodes(number_of(G.first_node())),
+	level(_G),
+	excess(_G)//,
+        // Default constructor: active_nodes()
+    { 
+      //Simplest parameter settings
+      node_examination = examine_full;//examine_to_relabel;//
+      //Which implementation to be usedexamine_full
+      implementation = impl_highest_label;//impl_fifo;
+ 
+      //
+      num_of_nodes_on_level.resize(2*number_of_nodes-1);
+      num_of_nodes_on_level.clear();
+
+      switch(implementation){
+      case impl_highest_label :{
+	active_nodes.resize(2*number_of_nodes-1);
+	active_nodes.clear();
+	break;
+      }
+      default:
+	break;
+      }
+
+    }
+
+    //Returns the value of a maximal flow 
+    T run();
+  
+    edge_property_vector<graph_type, T> getmaxflow(){
+      return preflow;
+    }
+
+
+  private:
+    //For testing purposes only
+    //Lists the node_properties
+    void write_property_vector(node_property_vector<graph_type, T> a, 
+			       char* prop_name="property"){
+      for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
+	cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a.get(i)<<endl;
+      }
+      cout<<endl;
+    }
+
+    //Modifies the excess of the node and makes sufficient changes
+    void modify_excess(const node_iterator& a ,T v){
+	T old_value=excess.get(a);
+	excess.put(a,old_value+v);
+    }
+  
+    //This private procedure is supposed to modify the preflow on edge j
+    //by value v (which can be positive or negative as well) 
+    //and maintain the excess on the head and tail
+    //Here we do not check whether this is possible or not
+    void modify_preflow(edge_iterator j, const T& v){
+
+      //Auxiliary variable
+      T old_value;
+	
+      //Modifiyng the edge
+      old_value=preflow.get(j);
+      preflow.put(j,old_value+v);
+
+
+      //Modifiyng the head
+      modify_excess(G.head(j),v);
+	
+      //Modifiyng the tail
+      modify_excess(G.tail(j),-v);
+
+    }
+
+    //Gives the active node to work with 
+    //(depending on the implementation to be used)
+    node_iterator get_active_node(){
+      //cout<<highest_active<<endl;
+
+      switch(implementation) {
+      case impl_highest_label : {
+
+	//First need to find the highest label for which there"s an active node
+	while( highest_active>=0 && active_nodes[highest_active].empty() ){ 
+	  --highest_active;
+	}
+
+	if( highest_active>=0) {
+	  node_iterator a=active_nodes[highest_active].front();
+	  active_nodes[highest_active].pop_front();
+	  return a;
+	}
+	else {
+	  return node_iterator();
+	}
+	
+	break;
+	
+      }
+      case impl_fifo : {
+
+	if( ! fifo_nodes.empty() ) {
+	  node_iterator a=fifo_nodes.front();
+	  fifo_nodes.pop_front();
+	  return a;
+	}
+	else {
+	  return node_iterator();
+	}
+	break;
+      }
+      }
+      //
+      return node_iterator();
+    }
+
+    //Puts node 'a' among the active nodes
+    void make_active(const node_iterator& a){
+      //s and t never become active
+      if (a!=s && a!= t){
+	switch(implementation){
+	case impl_highest_label :
+	  active_nodes[level.get(a)].push_back(a);
+	  break;
+	case impl_fifo :
+	  fifo_nodes.push_back(a);
+	  break;
+	}
+
+      }
+
+      //Update highest_active label
+      if (highest_active<level.get(a)){
+	highest_active=level.get(a);
+      }
+
+    }
+
+    //Changes the level of node a and make sufficent changes
+    void change_level_to(node_iterator a, int new_value){
+      int seged = level.get(a);
+      level.put(a,new_value);
+      --num_of_nodes_on_level[seged];
+      ++num_of_nodes_on_level[new_value];
+    }
+
+    //Collection of things useful (or necessary) to do before running
+    void preprocess(){
+
+      //---------------------------------------
+      //Initialize parameters
+      //---------------------------------------
+
+      //Setting starting preflow, level and excess values to zero
+      //This can be important, if the algorithm is run more then once
+      for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
+        level.put(i,0);
+        excess.put(i,0);
+	for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) 
+	  preflow.put(j, 0);
+      }
+      num_of_nodes_on_level[0]=number_of_nodes;
+      highest_active=0;
+      //---------------------------------------
+      //Initialize parameters
+      //---------------------------------------
+
+      
+      //------------------------------------
+      //This is the only part that uses BFS
+      //------------------------------------
+      //Setting starting level values using reverse bfs
+      reverse_bfs<graph_type> rev_bfs(G,t);
+      rev_bfs.run();
+      //write_property_vector(rev_bfs.dist,"rev_bfs");
+      for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
+        change_level_to(i,rev_bfs.dist(i));
+	//level.put(i,rev_bfs.dist.get(i));
+      }
+      //------------------------------------
+      //This is the only part that uses BFS
+      //------------------------------------
+      
+      
+      //Starting level of s
+      change_level_to(s,number_of_nodes);
+      //level.put(s,number_of_nodes);
+      
+      
+      //we push as much preflow from s as possible to start with
+      for(out_edge_iterator j=G.first_out_edge(s); j.valid(); ++j){ 
+	modify_preflow(j,capacity.get(j) );
+	make_active(G.head(j));
+	int lev=level.get(G.head(j));
+	if(highest_active<lev){
+	  highest_active=lev;
+	}
+      }
+      //cout<<highest_active<<endl;
+    } 
+
+    
+    //If the preflow is less than the capacity on the given edge
+    //then it is an edge in the residual graph
+    bool is_admissible_forward_edge(out_edge_iterator j, int& new_level){
+      if (capacity.get(j)>preflow.get(j)){
+	if(level.get(G.tail(j))==level.get(G.head(j))+1){
+	  return true;
+	}
+	else{
+	  if (level.get(G.head(j)) < new_level)
+	    new_level=level.get(G.head(j));
+	}
+      }
+      return false;
+    }
+
+    //If the preflow is greater than 0 on the given edge
+    //then the edge reversd is an edge in the residual graph
+    bool is_admissible_backward_edge(in_edge_iterator j, int& new_level){
+      if (0<preflow.get(j)){
+	if(level.get(G.tail(j))==level.get(G.head(j))-1){
+	  return true;
+	}
+	else{
+	  if (level.get(G.tail(j)) < new_level)
+	    new_level=level.get(G.tail(j));
+	}
+	
+      }
+      return false;
+    }
+
+ 
+  };  //class preflow_push  
+
+  template<typename graph_type, typename T>
+    T preflow_push<graph_type, T>::run() {
+    
+    preprocess();
+    
+    T e,v;
+    node_iterator a;
+    while (a=get_active_node(), a.valid()){
+      //cout<<G.id(a)<<endl;
+      //write_property_vector(excess,"excess");
+      //write_property_vector(level,"level");
+
+      //Initial value for the new level for the active node we are dealing with
+      int new_level=2*number_of_nodes;
+
+      bool go_to_next_node=false;
+      e = excess.get(a);
+      while (!go_to_next_node){
+	
+	//Out edges from node a
+	{
+	  out_edge_iterator j=G.first_out_edge(a);
+	  while (j.valid() && e){
+
+	    if (is_admissible_forward_edge(j,new_level)){
+	      v=min(e,capacity.get(j) - preflow.get(j));
+	      e -= v;
+	      //New node might become active
+	      if (excess.get(G.head(j))==0){
+		make_active(G.head(j));
+	      }
+	      modify_preflow(j,v);
+	    }
+	    ++j;
+	  }
+	}
+	//In edges to node a
+	{
+	  in_edge_iterator j=G.first_in_edge(a);
+	  while (j.valid() && e){
+	    if (is_admissible_backward_edge(j,new_level)){
+	      v=min(e,preflow.get(j));
+	      e -= v;
+	      //New node might become active
+	      if (excess.get(G.tail(j))==0){
+		make_active(G.tail(j));
+	      }
+	      modify_preflow(j,-v);
+	    }
+	    ++j;
+	  }
+	}
+
+	//cout<<G.id(a)<<" "<<new_level<<endl;
+
+	if (0==e){
+	  //Saturating push
+	  go_to_next_node=true;
+	}
+	else{//If there is still excess in node a
+
+	  //Level remains empty
+	  if (num_of_nodes_on_level[level.get(a)]==1){
+	    change_level_to(a,number_of_nodes);
+	    //go_to_next_node=True;
+	  }
+	  else{
+	    change_level_to(a,new_level+1);
+	    //increase_level(a);
+	  }
+
+    
+	  
+
+	  switch(node_examination){
+	  case examine_to_relabel:
+	    make_active(a);
+
+	    go_to_next_node = true;
+	    break;
+	  default:
+	    break;
+	  }
+	  
+    
+	
+	}//if (0==e)
+      }
+    }
+    maxflow_value = excess.get(t);
+    return maxflow_value;
+  }//run
+
+
+}//namespace marci
+
+#endif //PREFLOW_PUSH_HH