# HG changeset patch
# User athos
# Date 1082048624 0
# Node ID f5461f8bc59bbe42defafd2db346d3cf265d86fe
# Parent  7ac0d4e8a31c60fb2c85c62a81dcddcaa53be520
Elkezdtem atirni a preflow_push-t. Csinaltam egy backupot graph wrapper nelkul (without gw, azaz wogw)

diff -r 7ac0d4e8a31c -r f5461f8bc59b src/work/athos/makefile
--- a/src/work/athos/makefile	Thu Apr 15 14:41:20 2004 +0000
+++ b/src/work/athos/makefile	Thu Apr 15 17:03:44 2004 +0000
@@ -6,7 +6,7 @@
 #BOOSTROOT ?= /home/marci/boost
 INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,athos,akos,klao} #-I$(BOOSTROOT)
 #LEDAINCLUDE ?= -I$(LEDAROOT)/incl
-CXXFLAGS = -g -W -Wall $(INCLUDEDIRS) -ansi -pedantic
+CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) -ansi -pedantic
 
 #LEDABINARIES = lg_vs_sg leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
 BINARIES = suurballe
diff -r 7ac0d4e8a31c -r f5461f8bc59b src/work/athos/pf_demo.cc
--- a/src/work/athos/pf_demo.cc	Thu Apr 15 14:41:20 2004 +0000
+++ b/src/work/athos/pf_demo.cc	Thu Apr 15 17:03:44 2004 +0000
@@ -2,8 +2,8 @@
 #include <vector>
 #include <string>
 
-#include "list_graph.hh"
-#include "marci_graph_traits.hh"
+#include "list_graph.h"
+//#include "marci_graph_traits.hh"
 //#include "marci_property_vector.hh"
 #include "preflow_push.hh"
 
@@ -13,137 +13,88 @@
 int main (int, char*[])
 {
 
-  
-  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;
-  */
-  ListGraph flowG;
+  typedef ListGraph::Node Node;
+  typedef ListGraph::Edge Edge;
+
+  ListGraph graph;
 
   /*
   //Marci példája
 
 
-  NodeIt s=flowG.addNode();
-  NodeIt v1=flowG.addNode();
-  NodeIt v2=flowG.addNode();
-  NodeIt v3=flowG.addNode();
-  NodeIt v4=flowG.addNode();
-  NodeIt t=flowG.addNode();
+  NodeIt s=graph.addNode();
+  NodeIt v1=graph.addNode();
+  NodeIt v2=graph.addNode();
+  NodeIt v3=graph.addNode();
+  NodeIt v4=graph.addNode();
+  NodeIt t=graph.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);
+  EdgeIt s_v1=graph.addEdge(s, v1);
+  EdgeIt s_v2=graph.addEdge(s, v2);
+  EdgeIt v1_v2=graph.addEdge(v1, v2);
+  EdgeIt v2_v1=graph.addEdge(v2, v1);
+  EdgeIt v1_v3=graph.addEdge(v1, v3);
+  EdgeIt v3_v2=graph.addEdge(v3, v2);
+  EdgeIt v2_v4=graph.addEdge(v2, v4);
+  EdgeIt v4_v3=graph.addEdge(v4, v3);
+  EdgeIt v3_t=graph.addEdge(v3, t);
+  EdgeIt v4_t=graph.addEdge(v4, t);
 
-  ListGraph::EdgeMap<int> cap(flowG);
+  ListGraph::EdgeMap<int> length(graph);
 
-  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);
+  length.set(s_v1, 16);
+  length.set(s_v2, 13);
+  length.set(v1_v2, 10);
+  length.set(v2_v1, 4);
+  length.set(v1_v3, 12);
+  length.set(v3_v2, 9);
+  length.set(v2_v4, 14);
+  length.set(v4_v3, 7);
+  length.set(v3_t, 20);
+  length.set(v4_t, 4);
   */
 
 
   //Ahuja könyv példája
 
-  NodeIt s=flowG.addNode();
-  NodeIt v2=flowG.addNode();
-  NodeIt v3=flowG.addNode();
-  NodeIt v4=flowG.addNode();
-  NodeIt v5=flowG.addNode();
-  NodeIt t=flowG.addNode();
+  Node s=graph.addNode();
+  Node v2=graph.addNode();
+  Node v3=graph.addNode();
+  Node v4=graph.addNode();
+  Node v5=graph.addNode();
+  Node t=graph.addNode();
 
-  EdgeIt s_v2=flowG.addEdge(s, v2);
-  EdgeIt s_v3=flowG.addEdge(s, v3);
-  EdgeIt v2_v4=flowG.addEdge(v2, v4);
-  EdgeIt v2_v5=flowG.addEdge(v2, v5);
-  EdgeIt v3_v5=flowG.addEdge(v3, v5);
-  EdgeIt v4_t=flowG.addEdge(v4, t);
-  EdgeIt v5_t=flowG.addEdge(v5, t);
+  Edge s_v2=graph.addEdge(s, v2);
+  Edge s_v3=graph.addEdge(s, v3);
+  Edge v2_v4=graph.addEdge(v2, v4);
+  Edge v2_v5=graph.addEdge(v2, v5);
+  Edge v3_v5=graph.addEdge(v3, v5);
+  Edge v4_t=graph.addEdge(v4, t);
+  Edge v5_t=graph.addEdge(v5, t);
   
   //Kis modositas
-  //edge_iterator v2_s=flowG.add_edge(v2, s);
+  //edge_iterator v2_s=graph.add_edge(v2, s);
 
-  ListGraph::EdgeMap<int> cap(flowG);
+  ListGraph::EdgeMap<int> length(graph);
 
-  cap.set(s_v2, 10);
-  cap.set(s_v3, 10);
-  cap.set(v2_v4, 5);
-  cap.set(v2_v5, 8);
-  cap.set(v3_v5, 5);
-  cap.set(v4_t, 8);
-  cap.set(v5_t, 8);
+  length.set(s_v2, 10);
+  length.set(s_v3, 10);
+  length.set(v2_v4, 5);
+  length.set(v2_v5, 8);
+  length.set(v3_v5, 5);
+  length.set(v4_t, 8);
+  length.set(v5_t, 8);
 
   //Kis modositas
-  //cap.put(v2_s, 100);
- 
+  //length.put(v2_s, 100);
 
 
 
-  /*Egyszerű példa
-  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");
-  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(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) 
-      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_NodeIt i=flow_test.first_node(); i.valid(); ++i) { 
-  //  std::cout << i << " ";
-  //}
-  
-  preflow_push<ListGraph, int> preflow_push_test(flowG, s, t, cap);
+  preflow_push<ListGraph, int> preflow_push_test(graph, s, t, length);
   cout << preflow_push_test.run()<<endl;
 
   //cap.put(v5_t, 9);
@@ -151,12 +102,3 @@
 
   return 0;
 }
-
-
-
-
-
-
-
-
-
diff -r 7ac0d4e8a31c -r f5461f8bc59b src/work/athos/preflow_push.hh
--- a/src/work/athos/preflow_push.hh	Thu Apr 15 14:41:20 2004 +0000
+++ b/src/work/athos/preflow_push.hh	Thu Apr 15 17:03:44 2004 +0000
@@ -1,43 +1,32 @@
-#ifndef PREFLOW_PUSH_HH
-#define PREFLOW_PUSH_HH
+#ifndef HUGO_PREFLOW_PUSH_HH
+#define HUGO_PREFLOW_PUSH_HH
 
-#include <algorithm>
+//#include <algorithm>
 #include <list>
 #include <vector>
+#include <queue>
 //#include "pf_hiba.hh"
 //#include <marci_list_graph.hh>
 //#include <marci_graph_traits.hh>
-
-#include <reverse_bfs.hh>
+#include <invalid.h>
+#include <graph_wrapper.h>
+//#include <reverse_bfs.hh>
 
 using namespace std;
 
 namespace hugo {
 
-  template <typename graph_type, typename T>
+  template <typename Graph, typename T>
   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;
+    //Useful typedefs
+    typedef typename Graph::Node Node;
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::Edge Edge;
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    typedef typename Graph::InEdgeIt InEdgeIt;
 
 
-
-    /*
-    typedef graph_traits<graph_type>::node_iterator node_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_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
     //---------------------------------------------
@@ -55,43 +44,41 @@
  
   private:
     //input
-    graph_type& G;
-    NodeIt s;
-    NodeIt t;
-    typename graph_type::EdgeMap<T> &capacity;
-    //typename graph_type::EdgeMap<T>  &capacity;
+    Graph& G;
+    Node s;
+    Node t;
+    typename Graph::EdgeMap<T> &capacity;
+
     //output
-    //typename graph_type::EdgeMap<T>  
-    typename graph_type::EdgeMap<T> preflow;
+    typename Graph::EdgeMap<T> preflow;
     T maxflow_value;
   
     //auxiliary variables for computation
+    //The number of the nodes
     int number_of_nodes;
-    
-    
-    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;
+    //A nodemap for the level
+    typename Graph::NodeMap<int> level;
+    //A nodemap for the excess
+    typename Graph::NodeMap<T> excess;
     
     //Number of nodes on each level
     vector<int> num_of_nodes_on_level;
     
     //For the FIFO implementation
-    list<NodeIt> fifo_nodes;
+    list<Node> fifo_nodes;
     //For 'highest label' implementation
     int highest_active;
     //int second_highest_active;
-    vector< list<NodeIt> > active_nodes;
+    vector< list<Node> > active_nodes;
 
   public:
   
     //Constructing the object using the graph, source, sink and capacity vector
     preflow_push(
-		      graph_type& _G, 
-		      NodeIt _s, 
-		      NodeIt _t, 
-		      typename graph_type::EdgeMap<T> & _capacity)
+		      Graph& _G, 
+		      Node _s, 
+		      Node _t, 
+		      typename Graph::EdgeMap<T> & _capacity)
       : G(_G), s(_s), t(_t), 
 	capacity(_capacity), 
 	preflow(_G),
@@ -114,8 +101,9 @@
 
       switch(implementation){
       case impl_highest_label :{
+	active_nodes.clear();
 	active_nodes.resize(2*number_of_nodes-1);
-	active_nodes.clear();
+	
 	break;
       }
       default:
@@ -127,7 +115,7 @@
     //Returns the value of a maximal flow 
     T run();
   
-    typename graph_type::EdgeMap<T>  getmaxflow(){
+    typename Graph::EdgeMap<T>  getmaxflow(){
       return preflow;
     }
 
@@ -135,33 +123,29 @@
   private:
     //For testing purposes only
     //Lists the node_properties
-    void write_property_vector(typename graph_type::NodeMap<T> a,
-			       //node_property_vector<graph_type, T> a, 
+    void write_property_vector(typename Graph::NodeMap<T> a,
+			       //node_property_vector<Graph, T> a, 
 			       char* prop_name="property"){
-      for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
-	cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a.get(i)<<endl;
+      for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) {
+	cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a[i]<<endl;
       }
       cout<<endl;
     }
 
     //Modifies the excess of the node and makes sufficient changes
-    void modify_excess(const NodeIt& a ,T v){
-	T old_value=excess.get(a);
-	excess.set(a,old_value+v);
+    void modify_excess(const Node& a ,T v){
+      //T old_value=excess[a];
+      excess[a] += 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(EdgeIt j, const T& v){
+    void modify_preflow(Edge j, const T& v){
 
-      //Auxiliary variable
-      T old_value;
-	
       //Modifiyng the edge
-      old_value=preflow.get(j);
-      preflow.set(j,old_value+v);
+      preflow[j] += v;
 
 
       //Modifiyng the head
@@ -174,13 +158,13 @@
 
     //Gives the active node to work with 
     //(depending on the implementation to be used)
-    NodeIt get_active_node(){
+    Node get_active_node(){
       
 
       switch(implementation) {
       case impl_highest_label : {
 
-	//First need to find the highest label for which there"s an active node
+	//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;
 	}
@@ -188,13 +172,13 @@
 	if( highest_active>=0) {
 	  
 
-	  NodeIt a=active_nodes[highest_active].front();
+	  Node a=active_nodes[highest_active].front();
 	  active_nodes[highest_active].pop_front();
 	  
 	  return a;
 	}
 	else {
-	  return NodeIt();
+	  return INVALID;
 	}
 	
 	break;
@@ -203,27 +187,27 @@
       case impl_fifo : {
 
 	if( ! fifo_nodes.empty() ) {
-	  NodeIt a=fifo_nodes.front();
+	  Node a=fifo_nodes.front();
 	  fifo_nodes.pop_front();
 	  return a;
 	}
 	else {
-	  return NodeIt();
+	  return INVALID;
 	}
 	break;
       }
       }
       //
-      return NodeIt();
+      return INVALID;
     }
 
     //Puts node 'a' among the active nodes
-    void make_active(const NodeIt& a){
+    void make_active(const Node& 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);
+	  active_nodes[level[a]].push_back(a);
 	  break;
 	case impl_fifo :
 	  fifo_nodes.push_back(a);
@@ -233,15 +217,15 @@
       }
 
       //Update highest_active label
-      if (highest_active<level.get(a)){
-	highest_active=level.get(a);
+      if (highest_active<level[a]){
+	highest_active=level[a];
       }
 
     }
 
     //Changes the level of node a and make sufficent changes
-    void change_level_to(NodeIt a, int new_value){
-      int seged = level.get(a);
+    void change_level_to(Node a, int new_value){
+      int seged = level[a];
       level.set(a,new_value);
       --num_of_nodes_on_level[seged];
       ++num_of_nodes_on_level[new_value];
@@ -257,10 +241,10 @@
 
       //Setting starting preflow, level and excess values to zero
       //This can be important, if the algorithm is run more then once
-      for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
+      for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) {
         level.set(i,0);
         excess.set(i,0);
-	for(OutEdgeIt j=G.template first<OutEdgeIt>(i); j.valid(); ++j) 
+	for(OutEdgeIt j=G.template first<OutEdgeIt>(i); G.valid(j); G.next(j)) 
 	  preflow.set(j, 0);
       }
       num_of_nodes_on_level[0]=number_of_nodes;
@@ -273,14 +257,47 @@
       //------------------------------------
       //This is the only part that uses BFS
       //------------------------------------
+
+      /*Reverse_bfs from t, to find the starting level.*/
+      //Copyright: Jacint
+      change_level_to(t,0);
+
+      std::queue<Node> bfs_queue;
+      bfs_queue.push(t);
+
+      while (!bfs_queue.empty()) {
+
+	Node v=bfs_queue.front();	
+	bfs_queue.pop();
+	int l=level[v]+1;
+
+	InEdgeIt e;
+	for(G.first(e,v); G.valid(e); G.next(e)) {
+	  Node w=G.tail(e);
+	  if ( level[w] == number_of_nodes && w != s ) {
+	    bfs_queue.push(w);
+	    //Node first=level_list[l];
+	    //if ( G.valid(first) ) left.set(first,w);
+	    //right.set(w,first);
+	    //level_list[l]=w;
+	    change_level_to(w, l);
+	    //level.set(w, l);
+	  }
+	}
+      }
+      change_level_to(s,number_of_nodes);
+      //level.set(s,number_of_nodes);
+
+      /*
       //Setting starting level values using reverse bfs
-      reverse_bfs<graph_type> rev_bfs(G,t);
+      reverse_bfs<Graph> rev_bfs(G,t);
       rev_bfs.run();
       //write_property_vector(rev_bfs.dist,"rev_bfs");
-      for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
+      for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(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
       //------------------------------------
@@ -292,10 +309,10 @@
       
       
       //we push as much preflow from s as possible to start with
-      for(OutEdgeIt j=G.template first<OutEdgeIt>(s); j.valid(); ++j){ 
-	modify_preflow(j,capacity.get(j) );
+      for(OutEdgeIt j=G.template first<OutEdgeIt>(s); G.valid(j); G.next(j)){ 
+	modify_preflow(j,capacity[j] );
 	make_active(G.head(j));
-	int lev=level.get(G.head(j));
+	int lev=level[G.head(j)];
 	if(highest_active<lev){
 	  highest_active=lev;
 	}
@@ -306,15 +323,15 @@
     
     //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(OutEdgeIt j, int& new_level){
+    bool is_admissible_forward_edge(Edge j, int& new_level){
 
-      if (capacity.get(j)>preflow.get(j)){
-	if(level.get(G.tail(j))==level.get(G.head(j))+1){
+      if (capacity[j]>preflow[j]){
+	if(level[G.tail(j)]==level[G.head(j)]+1){
 	  return true;
 	}
 	else{
-	  if (level.get(G.head(j)) < new_level)
-	    new_level=level.get(G.head(j));
+	  if (level[G.head(j)] < new_level)
+	    new_level=level[G.head(j)];
 	}
       }
       return false;
@@ -322,16 +339,16 @@
 
     //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(InEdgeIt j, int& new_level){
+    bool is_admissible_backward_edge(Edge j, int& new_level){
       
-      if (0<preflow.get(j)){
-	if(level.get(G.tail(j))==level.get(G.head(j))-1){
+      if (0<preflow[j]){
+	if(level[G.tail(j)]==level[G.head(j)]-1){
 	 
 	  return true;
 	}
 	else{
-	  if (level.get(G.tail(j)) < new_level)
-	    new_level=level.get(G.tail(j));
+	  if (level[G.tail(j)] < new_level)
+	    new_level=level[G.tail(j)];
 	}
 	
       }
@@ -341,59 +358,57 @@
  
   };  //class preflow_push  
 
-  template<typename graph_type, typename T>
-    T preflow_push<graph_type, T>::run() {
+  template<typename Graph, typename T>
+    T preflow_push<Graph, T>::run() {
+    
+    //We need a residual graph
+    ResGraphType res_graph(G, preflow, capacity);
     
     preprocess();
     //write_property_vector(level,"level");
     T e,v;
-    NodeIt a;
-    while (a=get_active_node(), a.valid()){
+    Node a;
+    while (a=get_active_node(), G.valid(a)){
       
-      //cout<<G.id(a)<<endl;
-      //write_property_vector(excess,"excess");
-      //write_property_vector(level,"level");
+      bool go_to_next_node=false;
+      e = excess[a];
+      while (!go_to_next_node){
 
-
-      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
 	{
 	  OutEdgeIt j=G.template first<OutEdgeIt>(a);
-	  while (j.valid() && e){
+	  while (G.valid(j) && e){
 
 	    if (is_admissible_forward_edge(j,new_level)){
-	      v=min(e,capacity.get(j) - preflow.get(j));
+	      v=min(e,capacity[j] - preflow[j]);
 	      e -= v;
 	      //New node might become active
-	      if (excess.get(G.head(j))==0){
+	      if (excess[G.head(j)]==0){
 		make_active(G.head(j));
 	      }
 	      modify_preflow(j,v);
 	    }
-	    ++j;
+	    G.next(j);
 	  }
 	}
 	//In edges to node a
 	{
 	  InEdgeIt j=G.template first<InEdgeIt>(a);
-	  while (j.valid() && e){
+	  while (G.valid(j) && e){
 	    if (is_admissible_backward_edge(j,new_level)){
-	      v=min(e,preflow.get(j));
+	      v=min(e,preflow[j]);
 	      e -= v;
 	      //New node might become active
-	      if (excess.get(G.tail(j))==0){
+	      if (excess[G.tail(j)]==0){
 		make_active(G.tail(j));
 	      }
 	      modify_preflow(j,-v);
 	    }
-	    ++j;
+	    G.next(j);
 	  }
 	}
 
@@ -410,7 +425,7 @@
 	  //change_level_to(a,new_level+1);
 	  
 	  //Level remains empty
-	  if (num_of_nodes_on_level[level.get(a)]==1){
+	  if (num_of_nodes_on_level[level[a]]==1){
 	    change_level_to(a,number_of_nodes);
 	    //go_to_next_node=True;
 	  }
@@ -437,7 +452,7 @@
 	}//if (0==e)
       }
     }
-    maxflow_value = excess.get(t);
+    maxflow_value = excess[t];
     return maxflow_value;
   }//run
 
diff -r 7ac0d4e8a31c -r f5461f8bc59b src/work/athos/preflow_push_wogw.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/athos/preflow_push_wogw.h	Thu Apr 15 17:03:44 2004 +0000
@@ -0,0 +1,463 @@
+#ifndef HUGO_PREFLOW_PUSH_HH
+#define HUGO_PREFLOW_PUSH_HH
+
+//#include <algorithm>
+#include <list>
+#include <vector>
+#include <queue>
+//#include "pf_hiba.hh"
+//#include <marci_list_graph.hh>
+//#include <marci_graph_traits.hh>
+#include <invalid.h>
+//#include <reverse_bfs.hh>
+
+using namespace std;
+
+namespace hugo {
+
+  template <typename Graph, typename T>
+  class preflow_push {
+
+    //Useful typedefs
+    typedef typename Graph::Node Node;
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::Edge Edge;
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    typedef typename Graph::InEdgeIt InEdgeIt;
+
+
+    //---------------------------------------------
+    //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& G;
+    Node s;
+    Node t;
+    typename Graph::EdgeMap<T> &capacity;
+
+    //output
+    typename Graph::EdgeMap<T> preflow;
+    T maxflow_value;
+  
+    //auxiliary variables for computation
+    //The number of the nodes
+    int number_of_nodes;
+    //A nodemap for the level
+    typename Graph::NodeMap<int> level;
+    //A nodemap for the excess
+    typename Graph::NodeMap<T> excess;
+    
+    //Number of nodes on each level
+    vector<int> num_of_nodes_on_level;
+    
+    //For the FIFO implementation
+    list<Node> fifo_nodes;
+    //For 'highest label' implementation
+    int highest_active;
+    //int second_highest_active;
+    vector< list<Node> > active_nodes;
+
+  public:
+  
+    //Constructing the object using the graph, source, sink and capacity vector
+    preflow_push(
+		      Graph& _G, 
+		      Node _s, 
+		      Node _t, 
+		      typename Graph::EdgeMap<T> & _capacity)
+      : G(_G), s(_s), t(_t), 
+	capacity(_capacity), 
+	preflow(_G),
+	//Counting the number of nodes
+	//number_of_nodes(count(G.first<EachNodeIt>())),
+	number_of_nodes(G.nodeNum()),
+
+	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.clear();
+	active_nodes.resize(2*number_of_nodes-1);
+	
+	break;
+      }
+      default:
+	break;
+      }
+
+    }
+
+    //Returns the value of a maximal flow 
+    T run();
+  
+    typename Graph::EdgeMap<T>  getmaxflow(){
+      return preflow;
+    }
+
+
+  private:
+    //For testing purposes only
+    //Lists the node_properties
+    void write_property_vector(typename Graph::NodeMap<T> a,
+			       //node_property_vector<Graph, T> a, 
+			       char* prop_name="property"){
+      for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) {
+	cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a[i]<<endl;
+      }
+      cout<<endl;
+    }
+
+    //Modifies the excess of the node and makes sufficient changes
+    void modify_excess(const Node& a ,T v){
+      //T old_value=excess[a];
+      excess[a] += 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 j, const T& v){
+
+      //Modifiyng the edge
+      preflow[j] += 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 get_active_node(){
+      
+
+      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 a=active_nodes[highest_active].front();
+	  active_nodes[highest_active].pop_front();
+	  
+	  return a;
+	}
+	else {
+	  return INVALID;
+	}
+	
+	break;
+	
+      }
+      case impl_fifo : {
+
+	if( ! fifo_nodes.empty() ) {
+	  Node a=fifo_nodes.front();
+	  fifo_nodes.pop_front();
+	  return a;
+	}
+	else {
+	  return INVALID;
+	}
+	break;
+      }
+      }
+      //
+      return INVALID;
+    }
+
+    //Puts node 'a' among the active nodes
+    void make_active(const Node& a){
+      //s and t never become active
+      if (a!=s && a!= t){
+	switch(implementation){
+	case impl_highest_label :
+	  active_nodes[level[a]].push_back(a);
+	  break;
+	case impl_fifo :
+	  fifo_nodes.push_back(a);
+	  break;
+	}
+
+      }
+
+      //Update highest_active label
+      if (highest_active<level[a]){
+	highest_active=level[a];
+      }
+
+    }
+
+    //Changes the level of node a and make sufficent changes
+    void change_level_to(Node a, int new_value){
+      int seged = level[a];
+      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(){
+
+      //---------------------------------------
+      //Initialize parameters
+      //---------------------------------------
+
+      //Setting starting preflow, level and excess values to zero
+      //This can be important, if the algorithm is run more then once
+      for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) {
+        level.set(i,0);
+        excess.set(i,0);
+	for(OutEdgeIt j=G.template first<OutEdgeIt>(i); G.valid(j); G.next(j)) 
+	  preflow.set(j, 0);
+      }
+      num_of_nodes_on_level[0]=number_of_nodes;
+      highest_active=0;
+      //---------------------------------------
+      //Initialize parameters
+      //---------------------------------------
+
+      
+      //------------------------------------
+      //This is the only part that uses BFS
+      //------------------------------------
+
+      /*Reverse_bfs from t, to find the starting level.*/
+      //Copyright: Jacint
+      change_level_to(t,0);
+
+      std::queue<Node> bfs_queue;
+      bfs_queue.push(t);
+
+      while (!bfs_queue.empty()) {
+
+	Node v=bfs_queue.front();	
+	bfs_queue.pop();
+	int l=level[v]+1;
+
+	InEdgeIt e;
+	for(G.first(e,v); G.valid(e); G.next(e)) {
+	  Node w=G.tail(e);
+	  if ( level[w] == number_of_nodes && w != s ) {
+	    bfs_queue.push(w);
+	    //Node first=level_list[l];
+	    //if ( G.valid(first) ) left.set(first,w);
+	    //right.set(w,first);
+	    //level_list[l]=w;
+	    change_level_to(w, l);
+	    //level.set(w, l);
+	  }
+	}
+      }
+      change_level_to(s,number_of_nodes);
+      //level.set(s,number_of_nodes);
+
+      /*
+      //Setting starting level values using reverse bfs
+      reverse_bfs<Graph> rev_bfs(G,t);
+      rev_bfs.run();
+      //write_property_vector(rev_bfs.dist,"rev_bfs");
+      for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(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(OutEdgeIt j=G.template first<OutEdgeIt>(s); G.valid(j); G.next(j)){ 
+	modify_preflow(j,capacity[j] );
+	make_active(G.head(j));
+	int lev=level[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(Edge j, int& new_level){
+
+      if (capacity[j]>preflow[j]){
+	if(level[G.tail(j)]==level[G.head(j)]+1){
+	  return true;
+	}
+	else{
+	  if (level[G.head(j)] < new_level)
+	    new_level=level[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(Edge j, int& new_level){
+      
+      if (0<preflow[j]){
+	if(level[G.tail(j)]==level[G.head(j)]-1){
+	 
+	  return true;
+	}
+	else{
+	  if (level[G.tail(j)] < new_level)
+	    new_level=level[G.tail(j)];
+	}
+	
+      }
+      return false;
+    }
+
+ 
+  };  //class preflow_push  
+
+  template<typename Graph, typename T>
+    T preflow_push<Graph, T>::run() {
+    
+    preprocess();
+    //write_property_vector(level,"level");
+    T e,v;
+    Node a;
+    while (a=get_active_node(), G.valid(a)){
+      
+      //cout<<G.id(a)<<endl;
+      //write_property_vector(excess,"excess");
+      //write_property_vector(level,"level");
+
+
+      bool go_to_next_node=false;
+      e = excess[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
+	{
+	  OutEdgeIt j=G.template first<OutEdgeIt>(a);
+	  while (G.valid(j) && e){
+
+	    if (is_admissible_forward_edge(j,new_level)){
+	      v=min(e,capacity[j] - preflow[j]);
+	      e -= v;
+	      //New node might become active
+	      if (excess[G.head(j)]==0){
+		make_active(G.head(j));
+	      }
+	      modify_preflow(j,v);
+	    }
+	    G.next(j);
+	  }
+	}
+	//In edges to node a
+	{
+	  InEdgeIt j=G.template first<InEdgeIt>(a);
+	  while (G.valid(j) && e){
+	    if (is_admissible_backward_edge(j,new_level)){
+	      v=min(e,preflow[j]);
+	      e -= v;
+	      //New node might become active
+	      if (excess[G.tail(j)]==0){
+		make_active(G.tail(j));
+	      }
+	      modify_preflow(j,-v);
+	    }
+	    G.next(j);
+	  }
+	}
+
+	//if (G.id(a)==999)
+	//cout<<new_level<<" e: "<<e<<endl;
+	//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
+	  
+	  //change_level_to(a,new_level+1);
+	  
+	  //Level remains empty
+	  if (num_of_nodes_on_level[level[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[t];
+    return maxflow_value;
+  }//run
+
+
+}//namespace hugo
+
+#endif //PREFLOW_PUSH_HH
diff -r 7ac0d4e8a31c -r f5461f8bc59b src/work/athos/reverse_bfs.hh
--- a/src/work/athos/reverse_bfs.hh	Thu Apr 15 14:41:20 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,103 +0,0 @@
-/*
-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  hugo {
-
-  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 hugo
-
-#endif //REVERSE_BFS_HH
-
-