Solving Flows in Network Formats

Flows in Networks

Flows in Networks are used in problems such as traffic on roads and oil in pipelines. This graph is called a digraph where the arcs have a direction denoted by an arrow. The weights on the arcs are the capacities of the arc and show the limit of the flow that can be passes down that arc.

Consider a network with N nodes. Node 1 will be the source (all flow will come from node 1). Node N will be the sink (all flow will be to node N). For all the other nodes we will assume conservation of flow, i.e. no flow is lost.

The object is to maximise the total flow from node 1 to node N.

Intuitive Approach

Step 1. Find any flow-augmenting path from source to sink such that each of the arcs has a positive flow capacity.

Step 2. The arc with the smallest flow capacity limits the flow along the path. Assign (i.e. ‘send’) this flow (f) and reduce the capacities of the arcs on this path by f.

Step 3. Repeat steps 1 and 2 until no suitable path can be found.

e.g. Initial Flow-augmenting Path 1 ® 2 ® 4 ® 6 f1 = 4

Second Flow-augmenting Path 1 ® 3 ® 5 ® 6 f2 = 4

Third Flow-augmenting Path 1® 3 ® 4 ® 6 f3 = 1

Maximal flow = 4 + 4 + 1 = 9 (this is obviously maximal since all the arcs from the source are saturated).

It’s often difficult to see useful applications for these diagrams but they’re actually very useful in real life.   For instance creating such structure would have definitely helped programmers and designers who created the Netflix algorithm which creates your suggested option screens.  Using the data from previous selections it can use flow format theorems to create a likely pattern of other shows.  Just look carefully how the structure works, if you haven’t got Netflix access then just use this trial to watch the US version!

If however our initial flow-augmenting path was 1® 3 ® 4 ® 6, f1 = 5, then the network would be stuck but not at maximal flow. We must therefore build in a refinement to stop us getting stuck. The idea is to allow a ‘fictitious’ back flow in the wrong direction along an arc in order to cancel out all, or part, of a previously assigned flow. e.g. in the above stuck network we could send up to 5 from node 4 to node 3 and still end up with a real flow from node 3 to node 4. So the second path is 1 ® 2 ® 4 ® 3 ® 5® 6, f2 = 4. Now continuing as before we could again have a flow of 9. (The real flow along (3,4) is 1 from node 3 to node 4).

A different notation can be used called the labelling procedure and appears to be preferred by the examination board.  They are commonly used in network diagrams too if you want to illustrate the flow from something like a e-commerce server to an ATC proxy, or other network devices. In this method when the capacity is reduced after flow has been assigned a back flow in the opposite direction is shown. This can help in two ways; one is by showing the total flow after a few iterations along a certain arc, even if it is the “wrong” direction. The second is it may help with the fictitious flows mentioned above.