Network Flow

Given a graph with weighted edges (where the weight is the maximum flow capacity of the edge) and unweighted nodes this will determine the maximum amount of flow that can pass from any source node to any sink node.


//Ford-Fulkerson Max-Flow Min-Cut Theorem
public int maxFlow(int source, int sink) {
int maxFlow = 0;
// Initialize the flow matrix (how much has flowed on each edge).
flow = new int[nodeCount][nodeCount];
// While there's a path with flow between the source and the sink...
while (breadthFirstSearch(source, sink)) {
// Backtrack and find minimum cut.
int minCut = Integer.MAX_VALUE;
for (int u = sink; parent[u] >= 0; u = parent[u]) {
minCut = Math.min(minCut, edge[ parent[u] ][u] - flow[ parent[u] ][u]);
}
// Backtrack and adjust total flow of all edges.
for (int u = sink; parent[u] >= 0; u = parent[u]) {
flow[ parent[u] ][u] += minCut;
}
// Add how much flowed in this path.
maxFlow += minCut;
}
return maxFlow;
}