ArtsAutosBooksBusinessEducationEntertainmentFamilyFashionFoodGamesGenderHealthHolidaysHomeHubPagesPersonal FinancePetsPoliticsReligionSportsTechnologyTravel

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

Updated on June 11, 2009
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.

Comments

    0 of 8192 characters used
    Post Comment

    • profile image

      donwany 

      2 years ago

      code was perfect

    • profile image

      eng computer 

      6 years ago

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

    • profile image

      hola 

      6 years ago

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

    • profile image

      Rockm8n 

      7 years ago

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

      What the hell is capacity!??

    • profile image

      stefi deltz 

      7 years ago

      where did you get the capacity?

      Capacity

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

    • profile image

      Towfik Jemal 

      8 years ago

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

    working

    This website uses cookies

    As a user in the EEA, your approval is needed on a few things. To provide a better website experience, hubpages.com uses cookies (and other similar technologies) and may collect, process, and share personal data. Please choose which areas of our service you consent to our doing so.

    For more information on managing or withdrawing consents and how we handle data, visit our Privacy Policy at: https://hubpages.com/privacy-policy#gdpr

    Show Details
    Necessary
    HubPages Device IDThis is used to identify particular browsers or devices when the access the service, and is used for security reasons.
    LoginThis is necessary to sign in to the HubPages Service.
    Google RecaptchaThis is used to prevent bots and spam. (Privacy Policy)
    AkismetThis is used to detect comment spam. (Privacy Policy)
    HubPages Google AnalyticsThis is used to provide data on traffic to our website, all personally identifyable data is anonymized. (Privacy Policy)
    HubPages Traffic PixelThis is used to collect data on traffic to articles and other pages on our site. Unless you are signed in to a HubPages account, all personally identifiable information is anonymized.
    Amazon Web ServicesThis is a cloud services platform that we used to host our service. (Privacy Policy)
    CloudflareThis is a cloud CDN service that we use to efficiently deliver files required for our service to operate such as javascript, cascading style sheets, images, and videos. (Privacy Policy)
    Google Hosted LibrariesJavascript software libraries such as jQuery are loaded at endpoints on the googleapis.com or gstatic.com domains, for performance and efficiency reasons. (Privacy Policy)
    Features
    Google Custom SearchThis is feature allows you to search the site. (Privacy Policy)
    Google MapsSome articles have Google Maps embedded in them. (Privacy Policy)
    Google ChartsThis is used to display charts and graphs on articles and the author center. (Privacy Policy)
    Google AdSense Host APIThis service allows you to sign up for or associate a Google AdSense account with HubPages, so that you can earn money from ads on your articles. No data is shared unless you engage with this feature. (Privacy Policy)
    Google YouTubeSome articles have YouTube videos embedded in them. (Privacy Policy)
    VimeoSome articles have Vimeo videos embedded in them. (Privacy Policy)
    PaypalThis is used for a registered author who enrolls in the HubPages Earnings program and requests to be paid via PayPal. No data is shared with Paypal unless you engage with this feature. (Privacy Policy)
    Facebook LoginYou can use this to streamline signing up for, or signing in to your Hubpages account. No data is shared with Facebook unless you engage with this feature. (Privacy Policy)
    MavenThis supports the Maven widget and search functionality. (Privacy Policy)
    Marketing
    Google AdSenseThis is an ad network. (Privacy Policy)
    Google DoubleClickGoogle provides ad serving technology and runs an ad network. (Privacy Policy)
    Index ExchangeThis is an ad network. (Privacy Policy)
    SovrnThis is an ad network. (Privacy Policy)
    Facebook AdsThis is an ad network. (Privacy Policy)
    Amazon Unified Ad MarketplaceThis is an ad network. (Privacy Policy)
    AppNexusThis is an ad network. (Privacy Policy)
    OpenxThis is an ad network. (Privacy Policy)
    Rubicon ProjectThis is an ad network. (Privacy Policy)
    TripleLiftThis is an ad network. (Privacy Policy)
    Say MediaWe partner with Say Media to deliver ad campaigns on our sites. (Privacy Policy)
    Remarketing PixelsWe may use remarketing pixels from advertising networks such as Google AdWords, Bing Ads, and Facebook in order to advertise the HubPages Service to people that have visited our sites.
    Conversion Tracking PixelsWe may use conversion tracking pixels from advertising networks such as Google AdWords, Bing Ads, and Facebook in order to identify when an advertisement has successfully resulted in the desired action, such as signing up for the HubPages Service or publishing an article on the HubPages Service.
    Statistics
    Author Google AnalyticsThis is used to provide traffic data and reports to the authors of articles on the HubPages Service. (Privacy Policy)
    ComscoreComScore is a media measurement and analytics company providing marketing data and analytics to enterprises, media and advertising agencies, and publishers. Non-consent will result in ComScore only processing obfuscated personal data. (Privacy Policy)
    Amazon Tracking PixelSome articles display amazon products as part of the Amazon Affiliate program, this pixel provides traffic statistics for those products (Privacy Policy)