pythonpeixun
diff --git a/‎maximum_flow/max-flows.py
Lines changed: 72 additions & 0 deletions b/‎maximum_flow/max-flows.py
Lines changed: 72 additions & 0 deletions
@@ -0,0 +1,72 @@
+class Edge(object):
+    def __init__(self, u, v, w):
+        self.source = u
+        self.sink = v
+        self.capacity = w
+
+    def __repr__(self):
         return "%s->%s:%s" % (self.source, self.sink, self.capacity)
+
+
+class FlowNetwork(object):
+    def __init__(self):
+        self.adj = {}
+        self.flow = {}
+
+    def add_vertex(self, vertex):
+        self.adj[vertex] = []
+
+    def get_edges(self, v):
+        return self.adj[v]
+
+    def add_edge(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)
+        self.flow[edge] = 0
+        self.flow[redge] = 0
+
+    def find_path(self, source, sink, path):
+        if source == sink:
+            return path
+        for edge in self.get_edges(source):
+            residual = edge.capacity - self.flow[edge]
+            if residual > 0 and edge not in path:
+                result = self.find_path(edge.sink, sink, path + [edge])
+                if result is not None:
+                    return result
+
+    def max_flow(self, source, sink):
+        path = self.find_path(source, sink, [])
+        while path is not None:
+            residuals = [edge.capacity - self.flow[edge] for edge in path]
+            flow = min(residuals)
+            for edge in path:
+                self.flow[edge] += flow
+                self.flow[edge.redge] -= flow
+            path = self.find_path(source, sink, [])
+        return sum(self.flow[edge] for edge in self.get_edges(source))
+
+
+def main():
+    g = FlowNetwork()
+    [g.add_vertex(v) for v in "sopqrt"]
+    
+    g.add_edge('s', 'o', 3)
+    g.add_edge('s', 'p', 3)
+    g.add_edge('o', 'p', 2)
+    g.add_edge('o', 'q', 3)
+    g.add_edge('p', 'r', 2)
+    g.add_edge('r', 't', 3)
+    g.add_edge('q', 'r', 4)
+    g.add_edge('q', 't', 2)
+
+    print(g.max_flow('s', 't'))
+
+if __name__ == '__main__':
+    main()