Changeset 331:f5461f8bc59b in lemon-0.x for src/work

Timestamp:

04/15/04 19:03:44 (21 years ago)

Author:

athos

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@449

Message:

Elkezdtem atirni a preflow_push-t. Csinaltam egy backupot graph wrapper nelkul (without gw, azaz wogw)

Location:

src/work/athos

Files:

• makefile (modified) (1 diff)
• pf_demo.cc (modified) (5 diffs)
• preflow_push.hh (modified) (27 diffs)
• preflow_push_wogw.h (added)
• reverse_bfs.hh (deleted)

src/work/athos/makefile

@@ -7 +7 @@
 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

src/work/athos/pf_demo.cc

@@ -3 +3 @@
 #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"
@@ -14 +14 @@
 {
 
-  
-  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;
 
   /*
@@ -30 +23 @@
 
 
-  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);
   */
 
@@ -66 +59 @@
   //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;
 
@@ -152 +103 @@
   return 0;
 }
-
-
-
-
-
-
-
-
-

src/work/athos/preflow_push.hh

@@ -1 @@
-#ifndef PREFLOW_PUSH_HH
-#define PREFLOW_PUSH_HH
-
-#include <algorithm>
+#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 <reverse_bfs.hh>
+#include <invalid.h>
+#include <graph_wrapper.h>
+//#include <reverse_bfs.hh>
 
 using namespace std;
@@ -15 +17 @@
 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;
-
-
-
-    /*
-    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;
-    */
+    //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;
+
 
     //---------------------------------------------
@@ -56 +45 @@
   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
@@ -79 +66 @@
     
     //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:
@@ -89 +76 @@
     //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), 
@@ -115 +102 @@
       switch(implementation){
       case impl_highest_label :{
+        active_nodes.clear();
         active_nodes.resize(2*number_of_nodes-1);
-        active_nodes.clear();
+        
         break;
       }
@@ -128 +116 @@
     T run();
   
-    typename graph_type::EdgeMap<T>  getmaxflow(){
+    typename Graph::EdgeMap<T>  getmaxflow(){
       return preflow;
     }
@@ -136 +124 @@
     //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;
@@ -146 +134 @@
 
     //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;
     }
   
@@ -155 +143 @@
     //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){
-
-      //Auxiliary variable
-      T old_value;
-        
+    void modify_preflow(Edge j, const T& v){
+
       //Modifiyng the edge
-      old_value=preflow.get(j);
-      preflow.set(j,old_value+v);
+      preflow[j] += v;
 
 
@@ -175 +159 @@
     //Gives the active node to work with 
     //(depending on the implementation to be used)
-    NodeIt get_active_node(){
+    Node get_active_node(){
       
 
@@ -181 +165 @@
       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;
@@ -189 +173 @@
           
 
-          NodeIt a=active_nodes[highest_active].front();
+          Node a=active_nodes[highest_active].front();
           active_nodes[highest_active].pop_front();
           
@@ -195 +179 @@
         }
         else {
-          return NodeIt();
+          return INVALID;
         }
         
@@ -204 +188 @@
 
         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;
@@ -215 +199 @@
       }
       //
-      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 :
@@ -234 +218 @@
 
       //Update highest_active label
-      if (highest_active<level.get(a)){
-        highest_active=level.get(a);
+      if (highest_active<level[a]){
+        highest_active=level[a];
       }
 
@@ -241 +225 @@
 
     //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];
@@ -258 +242 @@
       //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);
       }
@@ -274 +258 @@
       //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
@@ -293 +310 @@
       
       //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;
@@ -307 +324 @@
     //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){
-
-      if (capacity.get(j)>preflow.get(j)){
-        if(level.get(G.tail(j))==level.get(G.head(j))+1){
+    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.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)];
         }
       }
@@ -323 +340 @@
     //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){
-      
-      if (0<preflow.get(j)){
-        if(level.get(G.tail(j))==level.get(G.head(j))-1){
+    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.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)];
         }
         
@@ -342 +359 @@
   };  //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()){
-      
-      //cout<<G.id(a)<<endl;
-      //write_property_vector(excess,"excess");
-      //write_property_vector(level,"level");
-
-
+    Node a;
+    while (a=get_active_node(), G.valid(a)){
+      
       bool go_to_next_node=false;
-      e = excess.get(a);
+      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 (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);
           }
         }
@@ -384 +399 @@
         {
           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);
           }
         }
@@ -411 +426 @@
           
           //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;
@@ -438 +453 @@
       }
     }
-    maxflow_value = excess.get(t);
+    maxflow_value = excess[t];
     return maxflow_value;
   }//run