Having trouble understanding and implementing the Ford Fulkerson algorithm

Question

I'm trying to implement the Ford Fulkerson algorithm in Java. So far I have a graph with Nodes and Edges. The nodes contains an ID string and an adjacencyList of edges. The edges contain the capacity and the node it leads to.

I'm trying to understand the psudo code on the Wikipedia page and how to implement it (I'm using Java). This is what I understand so far:

1. First I set the flow of all edges in the graph to zero.(What is a good way to represent flow? Directly in the edges of my graph as a variable?)

2. The second step is to create the residual graph which is a network where the edges have the residual capacity: capacity - flow (of the corresponding edges in the "normal graph"). Then you find a path from the source to the sink using this residual graph and find the minimal capacity along this path. (This is where stuff gets really tricky, should I create an entirely new graph for the residual graph or should I represent it somehow in the original graph? What is the best way?)

Step 2 is repeated until no path can be found but every time it is found you do step 3 and 4:

1. For each edge along the path you add the minimal value found in step 2.

2. For each edge in the opposite direction of the path you subtract the minimal value found in step 2.

Step 3 and 4 puzzles me since I feel like it is the same thing to add in one direction as it is to substracting in the opposite. These additions and substractions are made in the graph right, not the residual graph?

Would really appreciate some help, I have been trying to wrap my head around this for a couple of hours now but I just can't seem to understand it.

Answer 1

You should probably implement this first with a dense graph. That way, you can assume there's an edge in each direction between every pair of distinct vertices. You can represent functions on the edges as |V| x |V| matrices. In particular, declarations for capacity and flow are quite simple:

int[][] cap = new int[numverts][numverts];
int[][] flow = new int[numverts][numverts];

One useful trick is to represent a flow of k units along edge vw as a flow of a from v to w and a flow of -a from w to v. This way, you don't have to worry about whether each edge of your augmenting path is pushing more flow forward or less flow backward. If you do this, you can compute the residual capacity along vw by simply cap[v][w] - flow[v][w].

With this representation, finding an augmenting path becomes a breadth-first search in a dense graph where there is an edge from v to w exactly when cap[v][w] > flow[v][w]. This is fairly straightforwardly implemented.

Since you're using java, you should be mindful of its per-object overhead. The Edge structure you described contains not just two ints (or pointers) and two doubles, but also stuff like GC information, a klass pointer, and a monitor. This is a few dozen extra bytes, easily doubling or tripling the size of your object.

A better representation for static sparse graphs, when you get to making your code work with sparse graphs, is as follows:

int[] from = new int[numverts+1];
int[] to = new int[numedges];

Sort the edges by "from" vertex. The ith entry of the from array is the index of the first edge whose "from" vertex is the ith vertex or later. There's one extra entry at the end and you should set it to numedges; it comes in handy when you want to loop over all edges leaving a given vertex.

Since you're doing flow, you'll want to store backward edges as well, so have an

int[] rev = new int[numedges];

to store the edge index of the reverse of each edge. Now you can represent arbitrary functions, say cap and flow, on the edges like this:

int[] cap = new int[numedges];
int[] flow = new int[numedges];

So whether to store these attributes in the Edge structure is moot because the Edge structure has gone away.

Answer 2

Here's an implementation of the Ford-Fulkerson method using a Depth First Search (DFS) using an adjacency list to store the capacities. The tricky part about using an adjacency list as opposed to an adjacency matrix with Ford-Fulkerson is that you need to keep track of the residual edges yourself. To simplify things I created an 'addEdge' method which handles residual edges. The nice thing though about using an adjacency list as opposed to an adjacency matrix is that the time complexity reduces from O(fV²) to O(fE) which can be significant.

At a high level, most flow algorithms work much the same. All they do is start from a source node and using some technique (in the example below a depth first search) they find an augmenting path to the sink (the end node). Once the augmenting path is found you reduce the capacity of each edge along the path by the bottleneck value and also add this value to the residual graph. You repeat this procedure until no more augmenting paths can be found an bingo that's it! These are all the steps you need to be able to find the max flow and the min cut.

The code was taken from my algorithm repo. Feel free to check it out, there's also an adjacency matrix version of this algorithm in there.

/**
 * An implementation of the Ford-Fulkerson (FF) method with a DFS
 * as a method of finding augmenting paths. FF allows you to find
 * the max flow through a directed graph and the min cut as a byproduct.
 *
 * Time Complexity: O(fE), where f is the max flow and E is the number of edges
 * 
 * @author William Fiset
 **/

import java.util.ArrayList;
import java.util.List;

public class FordFulkersonDfsSolverAdjacencyList {

  public static class Edge {
    public Edge residual;
    public int to, capacity;
    public final int originalCapacity;
    public Edge(int to, int capacity) {
      this.to = to; 
      this.capacity = capacity;
      this.originalCapacity = capacity;
    }
  }

  // Inputs
  private int n, source, sink;

  // Internal
  private int visitedToken = 1;
  private int[] visited;
  private boolean solved;

  // Outputs
  private int maxFlow;
  private boolean[] minCut;
  private List<List<Edge>> graph;

  /**
   * Creates an instance of a flow network solver. Use the {@link #addEdge(int, int, int)}
   * method to add edges to the graph.
   *
   * @param n      - The number of nodes in the graph including source and sink nodes.
   * @param source - The index of the source node, 0 <= source < n
   * @param sink   - The index of the source node, 0 <= sink < n
   */
  public FordFulkersonDfsSolverAdjacencyList(int n, int source, int sink) {
    this.n = n;
    initializeGraph();
    this.source = source;
    this.sink = sink;
  }

  /**
   * Adds a directed edge (and residual edge) to the flow graph.
   *
   * @param from     - The index of the node the directed edge starts at.
   * @param to       - The index of the node the directed edge end at.
   * @param capacity - The capacity of the edge.
   */
  public void addEdge(int from, int to, int capacity) {
    Edge e1 = new Edge(to, capacity);
    Edge e2 = new Edge(from, 0);
    e1.residual = e2;
    e2.residual = e1;
    graph.get(from).add(e1);
    graph.get(to).add(e2);
  }

  /**
   * Returns the graph after the solver has been executed. This allow you to
   * inspect each edge's remaining {@link Edge#capacity} compared to the
   * {@link Edge.originalCapacity} value. This is useful if you want to figure 
   * out which edges were used during the max flow.
   */
  public List<List<Edge>> getGraph() {
    solve();
    return graph;
  }

  // Returns the maximum flow from the source to the sink.
  public int getMaxFlow() {
    solve();
    return maxFlow;
  }

  // Returns the min-cut of this flow network in which the nodes on the "left side"
  // of the cut with the source are marked as true and those on the "right side" 
  // of the cut with the sink are marked as false.
  public boolean[] getMinCut() {
    solve();
    return minCut;
  }

  // Performs the Ford-Fulkerson method applying a depth first search as
  // a means of finding an augmenting path. The input consists of a directed graph
  // with specified capacities on the edges.
  public void solve() {
    if (solved) return;

    maxFlow = 0;
    visited = new int[n];
    minCut = new boolean[n];

    // Find max flow.
    int flow;
    do {
      // Try to find an augmenting path from source to sink
      flow = dfs(source, Integer.MAX_VALUE);
      visitedToken++;
      maxFlow += flow;
    } while(flow != 0);

    // Find min cut.
    for(int i = 0; i < n; i++)
      if (visited[i] == visitedToken-1)
        minCut[i] = true;

    solved = true;
  }

  private int dfs(int node, int flow) {
    // At sink node, return augmented path flow.
    if (node == sink) return flow;

    List<Edge> edges = graph.get(node);
    visited[node] = visitedToken;

    for (Edge edge : edges) {
      if (visited[edge.to] != visitedToken && edge.capacity > 0) {

        // Update flow to be bottleneck 
        if (edge.capacity < flow) flow = edge.capacity;
        int dfsFlow = dfs(edge.to, flow);

        // Update edge capacities
        if (dfsFlow > 0) {
          Edge res = edge.residual;
          edge.capacity -= dfsFlow;
          res.capacity  += dfsFlow;
          return dfsFlow;
        }

      }
    }
    return 0;
  }

  // Construct an empty graph with n nodes including the source and sink nodes.
  private void initializeGraph() {
    graph = new ArrayList<>(n);
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
  }

}