9.1. Flow Network

This section describes how to implement a flow network.

A flow network is a directed graph that has the following properties:

Max Flow

Let us define the MaxFlow class that keeps track of the amount of flows in every edge used to find the maximum flow:

public class MaxFlow {
    private Map<Edge, Double> flow_map;
    private double maxflow;

    public MaxFlow(Graph graph) {
        init(graph);
    }

    public void init(Graph graph) {
        flow_map = new HashMap<>();
        maxflow = 0;

        for (Edge edge : graph.getAllEdges())
            flow_map.put(edge, 0d);
    }
}

• L2: consists of (edge, flow) as the key-value pair.

• L3: stores the total amount of flows to the target vertices.

• L13-14: initializes all flows to 0.

Let us define getter methods:

public double getMaxFlow() {
    return maxflow;
}

public double getResidual(Edge edge) {
    return edge.getWeight() - flow_map.get(edge);
}

• L5: returns the remaining residual that can be used to push more flows.

  • L6: the edge weight represents the total capacity.

Finally, let us define setter methods:

public void updateFlow(List<Edge> path, double flow) {
    path.forEach(e -> updateFlow(e, flow));
    maxflow += flow;
}

public void updateFlow(Edge edge, double flow) {
    Double prev = flow_map.getOrDefault(edge, 0d);
    flow_map.put(edge, prev + flow);
}

• L1: takes the path from a source and a target.

  • L2: updates the flow of every edge in the path with the specific flow.

  • L3: updates the overall flow.

• L6: adds the specific flow to the specific edge.