Maximum Flow Algorithms for Networks in JavaScript

Weighted edges present all sorts of interesting problems to solve and we took a look at a few of them. Dijkstra’s and Floyd-Warshall are great ways of approaching shortest path problems. But what if you want to find the biggest edges on purpose? And what if we aren’t just factoring in the cost of traveling down these edges, but also how fast and with how many in our caravan? Think on this while we solve the previous Daily Problem:

This article is part of the Data Structures and Algorithms Series following the course The Analysis of Algorithms. If you missed the previous article, check that out first as well as a copy of The Algorithm Design Manual.

Answers to the previous Daily Problem

Let G = (V, E) be an undirected weighted graph, and let T be the shortest-path spanning tree rooted at a vertex v. Suppose now that all the edge weights in G are increased by a constant number k. Is T still the shortest-path spanning tree from v?

The answer is no, and it will make sense with a simple example.

Suppose you have a triangle with two edges equal to 3 each and one edge equal to 7 (for all of your mathematicians out there, this is a contrived example so don’t message me that these edge weights couldn’t possibly construct a real triangle). The shortest path is going to be along the 2 3-weighted edges (with a total path weight of 6).

But if you add 10 to all 3 edges, you now have 13, 13, and 17, respectively. Now 17 is the shortest path. What was once the longest edge is now the shortest path, because if you went along the original shortest path, you’d travel 13+13 for a total path weight of 26.

Maximum flow and bipartite matching

We mentioned in a previous article about what a bipartite graph is, but at a high level, it’s just a way to divide a graph into two distinct sections. For example, a set of job vertices and a set of people to do those jobs (also represented as vertices). How can we connect these two sides in a way that the maximum amount of work gets done?

This is called the network flow problem because we want to be able to maximize the capacities from one side to the other so that it flows with maximum efficiency and capacity.

Why is this important to you?

Maximum flow algorithms are often solved with something called augmented paths. Think of it like pouring coffee through a filter or a clogged drain. If one pipe is running slow or only has so much capacity, wouldn’t you divert more water to the bigger pipe or the one that isn’t clogged?

Or imagine you’re a programmer on the city utilities division and you need to figure out how much water you can pump out to the town from a desalinization plant. How do you figure out where the water can go without wasting it or fully utilizing all of the available pipes? As a front-end developer, you might have to map this relationship on a visualization.

Residual graphs

We can use something called a residual graph to figure out this network. A residual graph is like a regular graph but it also includes flow and capacity. So if we look at a graph G and we layer on a residual graph R, we can now see, for every edge, how much flow can be pushed along an edge and, based on the weight, what the capacity that can be applied as well. With all of this extra data, we can find the inefficiencies as well as our limits.

Additionally, we can see what direction we can make use of the weights of an edge. For example, if to travel from a to b along edge (a,b) the weight is 12, we might find out from our residual graph that from a->b our flow is 10 and from b->a our flow is only 2. Whereas another edge may reveal that regardless of direction, the price is 5. These are very key points when trying to figure out how to best utilize our network.

In fact what this tells us is that the flow on our 2nd edge is maximized, and that our primary edge of (a,b) has some extra capacity to utilize. How much capacity? The minimum cut of that edge. Let’s look at that again. The weight of (a,b) is 12, with one cut at 10 and one cut at 2, so the amount we can optimize is by the minimum cut (in this case, 2). In fact we can generalize this augmented paths problem into the algorithm represented below:

class Vertex {
  constructor(
    capacity = 0,
    flow = 0,
    neighbor = null,
    nextVertex = null,
    residualCapacity = 0
  ) {
    this.capacity = capacity;
    this.flow = flow;
    this.neighbor = neighbor;
    this.nextVertex = nextVertex;
    this.residualCapacity = residualCapacity;
  }
}

class Graph {
  resetSearch() {
    for (let i = 0; i < this.vertices.length; i++) {
      PROCESSED[i] = false;
      VISITED[i] = false;
      PARENTS[i] = null;
    }
  }

  findEdge(start, end) {
    let path = this.connections[start];
    while (path) {
      if (path.adjacencyInfo === end) return path;
      path = path.nextVertex;
    }
    return path;
  }

  augmentPath(start, end, parents, volume) {
    if (start === end) return;

    let edge = this.findEdge(parents[end], end);
    edge.flow += volume;
    edge.residualCapacity -= volume;

    edge = this.findEdge(end, parents[end]);
    edge.residualCapacity += volume;

    this.augmentPath(start, parents[end], parents, volume);
  }

  pathVolume(source, sink, parents) {
    if (parents[parents.length-1] === -1) return 0;

    let edge = this.findEdge(parents[sink], sink);

    if (source === parents[sink]) {
      return edge.residualCapacity;
    } else {
      return Math.min(
        this.pathVolume(source, parents[sink], parents),
        edge.residualCapacity
      );
    }
  }

  edmondsKarp(source, sink) {
    this.addResidualEdges();
    this.resetSearch();
    this.bfs(source);

    let volume = this.pathVolume(source, sink, this.PARENTS);

    while (volume > 0) {
      this.augmentPath(source, sink, this.PARENTS, volume);
      this.resetSearch();
      this.bfs(source);
      volume = this.pathVolume(source, sink, this.PARENTS);
    }
  }
}

In this case, the source is an edge of a bipartite graph (let’s say one section is L and the other section is R) and the sink is the edge in the other section of the graph. These edges are special because they are connected to all other edges on their side by a weight of 1. Their job is to provide easy access to all edges in the graph and map out all of the main paths and find the efficiencies. We do this via breadth-first search to look for any path from the source to the sink that increases the total flow. The algorithm, known as Edmonds-Karp, is done when we have no more extra volume left to optimize.

Note: for the very astute, you might recognize this as the Ford-Fulkerson method. Though not fully recognized as an algorithm, Edmonds-Karp is an implementation of Ford-Fulkerson for maximum flow problems on networks.

Now that we’ve seen a bunch of algorithms for moving around a graph, here’s a few things to keep in mind:

Map the problem. Solve with an algorithm. Think of these algorithms as your ace-in-the-hole. They’re your ammunition for firing at problems. But you need to know what to fire at.
Create the framework. All problems can be fit into some sort of framework. Once you know the problems, the solutions are easy since they’ve already been given to you.
Practice. Problems are easier to recognize and slot into that framework if you see a lot of them. Make sure you hit the books and give some coding problems a try!

And with that last tip, let’s get on to the Daily Problem and apply some of these recent algorithmic concepts!

Onto the next Daily Problem

Let G = (V,E) be a directed weighted graph such that all the weights are positive. Let v and w be two vertices in G and k ≤ |V| be an integer. Design an algorithm to find the shortest path from v to w that contains exactly k edges. Note that the path need not be simple.

Maximum Flow Algorithms for Networks in JavaScript

Answers to the previous Daily Problem

Maximum flow and bipartite matching

Why is this important to you?

Residual graphs

Onto the next Daily Problem

More problems to practice on

Get the FREE UI crash course

Answers to the previous Daily Problem

Maximum flow and bipartite matching

Why is this important to you?

Residual graphs

Onto the next Daily Problem

More problems to practice on

Liked this post? You'll probably also like:

Get the FREE UI crash course