Skip to content

Instantly share code, notes, and snippets.

@Eyas
Created November 18, 2013 01:08
Show Gist options
  • Save Eyas/7520781 to your computer and use it in GitHub Desktop.
Save Eyas/7520781 to your computer and use it in GitHub Desktop.
Edmonds Karp in C#
using System;
using System.Collections.Generic;
namespace Algorithms
{
/// Edmonds Karp MaxFlow Algorithm
/// based on en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm
public class EdmondsKarp {
private int n = 0;
public int FindMaxFlow(
int[,] capacityMatrix,
Dictionary<int, List<int>> neighbors,
int source,
int sink,
out int[,] legalFlows)
{
n = capacityMatrix.GetLength(0);
int f = 0; // initial flow is 0
legalFlows = new int[n, n]; // residual capacity from u to v is capacityMatrix[u,v] - legalFlows[u,v]
while(true)
{
int[] p;
int m = BreadthFirstSearch(capacityMatrix, neighbors, source, sink, legalFlows, out p);
if (m == 0) break;
f += m;
// backtrakc search, and write flow
int v = sink;
while (v != source)
{
int u = p[v];
legalFlows[u, v] += m;
legalFlows[v, u] -= m;
v = u;
}
}
return f;
}
private int BreadthFirstSearch(
int[,] capacityMatrix,
Dictionary<int, List<int>> neighbors,
int source,
int sink,
int[,] legalFlows,
out int[] p)
{
p = new int[n];
for (int u = 0; u <n; u++)
{
p[u] = -1;
}
p[source] = -2; // make sure source is not rediscovered
int[] m = new int[n]; // capacity of found path to node
m[source] = int.MaxValue;
Queue<int> q = new Queue<int>();
q.Enqueue(source);
while (q.Count > 0)
{
int u = q.Dequeue();
foreach (int v in neighbors[u])
{
// if there is available capacity, and v is not seen before in search
if (capacityMatrix[u, v] - legalFlows[u, v] > 0 &&
p[v] == -1)
{
p[v] = u;
m[v] = Math.Min(m[u], capacityMatrix[u,v] - legalFlows[u,v]);
if (v != sink) q.Enqueue(v);
else return m[sink];
}
}
}
return 0;
}
}
}
Copy link

ghost commented Feb 6, 2020

Hello! Can you please show example input data for EdmondsKarp().FindMaxFlow(...)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment