Ford Fulkerson Maximum Flow Minimum Cut Algorithm - Using Matlab, C++ and Java to Solve Max Flow Min Cut
Max Flow Min Cut
I'm sure if you delved deep into computer networking you may have come across the Maximum flow Minimum Cut algorithm also referred to as the Ford Fulkerson Algorithm.
The basic idea behind this algorithm is to take a network diagram with a number of network nodes and links from each node. Each node will show how much capacity can flow down the link. We want to find a way to get the maximum flow from source to destination, this usually means avoiding bottlenecks or links with relatively low capacities compared to other surrounding nodes. The ford fulkerson algorithm is simply an algorithm to compute the maximum flow , which relates directly to the minimum cut so its pretty much the same thing.
I was recently trying to determine the max flow and min cut for a network I was designing and I found many different ways to solve the max flow min cut problem. These included using Matlab, C++, or java. The simplest method is definitely using matlab and I will go through how you can develop your own network and compute the values for maximum flow and minimu cut.
Also note: Great interactive animation that walks you through max flow min cut theorem www.cse.yorku.ca/~aaw/Wang/MaxFlowStart.htm
A little background Knowledge
The maximum flow problem refers to finding the most suitable & feasible way through a single sourced & sinks network. It is also seen as the maximum amount of flow that we can achieve from source to destination which is an incredibly important consideration especially in data networks where maximum throughput and minimum delay are preferred.
Finding the maximum flow involves looking at all the possible routes between source and destination. When the network is designed the links represent channels of flow with limited capacities. Maximum flow can be found by assigning flow to each link in the network so that the total flow from source to destination is as large as possible.
The maximum source to sink flow in a network is equal to the minimum source to sink cut in the network, which makes up the Maximum Flow minimum cut theorem.
A cut is any set of directed links containing at least one link in every path from origin node to destination node. This means if the links in the cut are removed the flow from the origin to destination is completely cut off. The cut value is the sum of the flow capacities in the origin to node direction over all the links. The minimum cut problem is to find the cut across the network that has the minimum cut value over all possible cuts.
The maximum flow problem is closely related to the minimum cut problem, creating the maximum flow minimum cut theorem.
Its also possible to compute the max flow and min cut manually but it can become very time consuming. One method is to understand the actual algorithm and all the mathematics behind it but that gets tricky and I will cover an easy manual method.
The basic idea behind it is to take your network diagram and then
- Draw cut across the network that separate the source and destination nodes
- The cuts across the network will cross a number of links
- Add the capacity link values of the cuts
- Now look through all your cuts, and the one with the smallest capacity value is your minimum cut.
This is all good but when it comes to complex networks will a million cuts all over the shop you will go mad trying to spot them.
Using MATLAB to solve
So by far the easiest way to compute maximum flow and minimum cut on any network you desire is to use matlab, a very powerful maths software package. The great thing about matlab is that it has inbuilt commands designed specifically to solve this algorithm. Which makes it incredibly simple.
Note: Matlab Version 2008 or over is recommended otherwise errors may occur.
For all those new to matlab just run these commands through the command line, sometimes it the window wont be open simple click window in the toolbar and select the command line window.
1.) Create your matrix which tells matlab how many nodes, links and how the links connect nodes, as well as link capacities
cm = sparse([1 1 2 2 3 4 4 5 5 6 7 8 9 9],[2 3 3 4 5 6 7 6 7 8 9 10 8 10],[15 10 3 8 9 7 5 6 2 12 10 6 10 8],10,10
Here I have created my matrix to run max flow min cut algorithm on. The Network Design looks like below
1 1 2 2 3 4 4 5 5 6 7 8 9 9
2 3 3 4 5 6 7 6 7 8 9 10 8 10
2 3 1 3 2 4 5 6 2 3 2 4 2 2
Matlab Network View
Matlab - Finding Max flow and Min cut
We can then find the maximum flow and minimum cut using the command
[M,F,K] = graphmaxflow(cm,1,10) [for example above]
M = The Maximum Flow
F = Flow on each link
K = Minimum cut (result displayed in matrix)
cm = Refers to the collection of data we inputted early, a N x N matrix
1 = The Source node
10 = The Destination node
Once you use this command it will display results for Max flow , Flow on each link and Minimum Cut.
Viewing the Maximum Flow Network Diagram
View Minimum Cut
set(h.Nodes(K(1,:)),'Color',[1 0 0])
(note: you will need to keep your original network diagram open to view the minimum cut solution)
So that's pretty much it for solving your max flow min cuts for a network design of your choice, if you have any question let me know and i will try to help you out.
There are many other methods for solving the maximum flow minimum cut problem and these include using C++, java, xml and a few others ( it can also be done in mathcad and goblin)
Some links below to code for the Max Flow Min Cut
http://www.pastey.net/115644-14wn - Max flow min cut code
Ford Fulkerson Package (good alternative to method above) - http://www.mathworks.com.au/matlabcentral/fileexchange/19439
have some more code somewhere including xml will paste the code when i find it.