// Edmond-Karp algorithm is an implementation of the Ford-Fulkerson method
// to compute max-flow between a pair of source-sink vertices in a weighted graph
// It uses BFS (Breadth First Search) to find the residual paths
// Time Complexity: O(V * E^2) where V is the number of vertices and E is the number of edges
// Space Complexity: O(V + E) Because we keep residual graph in size of the original graph
// Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, Third Edition (3rd. ed.). The MIT Press.
package graph
import (
"math"
)
// Returns a mapping of vertices as path, if there is any from source to sink
// Otherwise, returns nil
func FindPath(rGraph WeightedGraph, source int, sink int) map[int]int {
queue := make([]int, 0)
marked := make([]bool, len(rGraph))
marked[source] = true
queue = append(queue, source)
parent := make(map[int]int)
// BFS loop with saving the path found
for len(queue) > 0 {
v := queue[0]
queue = queue[1:]
for i := 0; i < len(rGraph[v]); i++ {
if !marked[i] && rGraph[v][i] > 0 {
parent[i] = v
// Terminate the BFS, if we reach to sink
if i == sink {
return parent
}
marked[i] = true
queue = append(queue, i)
}
}
}
// source and sink are not in the same connected component
return nil
}
func EdmondKarp(graph WeightedGraph, source int, sink int) float64 {
// Check graph emptiness
if len(graph) == 0 {
return 0.0
}
// Check correct dimensions of the graph slice
for i := 0; i < len(graph); i++ {
if len(graph[i]) != len(graph) {
return 0.0
}
}
rGraph := make(WeightedGraph, len(graph))
for i := 0; i < len(graph); i++ {
rGraph[i] = make([]float64, len(graph))
}
// Init the residual graph with the same capacities as the original graph
copy(rGraph, graph)
maxFlow := 0.0
for {
parent := FindPath(rGraph, source, sink)
if parent == nil {
break
}
// Finding the max flow over the path returned by BFS
// i.e. finding minimum residual capacity amonth the path edges
pathFlow := math.MaxFloat64
for v := sink; v != source; v = parent[v] {
u := parent[v]
if rGraph[u][v] < pathFlow {
pathFlow = rGraph[u][v]
}
}
// update residual capacities of the edges and
// reverse edges along the path
for v := sink; v != source; v = parent[v] {
u := parent[v]
rGraph[u][v] -= pathFlow
rGraph[v][u] += pathFlow
}
// Update the total flow found so far
maxFlow += pathFlow
}
return maxFlow
}