Skip to main content

Ford-Fulkerson Method

max flows, min cuts, and the Ford-Fulkerson method

max flows, min cuts, and the Ford-Fulkerson method

Min cuts and max flows

Set up

  • A directed graph G=(V,E)G = (V, E), and edge capacities c(u,v)c(u, v)

  • A source ss and a sink tt, ss has only outgoing edges, tt has only incoming edges

An s-t cut is a partition of VV into SS and T=V−ST = V - S such that s∈Ss \in S and t∈Tt \in T.

An edge crosses the cut if it goes from s's side to t's side.

The cost (or capacity) of the cut is the sum of the capacities of the edges that cross the cut.

A minimum s-t cut is an s-t cut whose cost is minimum over all s-t cuts.

Flows

  • In addition to a capacity, each edge has a flow

  • the flow on an edge can't exceed the capacity of the edge

  • At each vertex, the incoming flows must equal the outgoing flows, except at ss and tt

A maximum flow is a flow of maximum value.

Theorem: Max-flow min-cut theorem

  • The value of the maximum flow is equal to the capacity of the minimum cut.

The Ford-Fulkerson algorithm

  • Outline

    • We wiil be updating a flow f
    • start with f being the zero flow
    • We will maintain a "residual graph" GfG_f that indicates how we can change f to get a flow with larger value
    • A path from s to t in GfG_f will give us a way to increase the flow value
    • we will continue until there is no path from s to t in GfG_f

Tool: Residual networks

  • Given a flow ff and graph GG, the forward edge has weight[capacity]-[flow], the backward edge has weight[flow]. (Forward edges are the amount of capacity left, backward edges are the amount of flow that can be removed)

Residual networks tell us how to improve the flow.

  • Definition: A path from s to t in the residual network is called an augmenting path.

  • Claim: If there is an augmenting path, then f is not a maximum flow.

    • Easy case: all edges on the path are forward edges, just increase the flow on all the edges by the same amount, then update the residual network.

    • Harder case: some edges on the path are backward edges, we need to decrease the flow on those edges. Decrease the flow on all the backward edges by the same amount, then update the residual network.

    • increaseFlow(path P in GfG_f, flow f): -x = min of the capacities of the edges on P

      • for (u,v) in P:

        • if(u,v) is a forward edge:

          • f(u,v) += x

        • else:

          • f(v,u) -= x

      • return f

Ford-Fulkerson algorithm

    Ford-Fulkerson(G, s, t):
        f = 0
        G_f = G
        while t is reachable from s in G_f:
            P = any s-t path in G_f
            f = increaseFlow(P, f)
            G_f = residual network of f
        return f

Edmonds-Karp algorithm

  • The Ford-Fulkerson algorithm is correct, but it can be slow

  • Edmonds-Karp algorithm: always choose the shortest augmenting path in the residual network using BFS

  • The running time is O(VE2)O(VE^2)

Applications

Maximum bipartite matching

  • A bipartite graph is a graph whose vertices can be divided into two disjoint sets LL and RR such that every edge connects a vertex in LL to a vertex in RR.

  • A matching is a subset of edges in which no vertex appears more than once.

  • A maximum matching is a matching of maximum size.

Assignment problem

One set X, Another set Y, each x in X can participate in c(x) matches, each y in Y can participate in c(y) matches, each pair (x,y) can only be matched c(x,y) times.

Find a maximum matching.

code template

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

// the number of vertices
const int N = 20;

//reading the graph
void read_graph(int graph[N][N], int n)
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> graph[i][j];
}

// BFS
bool bfs(int rGraph[N][N], int s, int t, int parent[]){
    bool visited[N];
    memset(visited, 0, sizeof(visited));

    queue<int> q;
    q.push(s);
    visited[s] = true;
    parent[s] = -1;

    while (!q.empty()){
        int u = q.front();
        q.pop();

        for (int v = 0; v < N; v++){
            if (visited[v] == false && rGraph[u][v] > 0){
                q.push(v);
                parent[v] = u;
                visited[v] = true;
            }
        }
    }
    return (visited[t] == true);
}

int fordfulkerson(int graph[N][N], int s, int t){
    int u, v;
    int rGraph[N][N]; // residual graph

    // initialize residual graph
    for (u = 0; u < N; u++)
        for (v = 0; v < N; v++)
            rGraph[u][v] = graph[u][v];

    int parent[N]; // store the path
    int max_flow = 0; // max flow

    // BFS
    while (bfs(rGraph, s, t, parent)){
        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 max_flow;
}

Comments

Post a Comment

Popular posts from this blog

Tries

Tries Tries Tries and Patricia Tries Motivation: The autocomplete feature in a text editor. We have a dictionary of words, and we want to find all the words that start with a given prefix. The data structure we use to store the dictionary is called a trie. Each edge is labeled with a character. Some nodes are marked as terminal nodes. By convention, children of a node are ordered alphabetically. A preordering traversal of the trie yields the words in the dictionary in alphabetical order. The total length of our text strings is m and the length of our pattern string is n . Time to build the trie: O(m) Time to search for a pattern: O(n) How long does it take to find all the words that start with a given prefix? The $ symbol is called the sentinel or marker, add this to the end of each word. It is used to mark the end of a word, it precedes all other characters in the alphabet....
Post a Comment
Read more

Recap on BFS, DFS and Strongly Connected Components

graph graph DFS topological sort considering the dependencies between tasks, we can use topological sort to find the order of tasks. def topological_sort ( graph ): visited = set () stack = [] for node in graph: if node not in visited: dfs(graph, node, visited, stack) return stack[::- 1 ] def dfs ( graph, node, visited, stack ): visited.add(node) for neighbor in graph[node]: if neighbor not in visited: dfs(graph, neighbor, visited, stack) stack.append(node) if A -> B then B.finishtime < A.finishtime, that's why we need to reverse the stack. Topological Sorting on a DAG do DFS on the graph when a node is finished, insert it into the front of a linked list Another use of DFS is in-order traversal of a binary tree . BFS BFS is used to find the shortest path in an unweighted graph . we can...
Post a Comment
Read more

Balanced Trees

Balanced Trees Balanced Trees Balanced search trees are among the most useful and versatile data structures. Many programming languages include balanced search trees in their standard libraries. e.g. C++: std::map , Java: TreeMap , Python: dict , etc. Many advanced data structures are layered on top of balanced search trees.. A quick BST recap A binary search tree is a binary tree where each node has a key and a value, and the following properties hold: Each node in the BST stores a key, and optinally, some information associated with the key. The keys in the left subtree are less than the key in its parent node, and the keys in the right subtree are greater than the key in its parent node. The height of a BST is the number of nodes on the longest path from the root to a leaf. A tree with one node has height 0, A tree with no nodes has height -1. Deleting from a BST Deleting a n...
Post a Comment
Read more