title: Ford Fulkerson (Maximum flow, minimum cut) using DFS, adjacency list implementation in Python
body: <p>I am coding in Python and I am a beginner. I am stuck with Ford-Fulkerson DFS adjacency list code. Somehow, I am not able to get the flow variable assigned correctly. It would be great if somebody can help me here. The problem seems to be with the flow variable in which information is not getting transmitted correctly through different functions.</p>
  <pre><code>#..............................................................................
  Code in Python is as follows:  Answer to the problem1 is 11. Answer to problem2 is 19. 
  #...................................................................
  
  '''code'''
  
  class Edge:
      def __init__(self, v1,v2, capacity,flow):
          self.from1 = v1
          self.to1 = v2
          self.capacity = capacity
          self.residual=[]
          self.flow = flow
          
          
      def isResidual(self):
          return self.capacity == 0
      
      def remaining_capacity(self):
          
          kk = self.capacity - self.flow
          print(&quot;Line 22, inside remaining capacity, kk,self.flow&quot;,kk,self.flow )
          return self.capacity - self.flow
          
      def augment(self,bottleneck):
          print(&quot;Line 24, INside Augment, self.flow,self.residual.flow,, self.from1, self.to1, self.capacity &quot;, self.flow,self.residual.flow, self.from1, self.to1, self.capacity )
          self.flow =+ bottleneck
          self.residual.flow =- bottleneck
          #self.residual.capacity =- bottleneck
          #self.capacity =- bottleneck
          #self.residual.capacity =- bottleneck
          
          
  class Graph:
      def __init__(self, numvertices):
          self.m = numvertices
          self.graph = []
          self.initialize_empty_flow_graph()
          
      def initialize_empty_flow_graph(self):
          
          for i in range(self.m):
              self.graph.append([])
              
      def add_edge(self, v1,v2,capacity,flow):
          e1 = Edge(v1,v2, capacity,flow)
          e2 = Edge(v2,v1,0,flow)
          
          e1.residual = e2
          e2.residual = e1
                  self.graph[v1].append(e1)
          self.graph[v2].append(e2)
          
  class ford_fulkerson:
      def __init__(self, Graph, numvertices):
          #self.n = numvertices
          self.n = numvertices
          self.s = self.n - self.n # source index
          self.t = self.n - 1  # sink index
          self.visitedToken = 0
          #self.visited = list(range(0,self.n))
          self.visited = list(range(100,n+100))
          #self.visited = list(range(-self.n, 0))
          self.minCut = [False]*self.n
          self.maxFlow = 0
          
      def solve(self,Graph):
          
          while True:
                  
              print(&quot;-------Line 293---------, in solve&quot;)
              f = self.dfs(Graph, self.s, flow = float(&quot;inf&quot;))
              print(&quot;Line 79, bottleneck value in solve&quot;, f)
              self.visitedToken = self.visitedToken+1
              self.maxFlow = self.maxFlow+f
              
              print(&quot;Line 83: self.maxFlow and F&quot;,self.maxFlow, f )
              if f == 0:
                  break
              
      def dfs(self,Graph, node, flow):
          print(&quot;-----------a-------------------&quot;)
          #print()
          
          if (node == self.t):
              print(&quot;Line 92,flow&quot;, flow)
              return flow
          
          self.visited[node] = self.visitedToken
          edges = Graph.graph[node]
          for edge in edges:
              print(&quot;Line 97:Inside for loop,edge.from1,edge.to1,edge.capacity&quot;,edge.from1,edge.to1,edge.capacity)
              if (edge.remaining_capacity()&gt;0 and self.visited[edge.to1] != self.visitedToken):
                  print(&quot;Line 99:Inside if condition, for loop&quot;)
                  bottleneck = self.dfs(Graph,edge.to1, min(flow, edge.remaining_capacity()))
                  #flow = edge.flow
                  print(&quot;Line 102, bottleneck&quot;,bottleneck)
                  if (bottleneck &gt; 0):
                      
                      edge.augment(bottleneck)
                      
                      return bottleneck
          return 0
      
              
  #.......................
  # Problem 1: # Answer is 11.      
  
  n = 4
  g = Graph(n) # nodes+1source node +1 sink node
  
  s = n-n # source node is n-2; 
  t = n-1 # sink node is n-1
  flow = 0
  g.add_edge(s, 1, 7,flow)
  g.add_edge(s, 2, 12,flow)
  g.add_edge(1, 2, 9,flow)
  g.add_edge(1, t, 10,flow);
  g.add_edge(2, t, 4,flow);
  
  ford = ford_fulkerson(g,n)
  ford.solve(g)
  
  #.......................
  # Problem 1: # Answer is 19
  
  n = 6
  g = adjacency_set_graph(n, directed = False) # nodes+1source node +1 sink node
  s = n-n # source node is n-2; 
  t = n-1 # sink node is n-1
  flow = 0
  g.add_edge(s, 1, 10,flow)
  g.add_edge(s, 2, 10,flow)
  
  g.add_edge(1, 2, 2,flow)
  g.add_edge(1, 3, 4,flow)
  g.add_edge(1, 4, 8,flow)
  g.add_edge(2, 4, 9,flow)
  g.add_edge(4, 3, 6,flow)
  
  g.add_edge(3, t, 10,flow);
  g.add_edge(4, t, 10,flow);
  ford = ford_fulkerson(g)
  print(ford.n,ford.s,ford.t)
  ford.solve(g)
      
  </code></pre>