Ford Fulkerson Maximum Flow Minimum Cut Algorithm - Using Matlab, C++ and Java to Solve Max Flow Min Cut

picture from scienceblogs.com
picture from scienceblogs.com

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

Maximum Cut

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.

Minimum Cut

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.

Manual Method

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.

Very simple example, cut that separates source and node , in this case crossed links with values of 2 and 5, there this cut is worth 7, keep going till you find the cut with smallest capacity
Very simple example, cut that separates source and node , in this case crossed links with values of 2 and 5, there this cut is worth 7, keep going till you find the cut with smallest capacity

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.

Matlab Instructions

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

Source

1 1 2 2 3 4 4 5 5 6 7 8 9 9

Destination

2 3 3 4 5 6 7 6 7 8 9 10 8 10

Capacity

2 3 1 3 2 4 5 6 2 3 2 4 2 2

Matlab Network View

To see a network diagram picture in matlab use the command  "h = view(biograph(cm,[],'ShowWeights','on'))"
To see a network diagram picture in matlab use the command "h = view(biograph(cm,[],'ShowWeights','on'))"

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(biograph(F,[],'ShowWeights','on'))

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.

Picture of min cut solution on the left as well as max flow graph on right.
Picture of min cut solution on the left as well as max flow graph on right.

Other Methods

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

C++

http://www.cs.ucl.ac.uk/staff/V.Kolmogorov/software.html

http://www.pastey.net/115644-14wn - Max flow min cut code

Java

http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/maxflow/Maxflow.shtml

Matlab

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.

More by this Author


Comments 6 comments

Towfik Jemal 6 years ago

Everything is ok. But i couldn't similarity between minimum cut and maximum flow.


stefi deltz 5 years ago

where did you get the capacity?

Capacity

2 3 1 3 2 4 5 6 2 3 2 4 2 2


Rockm8n 5 years ago

What is this.. cant even reply to the man?!!

What the hell is capacity!??


hola 4 years ago

du you have any algorithm taking into account the lower bounds ?


eng computer 4 years ago

in the same way i want to select more then one way (alternative path) can that ?


donwany 13 months ago

code was perfect

    Sign in or sign up and post using a HubPages Network account.

    0 of 8192 characters used
    Post Comment

    No HTML is allowed in comments, but URLs will be hyperlinked. Comments are not for promoting your articles or other sites.


    Click to Rate This Article
    working