Maximum flow - Ford-Fulkerson: Undirected graph

Question

I am trying to solve the maxium flow problem for a graph using Ford–Fulkerson algorithm. The algorithm is only described with a directed graph. What about when the graph is undirected?

What I have done to mimic an undirected graph is to use two directed edges between a pair of vertices. What confuses me is: Should each of these edges then have a residual edge or is the "opposite" directed edge the residual edge?

I have assumed the last but my algorithm seems to go in an infinite loop. I hope any of you can give me some help. Below is my own implementation. I am using DFS in find.

import sys
import fileinput

class Vertex(object):
    def __init__(self, name):
        self.name = name
        self.edges = []

    def find(self, sink, path):
        if(self == sink):
            return path
        for edge in self.edges:
            residual = edge.capacity - edge.flow
            if(residual > 0 or edge.inf):
                if(edge not in path and edge.oppositeEdge not in path):
                    toVertex = edge.toVertex
                    path.append(edge)
                    result = toVertex.find(sink, path)
                    if result != None:
                        return result

class Edge(object):
    def __init__(self, fromVertex, toVertex, capacity):
        self.fromVertex = fromVertex
        self.toVertex = toVertex
        self.capacity = capacity
        self.flow = 0
        self.inf = False
        if(capacity == -1):
            self.inf = True
    def __repr__(self):
        return self.fromVertex.name.strip() + " - " + self.toVertex.name.strip()

def buildGraph(vertices, edges):
    for edge in edges:
        sourceVertex = vertices[int(edge[0])]
        sinkVertex = vertices[int(edge[1])]
        capacity = int(edge[2])
        edge1 = Edge(sourceVertex, sinkVertex, capacity)
        edge2 = Edge(sinkVertex, sourceVertex, capacity)
        sourceVertex.edges.append(edge1)
        sinkVertex.edges.append(edge2)
        edge1.oppositeEdge = edge2
        edge2.oppositeEdge = edge1

def maxFlow(source, sink):
    path = source.find(sink, [])
    while path != None:
        minCap = sys.maxint
        for e in path:
            if(e.capacity < minCap and not e.inf):
                minCap = e.capacity

        for edge in path:
            edge.flow += minCap
            edge.oppositeEdge.flow -= minCap
        path = source.find(sink, [])

    return sum(e.flow for e in source.edges)

vertices, edges = parse()
buildGraph(vertices, edges)
source = vertices[0]
sink = vertices[len(vertices)-1]
maxFlow = maxFlow(source, sink)

Solemn

Answer 1

Your approach using two antiparallel edges works. If your edge is a->b (capacity 10, we send 7 over it), we introduce a new residual edge (from b to a that has residual capacity 17, the residual edge from a to b has the remaining capacity 3).

The original back-edge (from b to a) can be left as it is or the new residual edge and the original backedge can be melt into one edge.

I could imagine that adding the residual capacity to the original back-edge is a bit simpler, but not sure about that.

Diestock

Thanks for answering and sorry for the late reply. How sure are you about that? a->b and b->a both have a capacity of 10. If we send 7 over a->b should't the residual edge capacity(in this case b->a) be 17 instead of 3 as you say? – Solemn

I think you're correct with this. Updated my answer accordingly. I originally ment the remaining capacity of a->b. – Diestock

Yes it works now. If anyone sees the code the error is in the find method. I recommend using dijkstra instead. – Solemn

This is exactly what I was looking for. I studied Max-Flow algorithm of Boykov & Kolmogorov and they use two edges (forward and reverse) in their original implementation as well, so I now understand the missing pieces. – Brook

This idea seems to work. I even found a proof for it in this paper inf.ufpr.br/pos/techreport/RT_DINF003_2004.pdf and I used it to solve this exercise uva.onlinejudge.org/… and got accepted. But when I tried to verify the results in Mathematica using FindMaximumFlow[] I got different results for some examples. Does anybody have an idea why that could be? If these two methods solve the same problem and if they are indeed correct, shouldn't they yield the same results? – Large