## What is Max Flow?

Given a **graph representing a flow network** in which one of the vertexes is considered as a **source** (From where the flow will start) and another single vertex as a** sink** (where the flow will end). Each edge has some specific capacity which represents the maximum flow through that edge.

We need to find the maximum possible flow from source to sink in the given graph (network). The **maximum possible flow value is known as max flow**.

**Tip**: Consider each edge as water pipe with a specific width (capacity in case of the graph). We need to find the maximum flow of water from source to sink in the given pipe network (Pipe with larger width/capacity will allow large flow).

## Ford Fulkerson Algorithm

Ford Fulkerson Algorithm helps in finding the max flow of the graph. In the Ford-Fulkerson method, we repeatedly find** augmenting path** through the **residual graph** and **augment the flow** until no more augmenting paths can be found.

**Residual Graph**: It is the given original graph but with the extra equal number of opposite edges as total original edges in the original graph. The capacity of each opposite edge is 0.

*Each Edge has (flow, Capacity) and initially flow = 0.*

**Augmenting Path**: It is the path of edges in which the unused capacity is greater than 0 i.e the **flow from source to sink is possible through this path**.

**Augment the path: **Means updating the flow value of the edges along the augmenting path.

On getting any augmenting path we update the residual graph ( i.e update flow of edges in the path found). Again we recheck for augmenting path in the updated graph. If found any, then means that more amount can flow through the network graph. Hence we **add the possible flow of the augmenting path to the max flow**.

**InShort:** Repeatedly find the path through which the flow from source to sink is possible and update the flow of the graph until no such path is still left.

### Java Program to Implement Ford Fulkerson Algorithm

Before starting program first we need to know **how to make a network graph** in a programming language.

For this, we first need to make Edge and Vertex class. Each Edge class object will represent a different edge and each Vertex class object will represent a different vertex.

So each Edge will have:

Similarly, each Vertex will have:

So we need to **create objects of Vertex and Edge class** depending on the size of the graph and **connect them with each other** to make complete network graph.

The Ford Fulkerson algorithm is not applicable to the original graph, we need to **create the residual graph of the original graph** by creating opposite residual edges for each original edges.

* Remember: Initially flow for all edges *is 0

*and capacity of residual edges should be 0.*

Now apply Ford Fulkerson algorithm until no argument path is left.

**Note:** Backtracking is used to find the augmenting path in the residual graph.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 |
package FordFulkerson; import java.util.ArrayList; import java.util.List; public class Vertex { String name; List<Edge> adjacentEdges; int currentVisit; public Vertex(String name) { this.name = name; this.adjacentEdges = new ArrayList<>(); this.currentVisit = 0; } public void addNeighbour(Edge edge){ adjacentEdges.add(edge); } } public class Edge { Vertex fromVertex; Vertex toVertex; double capacity; double flow; Edge residual; public Edge(Vertex s, Vertex t, double c){ this.fromVertex = s; this.toVertex = t; this.capacity =c; } private boolean isResidual(){ return capacity == 0; } public double remainingCapacity(){ return capacity - flow; } //Augment path/edge public void augment(double bottleneck){ //Updating the flow of the edge flow += bottleneck; //Decreasing the flow of the residual/opposite edge residual.flow -= bottleneck; } } public class FordFulkerson { Vertex source; Vertex sink; int visitedToken; double maxFlow; //Setting Source & Sink public FordFulkerson(Vertex source, Vertex sink){ this.source =source; this.sink = sink; this.visitedToken =0; this.maxFlow = 0; } //Solve For max flow using Ford Fulkerson Method public void solve(){ visitedToken =1; //Assuming initially that infinity amount can flow through the network double flow = Double.MAX_VALUE; //Finding augment path until there is none left do{ //If returned value of flow is not 0 then there is augment path flow = hasAugmentPath(flow, source); //Adding flow to calculate max flow maxFlow += flow; visitedToken++; //Updating visited token for next check } while(flow != 0); } private double hasAugmentPath(double flow, Vertex vertex) { //If current Vertex is sink then we reached the target //It means flow is possible, so return possible flow if(vertex == sink) return flow; //Updating the current visit of the vertex to visitedToken //So that we do visit the same vertex again vertex.currentVisit =visitedToken; //Checking if flow can be continued through any connected adjacentEdges //Flow can only be continued if remaining capacity of edges is > 0 for(Edge edge: vertex.adjacentEdges){ if(edge.remainingCapacity() > 0 && edge.toVertex.currentVisit != visitedToken){ //Checking min of flow and remaining capacity //If remaining capacity == 0, then min will be 0 //It means no more flow is possible through the network double bottleneck = hasAugmentPath(Double.min(flow,edge.remainingCapacity()),edge.toVertex); //By Backtracking we augment each edge if there is any flow possible if(bottleneck > 0){ edge.augment(bottleneck); return bottleneck; } } } //Returning 0 if no flow is possible through any connected egdes return 0; } } public class App { public static void main(String args[]){ //Creating Vertexs List<Vertex> vertexs = new ArrayList<>(); vertexs.add(new Vertex("A")); //0 vertexs.add(new Vertex("B")); //1 vertexs.add(new Vertex("C")); //2 vertexs.add(new Vertex("D")); //3 //Creating Edges List<Edge> edges = new ArrayList<>(); edges.add(new Edge(vertexs.get(0),vertexs.get(1),10)); edges.add(new Edge(vertexs.get(1),vertexs.get(3),4)); edges.add(new Edge(vertexs.get(2),vertexs.get(3),6)); edges.add(new Edge(vertexs.get(0),vertexs.get(2),6)); edges.add(new Edge(vertexs.get(2),vertexs.get(1),10)); //Edges and vertices are created but not connected for(Edge edge: edges){ //Creating opposite edge Edge opposite = new Edge(edge.toVertex,edge.fromVertex,0); edge.residual = opposite; opposite.residual = edge; //Connecting vertices with edges and residual edges edge.fromVertex.addNeighbour(edge); edge.toVertex.addNeighbour(opposite); } //Source - 0 -> A //Sink - 3 -> D FordFulkerson fordFulkerson = new FordFulkerson(vertexs.get(0),vertexs.get(3)); fordFulkerson.solve(); System.out.println("Max Flow:"+fordFulkerson.maxFlow); } } |

We have made augment method in the edge class to update the flow of the current edge and to reduce the flow of the residual edge.

* Remember: Residual edge of the original edge is opposite edge and the residual edge of the opposite edge is the original edge. So in augment, we increase the flow value of the current edge (can be *original

*or opposite edge) and decrease the flow of the corresponding residual edge.*

**Max Flow is the sum of all possible flow of the augmenting paths.**

### Output

That’s all for Ford Fulkerson Max Flow algorithm. It is possible that you may understand this algorithm or program in one go. Give it few try and watch the video again. You will surely start getting an idea how this algorithm works. Still you have any doubt then comment below.