Add Edmonds-Karp Algorithm in R

[nachiket2005]

Overview

The edmonds_karp function finds the maximum flow in a directed network by repeatedly searching for augmenting paths using Breadth-First Search (BFS).
At each iteration, it augments the flow along the shortest available path in terms of edge count, ensuring predictable and polynomial runtime.

This implementation follows the repository style conventions:

• Uses 1-based vertex indexing
• Provides a clear header and example usage
• Returns both the maximum flow value and residual capacity matrix

---

Features

• Implements the Edmonds-Karp variant of the Ford-Fulkerson algorithm
• Uses BFS to find shortest augmenting paths
• Works with directed graphs represented as numeric capacity matrices
• Returns both:
  • max_flow — total maximum flow value
  • residual — resulting residual capacity matrix
• Includes a ready-to-run example for verification

---

Complexity

• Time Complexity: O(V × E²)
• Space Complexity: O(V²) (due to capacity and residual matrices)

---

Demonstration

Run the following example in an R session to test the algorithm:

source('R/graph_algorithms/edmonds_karp.r')

graph <- matrix(c(
  0, 16, 13, 0, 0, 0,
  0, 0, 10, 12, 0, 0,
  0, 4, 0, 0, 14, 0,
  0, 0, 9, 0, 0, 20,
  0, 0, 0, 7, 0, 4,
  0, 0, 0, 0, 0, 0
), nrow = 6, byrow = TRUE)

source <- 1L
sink <- 6L

res <- edmonds_karp(graph, source, sink)
cat("Maximum Flow:", res$max_flow, "\n")