Graph Throughput Algorithm

Question

I have the task to calculate the maximum throughput in a graph.

The easiest way to describe the graph is as int[][]. The inner array is the nodes in graph and the outer array is the distance connecting each node in the graph, e.g.:

new int[][] {
    {0, 5, 0, 0}, // node 0 (the "source")
    {0, 0, 4, 0}, // node 1
    {0, 0, 0, 8}, // node 2
    {0, 0, 0, 0}  // node 3 (the "destination")
}

So to get from node 0 (the source) to node 3 (the destination the "maximum throughput" would be 4 per turn, because:

• 5 packets can go from node 0 to node 1
• 4 packets can go from node 1 to node 2
• 8 packets can go from node 2 to node 3

On a "per turn" basis, the bottleneck is between node 1 and node 2, where the maximum throughput capacity is 4.

Can someone point me to an algorithm that would solve this "maximum throughput" problem for any given graph defined in this way as int[][] and given source and destination nodes?

The example graph is to be extended with multiple "sources" and "destinations" where I will need to calculate the maximum throughput of the entire system on any given "turn".

I'd appreciate help in the form of algorithms to study or "pseudo-code".

Answer 1

Maximum flow problem is what you are looking for:

In optimization theory, maximum flow problems involve finding a feasible flow through a single-source, single-sink flow network that is maximum.

Edmonds–Karp algorithm is a usual algorithm for finding the Maximum flow:

In computer science, the Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson method for computing the maximum flow in a flow network in O(V E²) time.

As seen from the Pseudocode, it's not a complex algorithm when it comes to implementation. Here is a C++ implementation too.

Minimum cut can be combined with the Maximum flow problem, in order to find a bottleneck (there may be more than one):

The cut in a flow network that separates the source and sink vertices and minimizes the total weight on the edges that are directed from the source side of the cut to the sink side of the cut. As shown in the max-flow min-cut theorem, the weight of this cut equals the maximum amount of flow that can be sent from the source to the sink in the given network.

Minimum cut uses Maximum flow and looks for the first edges that are at capacity.

Read more in Max Flow, Min Cut.