Flow network

Imagine a situation: you have pipes that are connected to each other. They are different in diameter and can let different amounts of water through. There is one water source and one destination to where the water should be delivered. Which structure would you use to represent such a system?

There may be many options, but in this topic, you will learn about flow networks. They are used widely in the tasks where you need to analyze the number or amount of products, materials, etc. that can be transferred via some limited transportation channels. This analysis is often crucial, as it helps to optimize logistic processes and estimate the number of goods that can be transported.

Flow networks

Now, what may be called a flow network? It is a graph that has the following characteristics:

• It is directed. Just as in the example with water flowing from one pipe to another, the edges in the graph have a starting and a finishing vertices.

• Each edge of the graph has both flow and capacity . In terms of our pipeline system, it means the current amount of water that is transported through a pipe and the maximum one, respectively.

• There is one source and one sink in the graph. Going back to the pipes: a source is a place from which the water starts flowing, and sink is its destination.

Let's visualize a flow network. For example, it may look like this:

Here the numbers near the edges are given in the following format: flow/capacity.

Note that sometimes you can come across flow networks that have several sources or sinks. For instance, you may need several sources in critical systems, where problems with the source might threaten human lives (e.g. water and electricity systems in hospitals).

In such cases, for some problems it is useful to transform the system into a network with one supersource and one supersink. Node X in the graph below is a supersource – a node that is connected to all sources of the initial network, and node Y is a supersink – a node that, you've guessed it, is connected to all sinks of the network. Remember that an indegree of the supersource and an outdegree of the supersink equal zero.

Now it's time to take a closer look at the capacity and flow, since understanding these properties is crucial for learning flow networks.

Capacity and flow

Let's start with capacity. As mentioned before, it shows the maximum resource that can be pushed through one edge. The main thing you need to remember about capacity is that it is non-negative. If you remember the example, it is quite logical, as it is impossible to create a pipe that can let through only a negative amount of water. Therefore, there can never be an edge like this (the number is the capacity):

Sometimes, you can come across edges with a zero capacity. It means that no flow can be passed through it.

Now, moving on to the flow, you should keep in mind its characteristics:

• Capacity constraint. The flow of an edge cannot exceed its capacity. It can be only less (edges AB, CD, and ED below) or equal (edges AC and BE).

• Skew symmetry. When you push a flow through an edge, you can subtract it from the flow of the oppositely directed edge, even if it is non-existent. In other words, the flow of the edge from vertex X to Y equals the negative flow of the edge from vertex Y to X. In some sense, you may think of it as canceling the flow. For example, you can send trucks with goods from city A to city B. However, you can discover later on that there may not be enough space in the warehouse of the city B for storing the goods and sending them to other cities. Therefore, you may want to send them back to A and redistribute them from A to other destinations. You will get a better understanding of this property when studying flow network algorithms in the upcoming topics.

  

• Flow conservation. This rule basically says that the sum of the incoming flows equals the sum of the outgoing ones. Mind that if you count also the negative flows of the oppositely directed edges (you remember about the skew symmetry, right?), the total incoming and outgoing flows both equal 0. However, this does not work for the source and the sink, there is another rule for these two vertices: the sum of outgoing flows of the source equals the sum of the incoming flows of the sink.

  For instance, let's count the flows for the vertices A, B, and C of the graph from above:

  

It could've been the end of this section, but there is one more thing that you certainly need to remember in order not to get confused. Sometimes, the term flow is used to describe not an edge, but the total flow of the graph. In this case, it equals the sum of the flows coming out of the source and into the sink.

For example, look at the following graph. It has the sink – node G. There are two incoming edges for this vertex – edges EG and FG that both have the flow of 2. Thus, the flow of the graph is the sum of these values and equals 4.

Phew, now you definitely know everything about the capacity and flow! It's the perfect moment to go on and learn about possible ways of representing flow networks in your code.

Representation

Being a special type of graph, a flow network can indeed be represented as a graph, right? As you may remember, there are three basic options when choosing a suitable representation. Let's discuss them one by one and compare them by representing the network from above in different ways.

The first way for representation is having an adjacency matrix for the capacities and another matrix for storing the flows. It is easier to implement and more convenient in many cases, since you can access the values just by indexing the matrices. However, it is inefficient in terms of memory, especially for sparse graphs, as the space complexity is $O(|V|^2)$.

For existing edges, you write the values of the flow and capacity in the tables. If an edge between two vertices doesn't exist, you simply put zero in the corresponding cell.

An adjacency matrix for the flows:

An adjacency matrix for the capacities:

Another one is quite similar and has the same space complexity, but the difference is that you use only one adjacency matrix to store the pairs of the flow and capacity for each edge. You can easily create it by combining the two matrices from above:

The final option is to use an adjacency list with the capacity and flow stored in every node. It is more efficient in terms of memory, having a space complexity of $O(|V| + |E|)$, as you don't need to store values for all possible edges, only for the existent ones. Another benefit is that it is easier to add vertices and edges to such an adjacency list.

However, accessing data is more difficult in this case, as you have to iterate through the adjacent vertices in order to find the needed values. Additionally, flow and capacity for non-existent edges aren't stored in the list, so they have to be computed during the work of the program, which may be inconvenient.

All in all, each method has its pros and cons, so you should carefully choose a way of representing the flow network, depending on the problem you want to solve.

Of course, you can find more advanced structures to store flow networks, but they are out of the scope of this topic. Nevertheless, you are totally welcome to explore them by yourself and improve your knowledge of Algorithms even further!

Conclusion

To sum up, let's go through the main points of this topic:

• A flow network is a directed graph, each edge of which has a flow and a capacity.

• Generally, flow networks have one source and one sink. In some cases, you may add a supersource and a supersink.

• All vertices of a flow network should belong to some path from the source to the sink.

• Capacity is non-negative and equals zero for non-existent edges.

• Flow has the following characteristics: capacity constraint, skew symmetry, and flow conservation.

• Two separate adjacency matrices for the flow and the capacity, one matrix for the pairs of values, and an adjacency list are the basic ways of representing flow networks.