Ford-Fulkerson algorithm, from http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm minimum_cut() is added by naoya_t

ford_fulkerson.py

import Queue

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" % (str(self.source), str(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 is not defined in Edge class
        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 not (edge,residual) in path:
                result = self.find_path( edge.sink, sink, path + [(edge,residual)] ) 
                if result != None:
                    return result

    def max_flow(self, source, sink):
        path = self.find_path(source, sink, [])
        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
            path = self.find_path(source, sink, [])
        return sum(self.flow[edge] for edge in self.get_edges(source))

    def minimum_cut(self, source, sink):
        q = Queue.Queue()
        q.put(source)
        reachable = set()
        while not q.empty():
            source = q.get()
            reachable.add(source)
            for edge in self.adj[source]:
                if edge.sink in reachable: continue
                if 0 <= self.flow[edge] < edge.capacity:
                    q.put(edge.sink)
        return reachable


if __name__ == '__main__':
    g = FlowNetwork()
    map(g.add_vertex, ['s','o','p','q','r','t'])
    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')
    print g.minimum_cut('s','t')

    g = FlowNetwork()
    map(g.add_vertex, ['a','b','c','d','e','f'])
    g.add_edge('a','b',6)
    g.add_edge('a','c',8)
    g.add_edge('b','d',6)
    g.add_edge('b','e',3)
    g.add_edge('c','d',3)
    g.add_edge('c','e',3)
    g.add_edge('d','f',8)
    g.add_edge('e','f',6)
    print g.max_flow('a','f')
    print g.minimum_cut('a','f')

    g = FlowNetwork()
    map(g.add_vertex, ['a','b','c','d','e','f'])
    g.add_edge('a','b',2)
    g.add_edge('a','c',4)
    g.add_edge('b','c',1)
    g.add_edge('b','d',1)
    g.add_edge('c','d',3)
    g.add_edge('c','e',2)
    g.add_edge('d','e',1)
    g.add_edge('d','f',1)
    g.add_edge('e','f',3)
    print g.max_flow('a','f')
    print g.minimum_cut('a','f')