In this post I’ll describe a Java implementation of a fast maximum flow algorithm, known as the *Ahuja-Orlin* max flow algorithm. This algorithm implementation is part of a small and easy to use Java class library which can be used to model a flow graph, along with its nodes and edges, and to find the maximum flow that can be sent from a source node to a sink node. This library also provides a convenient way to calculate the maximum flow on a subgraph.

##### The Ahuja-Orlin max flow algorithm

The algorithm I chose to implement is *Improved shortest augmenting path* from *Ahuja* and *Orlin*. I chose it after finding that it came out as the best performing algorithm in an experimental analysis of max-flow graph algorithms from *TopCoder*.

This algorithms uses the concepts of *shortest augmenting path* and *distance labels*. The algorithm iteratively searches the shortest augmenting path in the residual network of the graph. It terminates when some conditions on the distance labels are met: these conditions indicate that the flow distribution is optimal and so no other augmenting paths exist.

In the following listing, the algorithm pseudocode is reported (source: TopCoder). The source node is called *s* and the sink node is called *t*.

Given an input graph, the algorithm initially builds the associated residual network. To obtain a residual network, *back-edges *are added to the graph: for each edge *(i, j)*, a *(j, i)* edge with zero capacity and flow is created.

Then, an initial labelling of the nodes is performed. Each node is associated with a distance label *d[i]* representing the length, in term of nodes, of the shortest path between *i* and the sink node in the residual network, having *d[t] = 0.* This labelling is done by means of a reverse breadth-first search of the graph, starting from the sink node.

If, in the iterations of the algorithm, the distance label of node *s* becomes greater or equal to the number of nodes, no more augmenting paths can exist in the residual network; this is the main termination criterion for the algorithm.

An edge *(i, j)* is called admissible if *d[i] = d[j] + 1*. The shortest augmenting path between *s* and *t* is defined as a s -> t path consisting only of admissible edges, each one with a residual capacity *r _{ij}* > 0.

The algorithm is composed of 4 main procedures: the main cycle, the *advance *procedure, the *retreat *procedure, and the *augment *procedure. In the main cycle, the algorithm iteratively tries to build an augmenting path from *s* to *t*, by using admissible edges.

If an admissible edge can be taken from the current node, an *advance *is performed, by means of which the path and the current node are updated. If the *t* node is reached, the *augment *takes place, which calculates the flow increment of the path, updates the graph, and resets *s* as the current node.

If, conversely, the are no admissible outbound edges from the current node, the *retreat* operation is executed, which increments the current node’s distance label and backtracks the augmenting path to the previous node.

An additional termination criterion is also used. During the generic iterations, the algorithm keeps track of the distance labels distribution over the nodes. When a node’s distance label is incremented, the algorithm tests whether the number of nodes having the previous label value has become 0: in this case, there is the guarantee that no more augmenting paths exist, and so the algorithm terminates.

##### Ahuja-Orlin Java implementation

To implement the solution I had to design the graph first, which is the data structure the algorithm runs on. I implemented a directed graph suitable for flow problems, with limited capacity edges. The graph internal representation consist of adiacency and incidency lists; this allows an easier navigation of the graph: for a generic node, both the adjacent and incident edges can be obtained. This solution also allows to optimize some operations executed by the max flow algorithm. The following diagrams show the structure and the relationships of the 5 modules of the solution: the *Graph* interface and the *FlowGraph*, *Node*, *Edge*, and *MaxFlowCalculator *classes.

The Edge and Node classes model the basic components of the graph. The edges use double values to model the edge capacity and flow. The nodes are represented with a integer id and a label (string).

The graph interface (of which *FlowGraph* is a concrete implementation) exposes the common methods for the graph manipulation and navigation, and additionally :

- a
*clone()*method that returns a “*deep copy*” of the graph; - The
*setSource(Node)*and*setSink(Node)*methods, used to specify the source and the sink nodes; - a
*getSubGraph(Set<Integer> s)*method that returns the induced subgraph from a given node subset (ids) and from the source and sink nodes.

The max flow algorithm has been implemented in the *MaxFlowCalculator *class*. *This class, as represented by the following diagram, exposes one public and static method *double getMaxFlow(Graph)* which calculates and returns the maximum flow value for the input graph.

The various steps of the algorithm have been implemented in different private methods for clarity purposes. The distance labels are managed by a *DistanceLabels *class, which provides methods for obtaining and setting the node labels, and keeps track of the label distribution (this is useful to implement the algorithm’s secondary termination criterion). The *getMaxFlow* method implementation is reported below.

public static double getMaxFlow(Graph g) { if(g.numNodes() == 0) { return 0; } DistanceLabels labels = calcDistanceLabels(g); double f = 0; // max flow int n = g.numNodes(); // add back edges to create residual network List<Edge> backEdges = addBackEdges(g); // current augmenting path LinkedList<Edge> path = new LinkedList<Edge>(); // distance of source from the sink int sourceDist; Node i = g.getSource(); // current node /* Main termination criterion: distance label of source node is greater or equal to the number of nodes. In that case, no more augmenting paths from the source to the sink can exist. */ while(i != null && (sourceDist = labels.getLabel(g.getSource())) < n) { Edge e = getAdmissibleEdge(g, i, labels); if(e != null) { i = advance(e, path); if(i.equals(g.getSink())) { double delta = augment(g, path); f += delta; i = g.getSource(); path.clear(); } } else i = retreat(g, labels, i, path); } removeBackEdges(g, backEdges); return f; }

##### Usage example

Let’s show how this Java class library can be used to calculate the maximum flow on a simple test graph, reported in the following figure:

This is a flow graph containing 7 nodes and 12 edges; the *a* node is the source and the *b* node is the sink. First of all, let’s see how to build the graph:

private static Graph buildTestGraph() { Graph graph = new FlowGraph(); Node na = new Node(0, "A"); Node n1 = new Node(1, "N1"); Node n2 = new Node(2, "N2"); Node n3 = new Node(3, "N3"); Node n4 = new Node(4, "N4"); Node n5 = new Node(5, "N5"); Node nb = new Node(6, "B"); graph.addNode(na); graph.setSource(na); graph.addNode(n1); graph.addNode(n2); graph.addNode(n3); graph.addNode(n4); graph.addNode(n5); graph.addNode(nb); graph.setSink(nb); graph.addEdge(new Edge(na, n1, 3)); graph.addEdge(new Edge(na, n3, 5)); graph.addEdge(new Edge(na, n2, 3)); graph.addEdge(new Edge(n1, n3, 4)); graph.addEdge(new Edge(n1, n4, 3)); graph.addEdge(new Edge(n3, n4, 2)); graph.addEdge(new Edge(n3, nb, 1)); graph.addEdge(new Edge(n3, n5, 4)); graph.addEdge(new Edge(n2, n3, 2)); graph.addEdge(new Edge(n2, n5, 2)); graph.addEdge(new Edge(n4, nb, 4)); graph.addEdge(new Edge(n5, nb, 4)); return graph; }

Now let’s calculate the max flow that can be sent from a to b on the whole graph:

// build the test graph Graph g = buildTestGraph(); // calculate max flow from source to sink on g double f = MaxFlowCalculator.getMaxFlow(g); System.out.println("max flow on g = " + f); // print the flow distribution on g System.out.println("flow distribution on g = " + g.getEdges());

The output is:

max flow on g = 9.0 flow distribution on g = [(0, 1) [3.0 / 3.0], (0, 3) [5.0 / 5.0], (0, 2) [1.0 / 3.0], (1, 3) [0.0 / 4.0], (1, 4) [3.0 / 3.0], (2, 3) [0.0 / 2.0], (2, 5) [1.0 / 2.0], (3, 4) [1.0 / 2.0], (3, 6) [1.0 / 1.0], (3, 5) [3.0 / 4.0], (4, 6) [4.0 / 4.0], (5, 6) [4.0 / 4.0]]

So the maximum flow between a and b on the entire network is 9. The output also shows the flow distribution (obtained with the *getEdges()* method of the graph). Now let’s see how the maximum flow changes if only a part of the graph is used to route the flow from the source to the sink.

The subgraph induced from the 1, 3 and 4 nodes is the following:

This subgraph is obtained from the original test graph, by removing the 2 and 5 nodes and the associated edges. The code for obtaining the subgraph and calculating the max flow follows:

// calculate the max flow from source to sink using // the subgraph induced from nodes 1, 3, 4 Set<Integer> s134 = new HashSet<Integer>(); s134.add(1); s134.add(3); s134.add(4); Graph g134 = buildTestGraph().getSubGraph(s134); double f134 = MaxFlowCalculator.getMaxFlow(g134); System.out.println("max flow on g[1, 3, 4] = " + f134); System.out.println("flow distribution on g[1, 3, 4] = " + g134.getEdges());

To get the subgraph, you must call *getSubGraph *on the graph object, and pass a set of node ids (1, 3 and 4, in this case). The result we get is:

max flow on g[1, 3, 4] = 5.0 flow distribution on g[1, 3, 4] = [(0, 1) [3.0 / 3.0], (0, 3) [2.0 / 5.0], (1, 3) [0.0 / 4.0], (1, 4) [3.0 / 3.0], (3, 4) [1.0 / 2.0], (3, 6) [1.0 / 1.0], (4, 6) [4.0 / 4.0]]

As expected, using a smaller network, the max flow that can be sent is lower. Finally, let’s consider an edge case (the irony), in which we can’t have any flow between the two nodes. The subgraph induced from node 2 is:

In this case, no path from the source node to the sink node exists, so we expect the flow to be 0. The code is very similar to the previous examples:

Set<Integer> s2 = new HashSet<Integer>(); s2.add(2); Graph g2 = buildTestGraph().getSubGraph(s2); double f2 = MaxFlowCalculator.getMaxFlow(g2); System.out.println("max flow on g[2] = " + f2); System.out.println("flow distribution on g[2] = " + g2.getEdges());

The output is:

max flow on g[2] = 0.0 flow distribution on g[2] = [(0, 2) [0.0 / 3.0]]