Python Data Structure and Algorithm Tutorial – Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm


In this tutorial, you will learn what Ford-Fulkerson algorithm is. Also, you will find working examples of finding maximum flow in a flow network in Python.

Ford-Fulkerson algorithm is a greedy approach for calculating the maximum possible flow in a network or a graph.

A term, flow network, is used to describe a network of vertices and edges with a source (S) and a sink (T). Each vertex, except S and T, can receive and send an equal amount of stuff through it. S can only send and T can only receive stuff.

We can visualize the understanding of the algorithm using a flow of liquid inside a network of pipes of different capacities. Each pipe has a certain capacity of liquid it can transfer at an instance. For this algorithm, we are going to find how much liquid can be flowed from the source to the sink at an instance using the network.

Flow network
Flow network graph

Terminologies Used

Augmenting Path

It is the path available in a flow network.

Residual Graph

It represents the flow network that has additional possible flow.

Residual Capacity

It is the capacity of the edge after subtracting the flow from the maximum capacity.


How Ford-Fulkerson Algorithm works?

The algorithm follows:

  1. Initialize the flow in all the edges to 0.
  2. While there is an augmenting path between the source and the sink, add this path to the flow.
  3. Update the residual graph.


We can also consider reverse-path if required because if we do not consider them, we may never find a maximum flow.

The above concepts can be understood with the example below.

Ford-Fulkerson Example

The flow of all the edges is 0 at the beginning.

Flow network
Flow network graph example
  1. Select any arbitrary path from S to T. In this step, we have selected path S-A-B-T.
    Find a path
    Find a path

    The minimum capacity among the three edges is 2 (B-T). Based on this, update the flow/capacity for each path.

    Update the capacities
    Update the capacities
  2. Select another path S-D-C-T. The minimum capacity among these edges is 3 (S-D).
    Find next path
    Find next path

    Update the capacities according to this.

    Update the capacities
    Update the capacities
  3. Now, let us consider the reverse-path B-D as well. Selecting path S-A-B-D-C-T. The minimum residual capacity among the edges is 1 (D-C).
    Find next path
    Find next path

    Updating the capacities.

    Update the capacities
    Update the capacities

    The capacity for forward and reverse paths are considered separately.

  4. Adding all the flows = 2 + 3 + 1 = 6, which is the maximum possible flow on the flow network.

Note that if the capacity for any edge is full, then that path cannot be used.

Python Examples

/* Ford-Fulkerson algorith in Python */

from collections import defaultdict

class Graph:

    def __init__(self, graph):
        self.graph = graph
        self. ROW = len(graph)

    /* Using BFS as a searching algorithm */
    def searching_algo_BFS(self, s, t, parent):

        visited = [False] * (self.ROW)
        queue = []

        visited[s] = True

        while queue:

            u = queue.pop(0)

            for ind, val in enumerate(self.graph[u]):
                if visited[ind] == False and val > 0:
                    visited[ind] = True
                    parent[ind] = u

        return True if visited[t] else False

    /* Applying fordfulkerson algorithm */
    def ford_fulkerson(self, source, sink):
        parent = [-1] * (self.ROW)
        max_flow = 0

        while self.searching_algo_BFS(source, sink, parent):

            path_flow = float("Inf")
            s = sink
            while(s != source):
                path_flow = min(path_flow, self.graph[parent[s]][s])
                s = parent[s]

            /* Adding the path flows */
            max_flow += path_flow

            /* Updating the residual values of edges */
            v = sink
            while(v != source):
                u = parent[v]
                self.graph[u][v] -= path_flow
                self.graph[v][u] += path_flow
                v = parent[v]

        return max_flow

graph = [[0, 8, 0, 0, 3, 0],
         [0, 0, 9, 0, 0, 0],
         [0, 0, 0, 0, 7, 2],
         [0, 0, 0, 0, 0, 5],
         [0, 0, 7, 4, 0, 0],
         [0, 0, 0, 0, 0, 0]]

g = Graph(graph)

source = 0
sink = 5

print("Max Flow: %d " % g.ford_fulkerson(source, sink))

Ford-Fulkerson Applications

  • Water distribution pipeline
  • Bipartite matching problem
  • Circulation with demands


Python Example for Beginners

Two Machine Learning Fields

There are two sides to machine learning:

  • Practical Machine Learning:This is about querying databases, cleaning data, writing scripts to transform data and gluing algorithm and libraries together and writing custom code to squeeze reliable answers from data to satisfy difficult and ill defined questions. It’s the mess of reality.
  • Theoretical Machine Learning: This is about math and abstraction and idealized scenarios and limits and beauty and informing what is possible. It is a whole lot neater and cleaner and removed from the mess of reality.

Data Science Resources: Data Science Recipes and Applied Machine Learning Recipes

Introduction to Applied Machine Learning & Data Science for Beginners, Business Analysts, Students, Researchers and Freelancers with Python & R Codes @ Western Australian Center for Applied Machine Learning & Data Science (WACAMLDS) !!!

Latest end-to-end Learn by Coding Recipes in Project-Based Learning:

Applied Statistics with R for Beginners and Business Professionals

Data Science and Machine Learning Projects in Python: Tabular Data Analytics

Data Science and Machine Learning Projects in R: Tabular Data Analytics

Python Machine Learning & Data Science Recipes: Learn by Coding

R Machine Learning & Data Science Recipes: Learn by Coding

Comparing Different Machine Learning Algorithms in Python for Classification (FREE)

Disclaimer: The information and code presented within this recipe/tutorial is only for educational and coaching purposes for beginners and developers. Anyone can practice and apply the recipe/tutorial presented here, but the reader is taking full responsibility for his/her actions. The author (content curator) of this recipe (code / program) has made every effort to ensure the accuracy of the information was correct at time of publication. The author (content curator) does not assume and hereby disclaims any liability to any party for any loss, damage, or disruption caused by errors or omissions, whether such errors or omissions result from accident, negligence, or any other cause. The information presented here could also be found in public knowledge domains.  

Google –> SETScholars