масштабирование проблема реализации потока

Question

Я пытался сделать программу для вычисления масштабного-макс алгоритм потока:

до сих пор у меня есть код функции, чтобы получить максимум веса и масштабирования maxflow, который я знаю, почти такой же, как алгоритм Форда Фулкерсона, только тот, который обновляет значения с помощью дельта; мой код:

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) 

Я вижу, что она печатает 23 для MaxFlow и 32 для scalingMaxFlow, что я делаю не так?

Благодаря

Answer 1

scalingMaxFlow не прекращается, когда FindPath(source, target, []) возвращает None, а затем треугольник никогда не обновляется. Это похоже на ваш пример.