FFEK, optimized a bit the bfs part and fixed a bug in the backtracking function

ffek.py

#!/usr/bin/env python
from collections import defaultdict, deque

class Edge(object):    
    def __init__(self, tail, head, capacity, name=None, flow=0):
    	self.name = tail + "-" + head if not name else name
        self.tail = tail
        self.head = head
        self.flow = flow
        self.capacity = capacity
        
    def is_forward(self, a, b):
        return (self.tail, self.head) == (a, b)
        
    def __str__(self):
        fmt = "edge \"%s\":\t (%s) ---%d/%d---> (%s)"
        return fmt % (self.name, self.tail, self.flow, self.capacity, self.head)
                    
                    
class Network(object):
    def __init__(self, source, sink, *edges):
        self.source = source
        self.sink = sink
        # search edges by name. We might have multiple edges leading to the same
        # nodes:
        self._edges = dict((edge.name, edge) for edge in edges)
        # keep track of the edges and backedges by node:
        self.edges = defaultdict(list)
        self.backedges = defaultdict(list)
        
        for edge in edges:
            self.edges[edge.tail].append(edge)
            self.backedges[edge.head].append(edge)
        
    def agumentate(self, path, delta):
        for agumentation_edge, is_forward in path:
            edge = self._edges[agumentation_edge.name]
            edge.flow += delta if is_forward else -delta

    def ffek(self):
        paths = []
        agumentation_path, delta = self.ek()
        while agumentation_path:
            self.agumentate(agumentation_path, delta)
            paths.append(e for e, d in agumentation_path)
            agumentation_path, delta = self.ek()
        return self, paths
         
    def __str__(self):
        s = "Network (flow: %d)" % self.flow
        return s + ''.join("\n\t- %s" % e for e in self._edges.itervalues())

    def ek(self):
        to_visit = deque([(None, self.source, None, None)], len(self._edges))
        visited = set()
        steps = []
        while to_visit:
            edge, node, parent, delta = to_visit.popleft()
            
            if node in visited: continue
            visited.add(node)
            
            steps.append((edge, node, parent, delta))
                
            for edge in (e for e in self.edges[node] if e.flow < e.capacity):
                to_visit.append((edge, edge.head, node, edge.capacity - edge.flow))
            
            for edge in (e for e in self.backedges[node] if e.flow > 0):
                to_visit.append((edge, edge.tail, node, edge.flow))
                
        return backtrack(self.sink, steps)
        
    @property
    def flow(self):
        return sum(edge.flow for edge in self._edges.values())
        

minimum = lambda a, b: min(a, b) if a and b else a or b

def backtrack(target, steps):
    delta = None # +inf
    path = []
    for edge, node, parent, delta1 in reversed(steps):
        if edge and node == target:
            path.append((edge, edge.is_forward(parent, node)))
            delta = minimum(delta, delta1)
            target = parent
    return path, delta or 0


if __name__ == "__main__":
    edges = [Edge(*t) for t in (
        ("f", "a", 12),
        ("a", "b", 30),
        ("b", "s", 10),
        ("a", "s", 20),
        ("s", "f", 10),
    )]
    
    net, paths = Network("f", "s", *edges).ffek()
    print net
    print "Network agumentation paths:"
    for i, p in enumerate(paths):
        print "step #%d" % (i + 1)
        for e in p:
            print "\t", e