bangnaga

Ford-fulkerson.py

May 1st, 2012
797
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Edge(object):
  2.     def __init__(self, u, v, w):
  3.         self.source = u
  4.         self.sink = v
  5.         self.capacity = w
  6.     def __repr__(self):
  7.         return "%s->%s:%s" % (self.source, self.sink, self.capacity)
  8.  
  9. class FlowNetwork(object):
  10.     def __init__(self):
  11.         self.adj = {}
  12.         self.flow = {}
  13.  
  14.     def add_vertex(self, vertex):
  15.         self.adj[vertex] = []
  16.  
  17.     def get_edges(self, v):
  18.         return self.adj[v]
  19.  
  20.     def add_edge(self, u, v, w=0):
  21.         if u == v:
  22.             raise ValueError("u == v")
  23.         edge = Edge(u,v,w)
  24.         redge = Edge(v,u,0)
  25.         edge.redge = redge
  26.         redge.redge = edge
  27.         self.adj[u].append(edge)
  28.         self.adj[v].append(redge)
  29.         self.flow[edge] = 0
  30.         self.flow[redge] = 0
  31.  
  32.     def find_path(self, source, sink, path):
  33.         if source == sink:
  34.             return path
  35.         for edge in self.get_edges(source):
  36.             residual = edge.capacity - self.flow[edge]
  37.             if residual > 0 and not (edge,residual) in path:
  38.                 result = self.find_path( edge.sink, sink, path + [(edge,residual)] )
  39.                 if result != None:
  40.                     return result
  41.  
  42.     def max_flow(self, source, sink):
  43.         path = self.find_path(source, sink, [])
  44.         while path != None:
  45.             flow = min(res for edge,res in path)
  46.             for edge,res in path:
  47.                 self.flow[edge] += flow
  48.                 self.flow[edge.redge] -= flow
  49.             path = self.find_path(source, sink, [])
  50.         return sum(self.flow[edge] for edge in self.get_edges(source))
  51.  
  52. g=FlowNetwork()
  53. map(g.add_vertex, ['s','o','p','q','r','t'])
  54. g.add_edge('s','o',3)
  55. g.add_edge('s','p',3)
  56. g.add_edge('o','p',2)
  57. g.add_edge('o','q',3)
  58. g.add_edge('p','r',2)
  59. g.add_edge('r','t',3)
  60. g.add_edge('q','r',4)
  61. g.add_edge('q','t',2)
  62. print g.max_flow('s','t')
RAW Paste Data