CODEWITHSUNDEEP
python
Layla
Layla

Reputation: 5466

scaling flow implementation issue

I have been trying to make a program for computing the scaling-max flow algorithm:

enter image description here

so far I have code a function to get the maximum of the weights and the scaling maxflow, which I know is almost the same as the Ford Fulkerson algorithm, only that updates the values with a delta; my code is:

import math

class Edge(object):
  def __init__(self, u, v, w):
    self.source = u
    self.target = v
    self.capacity = w

  def __repr__(self):
    return "%s->%s:%s" % (self.source, self.target, self.capacity)


class FlowNetwork(object):
  def  __init__(self):
    self.adj = {}
    self.flow = {}

  def AddVertex(self, vertex):
    self.adj[vertex] = []

  def GetEdges(self, v):
    return self.adj[v]

  def AddEdge(self, u, v, w = 0):
    if u == v:
      raise ValueError("u == v")
    edge = Edge(u, v, w)
    redge = Edge(v, u, 0)
    edge.redge = redge
    redge.redge = edge
    self.adj[u].append(edge)
    self.adj[v].append(redge)
    # Intialize all flows to zero
    self.flow[edge] = 0
    self.flow[redge] = 0

  def FindPath(self, source, target, path):
    if source == target:
      return path
    for edge in self.GetEdges(source):
      residual = edge.capacity - self.flow[edge]
      if residual > 0 and not (edge, residual) in path:
        result = self.FindPath(edge.target, target, path + [(edge, residual)])
        if result != None:
          return result

  def MaxFlow(self, source, target):
    path = self.FindPath(source, target, [])
    print 'path after enter MaxFlow: %s' % path
    for key in self.flow:
      print '%s:%s' % (key,self.flow[key])
    print '-' * 20
    while path != None:
      flow = min(res for edge, res in path)
      for edge, res in path:
        self.flow[edge] += flow
        self.flow[edge.redge] -= flow
      for key in self.flow:
        print '%s:%s' % (key,self.flow[key])
      path = self.FindPath(source, target, [])
      print 'path inside of while loop: %s' % path
    for key in self.flow:
      print '%s:%s' % (key,self.flow[key])
    return sum(self.flow[edge] for edge in self.GetEdges(source))

  def maxWeight(self):
    wmax=0
    for i in self.adj:
        for j in self.GetEdges(i):
            #print j.capacity
            if j.capacity>wmax:
                wmax=j.capacity
    return wmax

  def __iter__(self):
    return iter(self.adj.values())      


  def scalingMaxFlow(self,source,target):
    delta=2**int(math.log(self.maxWeight(),2))
    path = self.FindPath(source, target, [])
    while delta>=1:
      while path!=None:
        for edge, res in path:
           self.flow[edge] += delta
           self.flow[edge.redge] -= delta 
        path = self.FindPath(source, target, [])
      delta//=2
    #print delta
    return sum(self.flow[edge] for edge in self.GetEdges(source))

if __name__ == "__main__":
  g = FlowNetwork()
  map(g.AddVertex, ['s', 'o', 'p', 'q', 'r', 't'])
  g.AddEdge('s', 'o', 16)
  g.AddEdge('s', 'q', 13)
  g.AddEdge('o', 'q', 10)
  g.AddEdge('q', 'o', 4)
  g.AddEdge('o', 'p', 12)
  g.AddEdge('q', 'r', 14)
  g.AddEdge('p','q',9)
  g.AddEdge('p', 't', 20)
  g.AddEdge('r', 'p', 7)
  g.AddEdge('r', 't', 4)

I see that it prints 23 for the MaxFlow and 32 for the scalingMaxFlow, what am I doing wrong?

Thanks

Upvotes: 0

Views: 239

Answers (1)

user1415946
user1415946

Reputation:

scalingMaxFlow does not terminate when FindPath(source, target, []) returns None, as then delta is never updated. This seems to be the case in your example.

Upvotes: 1

Related Questions