9.2. Ford-Fulkerson Algorithm

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

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);
}

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;
}

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;
}

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);
        }
    }
}