Maximum Flow, Minimum Cut and the Ford-Fulkerson Method

Today I'm studying flow graphs and disjoint sets data structure.

Maximum flow falls into the category of combinatoric optimization problems. The Ford-Fulkerson method, published in 1956, is a way of solving the computation of maximum flow through a flow graph, which could represent a network or a set of fluid pipes. It is considered a method, not an algorithm, since there are pathological cases that will never terminate, and further, have no guarantee of convergence toward optimality.

The method follows all paths from a source node to a sink node, and augments the available capacity, reducing the capacity by the minimum available capacity in the path. The reduction in capacity is accumulated, and once there are no more paths available (meaning capacity is at maximum at some edge on each path), the accumulated value is the maximum value, and is also the minimum cut.

Here is Python code (from Wikipedia) that calculates maximum flow in a flow graph, slightly changed for safety when comparing a value to None:

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()