9.2. Ford-Fulkerson Algorithm

This section describes the implementation of Ford-Fulkerson Algorithm

Subgraph

Let us define the Subgraph class that consists of a subset of vertices and edges from the original graph:

public class Subgraph {
    private final List<Edge> edges;
    private final Set<Integer> vertices;

    public Subgraph() {
        edges = new ArrayList<>();
        vertices = new HashSet<>();
    }

    public Subgraph(Subgraph graph) {
        edges = new ArrayList<>(graph.getEdges());
        vertices = new HashSet<>(graph.getVertices());
    }
}

Let us define helper methods:

public List<Edge> getEdges() { return edges; }

public Set<Integer> getVertices() { return vertices; }

public void addEdge(Edge edge) {
    edges.add(edge);
    vertices.add(edge.getSource());
    vertices.add(edge.getTarget());
}

public boolean contains(int vertex) {
    return vertices.contains(vertex);
}

Ford-Fulkerson

Ford-Fulkerson algorithm finds the maximum flow from a flow network as follows:

Let us create the FordFulkerson class:

W/O Backward Pushing

public class FordFulkerson implements NetworkFlow {
    public MaxFlow getMaximumFlow(Graph graph, int source, int target) {
        MaxFlow mf = new MaxFlow(graph);
        Subgraph sub;

        while ((sub = getAugmentingPath(graph, mf, new Subgraph(), source, target)) != null) {
            double min = getMin(mf, sub.getEdges());
            mf.updateFlow(sub.getEdges(), min);
        }

        return mf;
    }
}

With Backward Pushing

• L2: indicates one source and one target vertices.

• L6: iterates as long as it can find an augmenting path

  • L7: finds the edge with the minimum capacity in the augmenting path.

  • L8: updates the edges in the path with the flow.

Let us define the getMin() method:

private double getMin(MaxFlow mf, List<Edge> path) {
    double min = mf.getResidual(path.get(0));

    for (int i = 1; i < path.size(); i++)
        min = Math.min(min, mf.getResidual(path.get(i)));

    return min;
}

Finally, let us define the getAugmentingPath() method:

private Subgraph getAugmentingPath(Graph graph, MaxFlow mf, Subgraph sub, int source, int target) {
    if (source == target) return sub;
    Subgraph tmp;

    for (Edge edge : graph.getIncomingEdges(target)) {
        if (sub.contains(edge.getSource())) continue;
        if (mf.getResidual(edge) <= 0) continue;
        tmp = new Subgraph(sub);
        tmp.addEdge(edge);
        tmp = getAugmentingPath(graph, mf, tmp, source, edge.getSource());
        if (tmp != null) return tmp;
    }

    return null;
}

• L2: once the source reaches the target, it found an augmenting path.

• L6: adding the source vertex would cause a cycle.

• L7: cannot push the flow when there is no residual left.

• L10: recursively finds the augmenting path by switching the target.

Backward Pushing

Let us consider the following graph:

As shown, our implementation of Ford-Fulkerson Algorithm does not always guarantee to find the maximum flow correctly. To fix this issue, we need to implement backward pushing:

The backward pushing can be performed after the applying the flow to all edges as in the implementation above (see the code in the "With Backward Pushing" tab).

Finally, the updateBackward() method can be implemented as follows:

protected void updateBackward(Graph graph, Subgraph sub, MaxFlow mf, double min) {
    boolean found;

    for (Edge edge : sub.getEdges()) {
        found = false;

        for (Edge rEdge : graph.getIncomingEdges(edge.getSource())) {
            if (rEdge.getSource() == edge.getTarget()) {
                mf.updateFlow(rEdge, -min);
                found = true;
                break;
            }
        }

        if (!found) {
            Edge rEdge = graph.setDirectedEdge(edge.getTarget(), edge.getSource(), 0);
            mf.updateFlow(rEdge, -min);
        }
    }
}