Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Network flow problem: Maximize total amount of flow from s to t

Sharing is caring!

Problem statement
Find the maximum flow in a flow network (directed graph) from a source node s to a target node t subject to two constraints:
– The flow on edge e doesn’t exceed its capacity c(e)
– For every node v \ne s, t, the incoming flow is equal to outgoing flow.

Consider the graph below. The image on the left depicts the graph with its edge capacities, while the image on the right illustrates the same graph with a maximum flow of 19:

 

 

 

 

 

 

Notice also on the right image, that for every node v \ne s, t, the incoming flow is equal to outgoing flow while the flow does not exceed the edge’s capacity.

How can we find the maximum flow?
We will do this by finding augmenting paths from node s to t. An augmenting path is a path whose edges are:
1. Non-full and forward or
2. Non-empty and backward
In other words, it is a path where the residual capacity is \textgreater 0, with the residual capacity of an edge e, being the total capacity c(e) minus the flow that goes through e. For the above graph we can annotate the edges with their current flow and capacity. At the beginning the flow through each edge is 0, so their residual capacity is equal to their capacity:

The general algorithm (also known as Ford-Fulkerson algorithm) is as follows:
1. Find an augmenting path (using Breadth-first search or Depth-first search) from s to t
2. Compute the bottleneck capacity (i.e. an edge in the path with the smallest residual capacity)
3. Augment each edge and the total flow
4. Repeat steps 1-3 until no augmenting path can be found

The first path we can find is s \rightarrow A \rightarrow B \rightarrow t with a bottleneck of 4:

Next, we find the path s \rightarrow C \rightarrow D \rightarrow t with a bottleneck of 9:

The next path is s \rightarrow A \rightarrow D \rightarrow B \rightarrow t with a bottleneck of 6:

Finally we cannot find any more augmenting paths so we stop with a maximum flow of 19.

What if the paths we choose are different. Is the maximum flow still going to be the same?
Let us consider choosing the following paths. First we choose the path s \rightarrow A \rightarrow B \rightarrow t with a bottleneck of 4::

Next, we choose the path s \rightarrow A \rightarrow C \rightarrow D \rightarrow t with a bottleneck of 2:

We then go on and choose the path s \rightarrow C \leftarrow A \rightarrow D \rightarrow t. This path has a backward edge C \leftarrow A. We augment flow through the whole network by removing flow in that path. So when we add 2 units of flow to the edge s \rightarrow C, we can remove 2 units of flow the backward edge A \leftarrow C to preserve the local equilibrium. Essentially that 2 units of flow gets transferred through edge C \rightarrow D and then for the forward edges we add the flow:

Next, we choose the path s \rightarrow A \rightarrow D \rightarrow t with a bottleneck of 4:

We then choose the path s \rightarrow C \rightarrow D \rightarrow B \rightarrow t with a bottleneck of 6:

Next, we find the path s \rightarrow C \rightarrow D \rightarrow t with a bottleneck of 1:

Finally we cannot find any more augmenting paths so we stop with a maximum flow of 19.

How do we know that this algorithm gives us the maximum flow?
Suppose this algorithm does not give us the maximum flow. Take a maximum flow m' and subtract our found flow m. Whats left is a valid flow \textgreater 0. That is, there exists a path with a residual capacity \textgreater 0 (augmenting path). But, by algorithm, this path must have been found (see step 4 of algorithm). Contradiction.

Sample implementation

public class FordFulkerson {
    private static class DirectedGraph {
        private Map> nodeToNeighbors;
        private Map> capacity;
        private Map> residualCapacity;

        public DirectedGraph() {
            nodeToNeighbors = new HashMap>();
            capacity = new HashMap>();
            residualCapacity = new HashMap>();
        }

        public void addNode(T node) {
            if (!nodeToNeighbors.containsKey(node)) {
                nodeToNeighbors.put(node, new HashSet());
            }
        }

        public void addEdge(T start, T dest, int cap) {
            nodeToNeighbors.get(start).add(dest);
            if (!capacity.containsKey(start)) {
                capacity.put(start, new HashMap());
            }

            if (!residualCapacity.containsKey(start)) {
                residualCapacity.put(start, new HashMap());
            }

            if (!residualCapacity.containsKey(dest)) {
                residualCapacity.put(dest, new HashMap());
            }

            capacity.get(start).put(dest, cap);
            residualCapacity.get(start).put(dest, cap);
            residualCapacity.get(dest).put(start, 0);
        }

        public Set getNodes() {
            return nodeToNeighbors.keySet();
        }

        public int getResidualCapacity(T start, T dest) {
            if (!residualCapacity.get(start).containsKey(dest)) {
                return 0;
            } else {
                return residualCapacity.get(start).get(dest);
            }
        }

        public void setResidualCapacity(T start, T dest, int f) {
            residualCapacity.get(start).put(dest, f);
        }
    }


    // Get BFS backtrack from source -> target
    private static Map bfs(DirectedGraph graph, String source, String target) {
        Map backtrack = new HashMap<>();
        Set visited = new HashSet<>();
        Queue queue = new LinkedList();
        queue.add(source);

        OUTER:
        while (!queue.isEmpty()) {
            String node = queue.poll();
            visited.add(node);

            for (String n : graph.getNodes()) {
                if (!n.equals(node) && !visited.contains(n)) {
                    if (graph.getResidualCapacity(node, n) > 0) {
                        // We have a positive residual capacity to reach n from node
                        queue.add(n);
                        backtrack.put(n, node);
                        if (n.equals(target)) {
                            break OUTER;
                        }
                    }
                }
            }

        }

        return backtrack;
    }


    private static int maxFlow(DirectedGraph graph, String source, String target) {
        int ans = 0;
        Map backtrack = bfs(graph, source, target);
        List path = new LinkedList<>();
        do {
            // Print augmenting path and also find the bottleneck of the path
            path.clear();
            path.add(target);
            String tail = target;
            int min = Integer.MAX_VALUE;
            while (backtrack.containsKey(tail)) {
                String prev = backtrack.get(tail);
                min = Math.min(min, graph.getResidualCapacity(prev, tail));
                path.add(0, prev);
                tail = prev;
            }

            if (path.size() <= 1) {
                break;
            }

            System.out.println("Found augmenting path '" + path + "' with bottleneck " + min);

            // Update residualCapacity
            tail = target;
            while (backtrack.containsKey(tail)) {
                String prev = backtrack.get(tail);
                // Decrement residual capacity for edge prev->tail
                graph.setResidualCapacity(prev, tail, graph.getResidualCapacity(prev, tail) - min);

                // Increase residual capacity for backwards edge tail->prev (i.e. open up an edge in the opposite direction)
                graph.setResidualCapacity(tail, prev, graph.getResidualCapacity(tail, prev) + min);

                tail = prev;
            }

            // Update max flow by min
            ans += min;

            // Repeat process: find a new path
            backtrack = bfs(graph, source, target);
        } while (path.size() > 1);

        return ans;
    }

    public static void main(String[] args) {
        DirectedGraph graph = new DirectedGraph();
        graph.addNode("s");
        graph.addNode("A");
        graph.addNode("B");
        graph.addNode("C");
        graph.addNode("D");
        graph.addNode("t");

        graph.addEdge("s", "A", 10);
        graph.addEdge("s", "C", 10);
        graph.addEdge("A", "B", 4);
        graph.addEdge("A", "C", 2);
        graph.addEdge("A", "D", 8);
        graph.addEdge("B", "t", 10);
        graph.addEdge("C", "D", 9);
        graph.addEdge("D", "B", 6);
        graph.addEdge("D", "t", 10);
        System.out.println("max flow = " + maxFlow(graph, "s", "t") + "\n"); // 19


        graph = new DirectedGraph();
        graph.addNode("A");
        graph.addNode("B");
        graph.addNode("C");
        graph.addNode("D");
        graph.addNode("E");
        graph.addNode("F");
        graph.addNode("G");

        graph.addEdge("A", "B", 3);
        graph.addEdge("A", "D", 3);
        graph.addEdge("B", "C", 4);
        graph.addEdge("C", "A", 3);
        graph.addEdge("C", "D", 1);
        graph.addEdge("C", "E", 2);
        graph.addEdge("D", "E", 2);
        graph.addEdge("D", "F", 6);
        graph.addEdge("E", "B", 1);
        graph.addEdge("E", "G", 1);
        graph.addEdge("F", "G", 9);
        System.out.println("max flow = " + maxFlow(graph, "A", "G") + "\n"); // 5

    }
}

References
https://www.youtube.com/watch?v=GiN3jRdgxU4