Ford-Fulkerson Algorithm for Maximum Flow Problem - GeeksforGeeks
Given a graph which represents a flow network where every edge has a capacity. Also given two vertices source ‘s’ and sink ‘t’ in the graph, find the maximum possible flow from s to t with following constraints:
a) Flow on an edge doesn’t exceed the given capacity of the edge.
b) Incoming flow is equal to outgoing flow for every vertex except s and t.
https://sites.google.com/site/indy256/algo/edmonds_karp
https://code.google.com/p/svantes-petrinet/source/browse/PrisonProblem/trunk/src/EdmondsKarp.java?spec=svn14&r=14
prev[] array: BFS(or DFS) path
static class Edge { int s, t, rev, cap, f;}
public static int maxFlow(List<Edge>[] graph, int s, int t) {
int flow = 0;
int[] q = new int[graph.length];
while (true) {
int qt = 0;
q[qt++] = s;
Edge[] pred = new Edge[graph.length];
for (int qh = 0; qh < qt && pred[t] == null; qh++) {
int cur = q[qh];
for (Edge e : graph[cur]) {
if (pred[e.t] == null && e.cap > e.f) {
pred[e.t] = e;
q[qt++] = e.t;
}
}
}
if (pred[t] == null)
break;
int df = Integer.MAX_VALUE;
for (int u = t; u != s; u = pred[u].s)
df = Math.min(df, pred[u].cap - pred[u].f);
for (int u = t; u != s; u = pred[u].s) {
pred[u].f += df;
graph[pred[u].t].get(pred[u].rev).f -= df;
}
flow += df;
}
return flow;
}
http://algs4.cs.princeton.edu/64maxflow/FordFulkerson.java.html
Read full article from Ford-Fulkerson Algorithm for Maximum Flow Problem - GeeksforGeeks
Given a graph which represents a flow network where every edge has a capacity. Also given two vertices source ‘s’ and sink ‘t’ in the graph, find the maximum possible flow from s to t with following constraints:
a) Flow on an edge doesn’t exceed the given capacity of the edge.
b) Incoming flow is equal to outgoing flow for every vertex except s and t.
The maximum possible flow in the above graph is 23.
Ford-Fulkerson Algorithm
The following is simple idea of Ford-Fulkerson algorithm:
1) Start with initial flow as 0.
2) While there is a augmenting path from source to sink.
Add this path-flow to flow.
3) Return flow.
Time Complexity: Time complexity of the above algorithm is O(max_flow * E). We run a loop while there is an augmenting path. In worst case, we may add 1 unit flow in every iteration. Therefore the time complexity becomes O(max_flow * E).
Residual capacity is 0 if there is no edge between to vertices of residual graph. We can initialize the residual graph as original graph as there is no initial flow and initially residual capacity is equal to original capacity.
To find an augmenting path, we can either do a BFS or DFS of the residual graph. We have used BFS in below implementation. Using BFS, we can find out if there is a path from source to sink. BFS also builds parent[] array. Using the parent[] array, we traverse through the found path and find possible flow through this path by finding minimum residual capacity along the path. We later add the found path flow to overall flow.
The important thing is, we need to update residual capacities in the residual graph. We subtract path flow from all edges along the path and we add path flow along the reverse edges We need to add path flow along reverse edges because may later need to send flow in reverse direction.
Edmonds–Karp_algorithm
It is called a "method" instead of an "algorithm" as the approach to finding augmenting paths in a residual graph is not fully specified or it is specified in several implementations with different running times.
s long as there is a path from the source (start node) to the sink (end node), with available capacity on all edges in the path, we send flow along one of the paths. Then we find another path, and so on. A path with available capacity is called an augmenting path.
The above implementation of Ford Fulkerson Algorithm is called Edmonds-Karp Algorithm. The idea of Edmonds-Karp is to use BFS in Ford Fulkerson implementation as BFS always picks a path with minimum number of edges. When BFS is used, the worst case time complexity can be reduced to O(VE2). The above implementation uses adjacency matrix representation though where BFS takes O(V2) time, the time complexity of the above implementation is O(EV3)
The algorithm is identical to the Ford–Fulkerson algorithm, except that the search order when finding the augmenting path is defined. The path found must be a shortest path that has available capacity. This can be found by a breadth-first search, as we let edges have unit length. The running time of O(V E2) is found by showing that each augmenting path can be found in O(E) time, that every time at least one of the E edges becomes saturated (an edge which has the maximum possible flow), that the distance from the saturated edge to the source along the augmenting path must be longer than last time it was saturated, and that the length is at most V. Another property of this algorithm is that the length of the shortest augmenting path increases monotonically.
Back edges are the edges on which you can decrease the flow to find new paths which can potentially lead to a higher flow than the current value. This can happen in cases when you pick a path which prevent other paths from being picked which might result in higher flow. Sending flow along a back edge essentially means removing flow along that path and pushing the difference along other paths.
Flow augmenting paths
Flow augmenting path = a path from source S to sink T where you can increase the amount of flow of the commodity
I distinguish 2 types of flow augmenting paths:
I call the first type of flow augmenting paths:
Purely unsaturated path
A path from source S → sink T consisting entirely if unsaturated edges is an flow augmenting path
I call the second type of flow augmenting paths:
Hybrid paths
Slack: amount of increase on a flow augmenting path
Slack( path ) = maximum amount of flow that can be
increased along the given path
Slack on a flow augmenting path of type #1:
Slack ( flow augmenting path type 1 ) = min e ∈ path ( c(e) - f(e) )
Flow augment path --- preliminray to the type #2 paths
The edge e is an forward edge if:
The path P uses edge e in the forward direction
The edge e is an backward edge if:
The path P uses edge e in the backward direction
The flow on a (any) path is increased by:
Increasing the flow on the forward edges of the path and (simultaneously)
Decreasing the flow on the back edges of the path !!!!
When you cut back on the amount you push backward, you will increase the amount that you push forward !!!
If 𝑓 amount of flow goes through 𝑢 → 𝑣, then:
Decrease 𝑐 𝑢 → 𝑣 by 𝑓
Increase 𝑐 𝑣 → 𝑢 by 𝑓
Why do we need to do this?
Sending flow to both directions is equivalent to
canceling flow
/* Returns true if there is a path from source 's' to sink 't' in residual graph. Also fills parent[] to store the path */bool bfs(int rGraph[V][V], int s, int t, int parent[]){ // Create a visited array and mark all vertices as not visited bool visited[V]; memset(visited, 0, sizeof(visited)); // Create a queue, enqueue source vertex and mark source vertex // as visited queue <int> q; q.push(s); visited[s] = true; parent[s] = -1; // Standard BFS Loop while (!q.empty()) { int u = q.front(); q.pop(); for (int v=0; v<V; v++) { if (visited[v]==false && rGraph[u][v] > 0) { q.push(v); parent[v] = u; visited[v] = true; } } } // If we reached sink in BFS starting from source, then return // true, else false return (visited[t] == true);}// Returns tne maximum flow from s to t in the given graphint fordFulkerson(int graph[V][V], int s, int t){ int u, v; // Create a residual graph and fill the residual graph with // given capacities in the original graph as residual capacities // in residual graph int rGraph[V][V]; // Residual graph where rGraph[i][j] indicates // residual capacity of edge from i to j (if there // is an edge. If rGraph[i][j] is 0, then there is not) for (u = 0; u < V; u++) for (v = 0; v < V; v++) rGraph[u][v] = graph[u][v]; int parent[V]; // This array is filled by BFS and to store path int max_flow = 0; // There is no flow initially // Augment the flow while tere is path from source to sink while (bfs(rGraph, s, t, parent)) { // Find minimum residual capacity of the edhes along the // path filled by BFS. Or we can say find the maximum flow // through the path found. int path_flow = INT_MAX; for (v=t; v!=s; v=parent[v]) { u = parent[v]; path_flow = min(path_flow, rGraph[u][v]); } // update residual capacities of the edges and reverse edges // along the path for (v=t; v != s; v=parent[v]) { u = parent[v]; rGraph[u][v] -= path_flow; rGraph[v][u] += path_flow; } // Add path flow to overall flow max_flow += path_flow; } // Return the overall flow return max_flow;}https://code.google.com/p/svantes-petrinet/source/browse/PrisonProblem/trunk/src/EdmondsKarp.java?spec=svn14&r=14
prev[] array: BFS(or DFS) path
static class Edge { int s, t, rev, cap, f;}
public static int maxFlow(List<Edge>[] graph, int s, int t) {
int flow = 0;
int[] q = new int[graph.length];
while (true) {
int qt = 0;
q[qt++] = s;
Edge[] pred = new Edge[graph.length];
for (int qh = 0; qh < qt && pred[t] == null; qh++) {
int cur = q[qh];
for (Edge e : graph[cur]) {
if (pred[e.t] == null && e.cap > e.f) {
pred[e.t] = e;
q[qt++] = e.t;
}
}
}
if (pred[t] == null)
break;
int df = Integer.MAX_VALUE;
for (int u = t; u != s; u = pred[u].s)
df = Math.min(df, pred[u].cap - pred[u].f);
for (int u = t; u != s; u = pred[u].s) {
pred[u].f += df;
graph[pred[u].t].get(pred[u].rev).f -= df;
}
flow += df;
}
return flow;
}
http://algs4.cs.princeton.edu/64maxflow/FordFulkerson.java.html
public FordFulkerson(FlowNetwork G, int s, int t) { validate(s, G.V()); validate(t, G.V()); if (s == t) throw new IllegalArgumentException("Source equals sink"); if (!isFeasible(G, s, t)) throw new IllegalArgumentException("Initial flow is infeasible"); // while there exists an augmenting path, use it value = excess(G, t); while (hasAugmentingPath(G, s, t)) { // compute bottleneck capacity double bottle = Double.POSITIVE_INFINITY; for (int v = t; v != s; v = edgeTo[v].other(v)) { bottle = Math.min(bottle, edgeTo[v].residualCapacityTo(v)); } // augment flow for (int v = t; v != s; v = edgeTo[v].other(v)) { edgeTo[v].addResidualFlowTo(v, bottle); } value += bottle; } // check optimality conditions assert check(G, s, t); }
// is there an augmenting path? // if so, upon termination edgeTo[] will contain a parent-link representation of such a path // this implementation finds a shortest augmenting path (fewest number of edges), // which performs well both in theory and in practice private boolean hasAugmentingPath(FlowNetwork G, int s, int t) { edgeTo = new FlowEdge[G.V()]; marked = new boolean[G.V()]; // breadth-first search Queue<Integer> queue = new Queue<Integer>(); queue.enqueue(s); marked[s] = true; while (!queue.isEmpty() && !marked[t]) { int v = queue.dequeue(); for (FlowEdge e : G.adj(v)) { int w = e.other(v); // if residual capacity from v to w if (e.residualCapacityTo(w) > 0) { if (!marked[w]) { edgeTo[w] = e; marked[w] = true; queue.enqueue(w); } } } } // is there an augmenting path? return marked[t]; }
Read full article from Ford-Fulkerson Algorithm for Maximum Flow Problem - GeeksforGeeks
