Skip to content

Max Flow / Min Cut Problem using Ford-Fulkerson Algorithm

Notifications You must be signed in to change notification settings

SleekPanther/ford-fulkerson

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

15 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Ford Fulkerson Max-Flow / Min Cut Algorithm

Simple implementation to find the maximum flow through a flow network (no Capacity Scaling)

"0/10" means an edge with capacity 10 and 0 flow assigned

Terminology

  • Residual graph
    Directed graph showing how much of the flow assignments can be undone
    Edge e=(u,v) shows how much flow is left to be assigned to that edge
    Edge e=(v,u) is how much flow already been assigned (how much ca be undone)
  • Augmentation Path
    An arbitrary path from S to T found in residual graph
  • Bottleneck
    Minimum capacity from the path found in the residual graph (how much flow is assigned after each path is found)

Usage

  • vertexCount must be hard coded for different graphs
  • Code deals directly with integer array indexes. Index 0 is S (source) and index vertexCount-1 is T (sink) (-1 since arrays count from 0)
  • arrayIndexStringEquivalents holds string equivalents of the index. So vertices can have humanly readable IDs like S & T, and don't have to be sequential integers
    • arrayIndexStringEquivalents[1] is 2 because the vertex called "2" is the in position 1 in the array indexes
  • Graphs are represented as adjacency matrices
    • Directed Graph so order matters
    • graphMatrix[i][j] represents the capacity of an edge from i to j
      • 0 if no edge exists
      • No vertex has an edge to itself. There should always be a 0 in graphMatrix[x][x]
        • graphMatrix[0][0] is 0 since S has no edges to itself
        • Same for all vertices
        • graphMatrix[1][1] is 0 since the vertex in position 1 (vertex "2") has no edges to itself, etc.
      • Row vertexCount-1 is always all 0's since T (the sink) has NO outgoing edges {0, 0, 0, 0, 0, 0, 0, 0}

Final Flow Network

Final Residual Graph

Max Flow = 28

Code Details

  • Constructor takes in an array of strings to have human readable vertices instead of ints
  • maxFlow() finds the maximum flow through the network
    • Creates a residual graph & leaves the original graph unchanged
  • Uses Breadth First Search bfs() to find augmentation paths
    • Returns true/false if a path from S to T was found
    • Updates parent[] array so the actual path can be found
  • maxFlow() outputs each augmentation path found & the amount of flow added to total flow (bottleneck)