# HG changeset patch
# User athos
# Date 1076947079 0
# Node ID 69b2d279c8f078b08e8e5e68fbfe250febf98f19
# Parent  d9650659a6ee5d4564cf71d0e9b9e14239e379d3
Kijavitottam a preflow_push algoritmust az uj koncept szerint.

diff -r d9650659a6ee -r 69b2d279c8f0 src/work/athos/pf_demo.cc
--- a/src/work/athos/pf_demo.cc	Mon Feb 16 11:38:19 2004 +0000
+++ b/src/work/athos/pf_demo.cc	Mon Feb 16 15:57:59 2004 +0000
@@ -2,9 +2,9 @@
 #include <vector>
 #include <string>
 
-#include "marci_list_graph.hh"
+#include "list_graph.hh"
 #include "marci_graph_traits.hh"
-#include "marci_property_vector.hh"
+//#include "marci_property_vector.hh"
 #include "preflow_push.hh"
 
 using namespace marci;
@@ -12,24 +12,67 @@
 
 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;
- 
   
+  typedef ListGraph::NodeIt NodeIt;
+  typedef ListGraph::EdgeIt EdgeIt;
+  /*
+  typedef ListGraph::EachNodeIt EachNodeIt;
+  typedef ListGraph::EachEdgeIt EachEdgeIt;
+  typedef ListGraph::OutEdgeIt OutEdgeIt;
+  typedef ListGraph::InEdgeIt InEdgeIt;
+  typedef ListGraph::SymEdgeIt SymEdgeIt;
+  */
+  
+  //Marci példája
+  ListGraph flowG;
+
+  NodeIt s=flowG.addNode();
+  NodeIt v1=flowG.addNode();
+  NodeIt v2=flowG.addNode();
+  NodeIt v3=flowG.addNode();
+  NodeIt v4=flowG.addNode();
+  NodeIt t=flowG.addNode();
+  
+
+  EdgeIt s_v1=flowG.addEdge(s, v1);
+  EdgeIt s_v2=flowG.addEdge(s, v2);
+  EdgeIt v1_v2=flowG.addEdge(v1, v2);
+  EdgeIt v2_v1=flowG.addEdge(v2, v1);
+  EdgeIt v1_v3=flowG.addEdge(v1, v3);
+  EdgeIt v3_v2=flowG.addEdge(v3, v2);
+  EdgeIt v2_v4=flowG.addEdge(v2, v4);
+  EdgeIt v4_v3=flowG.addEdge(v4, v3);
+  EdgeIt v3_t=flowG.addEdge(v3, t);
+  EdgeIt v4_t=flowG.addEdge(v4, t);
+
+  ListGraph::EdgeMap<int> cap(flowG);
+
+  cap.set(s_v1, 16);
+  cap.set(s_v2, 13);
+  cap.set(v1_v2, 10);
+  cap.set(v2_v1, 4);
+  cap.set(v1_v3, 12);
+  cap.set(v3_v2, 9);
+  cap.set(v2_v4, 14);
+  cap.set(v4_v3, 7);
+  cap.set(v3_t, 20);
+  cap.set(v4_t, 4);
+
+
+
+
+
+
+
+  /*
   //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();
+  NodeIt v2=flow_test.add_node();
+  NodeIt v3=flow_test.add_node();
+  NodeIt v4=flow_test.add_node();
+  NodeIt v5=flow_test.add_node();
+  NodeIt t=flow_test.add_node();
   
   node_property_vector<list_graph, std::string> node_name(flow_test);
   node_name.put(s, "s");  
@@ -70,52 +113,15 @@
   //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();
+  NodeIt s=flow_test.add_node();
+  NodeIt v1=flow_test.add_node();
+  NodeIt v2=flow_test.add_node();
+  NodeIt t=flow_test.add_node();
   
   node_property_vector<list_graph, std::string> node_name(flow_test);
   node_name.put(s, "s");
@@ -135,9 +141,11 @@
   */
 
   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) { 
+  for(EachNodeIt 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) 
@@ -147,13 +155,13 @@
       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) { 
+  //for(each_NodeIt i=flow_test.first_node(); i.valid(); ++i) { 
   //  std::cout << i << " ";
   //}
   
-  preflow_push<list_graph, int> preflow_push_test(flow_test, s, t, cap);
+  preflow_push<ListGraph, int> preflow_push_test(flowG, s, t, cap);
   cout << preflow_push_test.run()<<endl;
 
   //cap.put(v5_t, 9);
diff -r d9650659a6ee -r 69b2d279c8f0 src/work/athos/preflow_push.hh
--- a/src/work/athos/preflow_push.hh	Mon Feb 16 11:38:19 2004 +0000
+++ b/src/work/athos/preflow_push.hh	Mon Feb 16 15:57:59 2004 +0000
@@ -6,7 +6,8 @@
 #include <vector>
 //#include "pf_hiba.hh"
 //#include <marci_list_graph.hh>
-#include <marci_graph_traits.hh>
+//#include <marci_graph_traits.hh>
+
 #include "reverse_bfs.hh"
 
 using namespace std;
@@ -17,13 +18,25 @@
   class preflow_push {
 
     //Hasznos typedef-ek
+    typedef typename graph_type::NodeIt NodeIt;
+    typedef typename graph_type::EdgeIt EdgeIt;
+    typedef typename graph_type::EachNodeIt EachNodeIt;
+    typedef typename graph_type::EachEdgeIt EachEdgeIt;
+    typedef typename graph_type::OutEdgeIt OutEdgeIt;
+    typedef typename graph_type::InEdgeIt InEdgeIt;
+    typedef typename graph_type::SymEdgeIt SymEdgeIt;
+
+
+
+    /*
     typedef graph_traits<graph_type>::node_iterator node_iterator;
-    typedef graph_traits<graph_type>::edge_iterator edge_iterator;
+    typedef graph_traits<graph_type>::EdgeIt EdgeIt;
     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;
+    typedef graph_traits<graph_type>::each_EdgeIt each_EdgeIt;
+    typedef graph_traits<graph_type>::out_EdgeIt out_EdgeIt;
+    typedef graph_traits<graph_type>::InEdgeIt InEdgeIt;
+    typedef graph_traits<graph_type>::sym_EdgeIt sym_EdgeIt;
+    */
 
     //---------------------------------------------
     //Parameters of the algorithm
@@ -43,41 +56,49 @@
   private:
     //input
     graph_type& G;
-    node_iterator s;
-    node_iterator t;
-    edge_property_vector<graph_type, T> &capacity;
+    NodeIt s;
+    NodeIt t;
+    typename graph_type::EdgeMap<T> &capacity;
+    //typename graph_type::EdgeMap<T>  &capacity;
     //output
-    edge_property_vector<graph_type, T> preflow;
+    //typename graph_type::EdgeMap<T>  
+    typename graph_type::EdgeMap<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;
+    
+    
+    typename graph_type::NodeMap<int> level;
+    typename graph_type::NodeMap<T> excess;
+    //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;
+    list<NodeIt> fifo_nodes;
     //For 'highest label' implementation
     int highest_active;
     //int second_highest_active;
-    vector< list<node_iterator> > active_nodes;
+    vector< list<NodeIt> > 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)
+		      NodeIt _s, 
+		      NodeIt _t, 
+		      typename graph_type::EdgeMap<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())),
+	//number_of_nodes(count(G.first<EachNodeIt>())),
+	number_of_nodes(G.nodeNum()),
+
 	level(_G),
 	excess(_G)//,
         // Default constructor: active_nodes()
@@ -106,7 +127,7 @@
     //Returns the value of a maximal flow 
     T run();
   
-    edge_property_vector<graph_type, T> getmaxflow(){
+    typename graph_type::EdgeMap<T>  getmaxflow(){
       return preflow;
     }
 
@@ -114,32 +135,33 @@
   private:
     //For testing purposes only
     //Lists the node_properties
-    void write_property_vector(node_property_vector<graph_type, T> a, 
+    void write_property_vector(typename graph_type::NodeMap<T> a,
+			       //node_property_vector<graph_type, T> a, 
 			       char* prop_name="property"){
-      for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
+      for(EachNodeIt i=G.template first<EachNodeIt>(); 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){
+    void modify_excess(const NodeIt& a ,T v){
 	T old_value=excess.get(a);
-	excess.put(a,old_value+v);
+	excess.set(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){
+    void modify_preflow(EdgeIt j, const T& v){
 
       //Auxiliary variable
       T old_value;
 	
       //Modifiyng the edge
       old_value=preflow.get(j);
-      preflow.put(j,old_value+v);
+      preflow.set(j,old_value+v);
 
 
       //Modifiyng the head
@@ -152,7 +174,7 @@
 
     //Gives the active node to work with 
     //(depending on the implementation to be used)
-    node_iterator get_active_node(){
+    NodeIt get_active_node(){
       //cout<<highest_active<<endl;
 
       switch(implementation) {
@@ -164,12 +186,12 @@
 	}
 
 	if( highest_active>=0) {
-	  node_iterator a=active_nodes[highest_active].front();
+	  NodeIt a=active_nodes[highest_active].front();
 	  active_nodes[highest_active].pop_front();
 	  return a;
 	}
 	else {
-	  return node_iterator();
+	  return NodeIt();
 	}
 	
 	break;
@@ -178,22 +200,22 @@
       case impl_fifo : {
 
 	if( ! fifo_nodes.empty() ) {
-	  node_iterator a=fifo_nodes.front();
+	  NodeIt a=fifo_nodes.front();
 	  fifo_nodes.pop_front();
 	  return a;
 	}
 	else {
-	  return node_iterator();
+	  return NodeIt();
 	}
 	break;
       }
       }
       //
-      return node_iterator();
+      return NodeIt();
     }
 
     //Puts node 'a' among the active nodes
-    void make_active(const node_iterator& a){
+    void make_active(const NodeIt& a){
       //s and t never become active
       if (a!=s && a!= t){
 	switch(implementation){
@@ -215,14 +237,15 @@
     }
 
     //Changes the level of node a and make sufficent changes
-    void change_level_to(node_iterator a, int new_value){
+    void change_level_to(NodeIt a, int new_value){
       int seged = level.get(a);
-      level.put(a,new_value);
+      level.set(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(){
 
       //---------------------------------------
@@ -231,11 +254,11 @@
 
       //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);
+      for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
+        level.set(i,0);
+        excess.set(i,0);
+	for(OutEdgeIt j=G.template first<OutEdgeIt>(i); j.valid(); ++j) 
+	  preflow.set(j, 0);
       }
       num_of_nodes_on_level[0]=number_of_nodes;
       highest_active=0;
@@ -251,7 +274,7 @@
       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) {
+      for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
         change_level_to(i,rev_bfs.dist(i));
 	//level.put(i,rev_bfs.dist.get(i));
       }
@@ -266,7 +289,7 @@
       
       
       //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){ 
+      for(OutEdgeIt j=G.template first<OutEdgeIt>(s); j.valid(); ++j){ 
 	modify_preflow(j,capacity.get(j) );
 	make_active(G.head(j));
 	int lev=level.get(G.head(j));
@@ -280,7 +303,7 @@
     
     //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){
+    bool is_admissible_forward_edge(OutEdgeIt 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;
@@ -295,7 +318,7 @@
 
     //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){
+    bool is_admissible_backward_edge(InEdgeIt j, int& new_level){
       if (0<preflow.get(j)){
 	if(level.get(G.tail(j))==level.get(G.head(j))-1){
 	  return true;
@@ -318,22 +341,25 @@
     preprocess();
     
     T e,v;
-    node_iterator a;
+    NodeIt 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){
-	
+
+	//Initial value for the new level for the active node we are dealing with
+	int new_level=2*number_of_nodes;
+	//write_property_vector(excess,"excess");
+	//write_property_vector(level,"level");
+	//cout<<G.id(a)<<endl;
 	//Out edges from node a
 	{
-	  out_edge_iterator j=G.first_out_edge(a);
+	  OutEdgeIt j=G.template first<OutEdgeIt>(a);
 	  while (j.valid() && e){
 
 	    if (is_admissible_forward_edge(j,new_level)){
@@ -350,7 +376,7 @@
 	}
 	//In edges to node a
 	{
-	  in_edge_iterator j=G.first_in_edge(a);
+	  InEdgeIt j=G.template first<InEdgeIt>(a);
 	  while (j.valid() && e){
 	    if (is_admissible_backward_edge(j,new_level)){
 	      v=min(e,preflow.get(j));
@@ -372,7 +398,9 @@
 	  go_to_next_node=true;
 	}
 	else{//If there is still excess in node a
-
+	  
+	  //change_level_to(a,new_level+1);
+	  
 	  //Level remains empty
 	  if (num_of_nodes_on_level[level.get(a)]==1){
 	    change_level_to(a,number_of_nodes);
@@ -382,7 +410,7 @@
 	    change_level_to(a,new_level+1);
 	    //increase_level(a);
 	  }
-
+	  
     
 	  
 
diff -r d9650659a6ee -r 69b2d279c8f0 src/work/athos/reverse_bfs.hh
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/athos/reverse_bfs.hh	Mon Feb 16 15:57:59 2004 +0000
@@ -0,0 +1,103 @@
+/*
+reverse_bfs
+by jacint
+Performs a bfs on the out edges. It does not count predecessors, 
+only the distances, but one can easily modify it to know the pred as well.
+
+Constructor: 
+
+reverse_bfs(graph_type& G, node_iterator t)
+
+
+
+Member functions:
+
+void run(): runs a reverse bfs from t
+
+  The following function should be used after run() was already run.
+
+int dist(node_iterator v) : returns the distance from v to t. It is the number of nodes if t is not reachable from v.
+
+*/
+#ifndef REVERSE_BFS_HH
+#define REVERSE_BFS_HH
+
+#include <queue>
+
+//#include <marci_list_graph.hh>
+//#include <marci_property_vector.hh>
+
+
+
+namespace  marci {
+
+  template <typename graph_type>
+  class reverse_bfs {
+
+    typedef typename graph_type::NodeIt NodeIt;
+    typedef typename graph_type::EdgeIt EdgeIt;
+    typedef typename graph_type::EachNodeIt EachNodeIt;
+    typedef typename graph_type::EachEdgeIt EachEdgeIt;
+    typedef typename graph_type::OutEdgeIt OutEdgeIt;
+    typedef typename graph_type::InEdgeIt InEdgeIt;
+    typedef typename graph_type::SymEdgeIt SymEdgeIt;
+
+
+
+    graph_type& G;
+    NodeIt t;
+//    node_property_vector<graph_type, edge_iterator> pred;
+    //node_property_vector<graph_type, int>
+    typename graph_type::NodeMap<int> distance;
+    
+
+  public :
+
+    /*
+      The distance of the nodes is n, except t for which it is 0.
+    */
+    reverse_bfs(graph_type& _G, NodeIt _t) : 
+      G(_G), t(_t), 
+      distance(G, G.nodeNum()) {
+      distance.set(t,0);
+    }
+    
+    void run() {
+
+      //node_property_vector<graph_type, bool> 
+      typename graph_type::NodeMap<bool> reached(G, false); 
+      reached.set(t, true);
+
+      std::queue<NodeIt> bfs_queue;
+      bfs_queue.push(t);
+
+      while (!bfs_queue.empty()) {
+
+        NodeIt v=bfs_queue.front();	
+	bfs_queue.pop();
+
+	for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
+	  NodeIt w=G.tail(e);
+	  if (!reached.get(w)) {
+	    bfs_queue.push(w);
+	    distance.set(w, distance.get(v)+1);
+	    reached.set(w, true);
+	  }
+	}
+      }
+    }
+
+
+
+    int dist(NodeIt v) {
+      return distance.get(v);
+    }
+
+
+  };
+
+} // namespace marci
+
+#endif //REVERSE_BFS_HH
+
+