Network Flow Problems

Previous
Quiz
Next

Network flow problems are all about figuring out how stuff (data, resources, whatever) can move from a start point (source) to an endpoint (sink) in a network. Its like optimizing a traffic system, a data network, or even supply chains. In this article, well talk about what network flow problems are and how we handle them using data structures.

What are Network Flow Problems?

So, network flow problems deal with this idea of moving flow from one point to another. We have a network of nodes connected by edges, and each edge has a capacity. The capacity shows how much can actually flow through that edge, and the flow is the amount thats actually moving. The rule is that the flow on an edge can't be more than its capacity.

The whole point of these problems is to move as much "stuff" (data, goods, etc.) as we can from the source to the sink. But we have to respect the limits (capacities) of each edge along the way. The goal is to maximize the flow without breaking any edges.

Network Flow Problem Example

Imagine we have a simple network with a source node and a sink node. The nodes are connected by edges with certain capacities. We apply the right algorithm to find out how much flow can go from source to sink while respecting the edge capacities. We want to push as much flow through the network as possible.

Network Flow Problem Algorithms

To solve these problems, we use a few different algorithms. They help us figure out the max flow in the network. Heres a quick rundown:

  • Ford-Fulkerson Algorithm: This ones pretty basic. It keeps finding augmenting paths and pushing flow through them until it cant anymore.
  • Edmonds-Karp Algorithm: Its a bit faster than Ford-Fulkerson, using BFS to find the shortest augmenting path.
  • Dinic's Algorithm: A bit more advanced and faster in some cases. It uses a layered approach.
  • Push-Relabel Algorithm: Works by pushing flow around efficiently and adjusting the flow with labels.

They all work by finding these paths called augmenting pathspaths where we can add more flow. Its like a race to find the best path to push more stuff through until theres no room left to move more.

Example of Network Flow Problems

You are given a directed graph representing a network with capacities on edges. The graph has a source node (s) and a sink node (t). The goal is to determine the maximum flow that can be sent from source to sink while respecting the capacity constraints.


    (0)
    /   \
  10     15
  /       \
(1)---5---(3)  
  \       /
   10    10
    \   /
     (4)
       \
        10
         \
         (5)

In the above graph, the numbers on the edges represent the capacities. The maximum flow from source (0) to sink (5) is 20.

Network Flow Problem Code

Here's code for above problem in C, C++, Java, and Python:

C C++ Java Python 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>  

#define MAX_VERTICES 6

#define min(a, b) ((a) < (b) ? (a) : (b))

int bfs(int rGraph[MAX_VERTICES][MAX_VERTICES], int s, int t, int parent[MAX_VERTICES]) {
   int visited[MAX_VERTICES];
   memset(visited, 0, sizeof(visited));
   visited[s] = 1;
   int queue[MAX_VERTICES];
   int front = 0, rear = 0;
   queue[rear++] = s;
   parent[s] = -1;

   while (front != rear) {
      int u = queue[front++];
      for (int v = 0; v < MAX_VERTICES; v++) {
         if (!visited[v] && rGraph[u][v] > 0) {
            queue[rear++] = v;
            parent[v] = u;
            visited[v] = 1;
            if (v == t) {
               return 1;  
            }
         }
      }
   }
   return 0;  // No more augmenting path
}

int ford_fulkerson(int graph[MAX_VERTICES][MAX_VERTICES], int s, int t) {
   int u, v;
   int rGraph[MAX_VERTICES][MAX_VERTICES];

   for (u = 0; u < MAX_VERTICES; u++)
      for (v = 0; v < MAX_VERTICES; v++)
         rGraph[u][v] = graph[u][v];

   int parent[MAX_VERTICES];
   int max_flow = 0;

   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]);
      }

      for (v = t; v != s; v = parent[v]) {
         u = parent[v];
         rGraph[u][v] -= path_flow;
         rGraph[v][u] += path_flow;
      }

      max_flow += path_flow;
   }
   return max_flow;
}

int main() {
   int adj[MAX_VERTICES][MAX_VERTICES] = {
      {0, 10, 15, 0, 0, 0},
      {0, 0, 0, 5, 10, 0},
      {0, 0, 0, 0, 0, 10},
      {0, 0, 0, 0, 0, 5},
      {0, 0, 0, 0, 0, 10},
      {0, 0, 0, 0, 0, 0}
   };

   int source = 0;
   int sink = 5;
   int max_flow = ford_fulkerson(adj, source, sink);

   printf("Maximum flow from source to sink is %d\n", max_flow);
   return 0;
}

Output

Following is the output of the above code:

Maximum flow from source to sink is 20

#include <iostream>
#include <climits>
#include <queue>
#include <string.h>
using namespace std;

#define MAX_VERTICES 6

int adj[MAX_VERTICES][MAX_VERTICES] = {
   {0, 10, 15, 0, 0, 0},
   {0, 0, 0, 5, 10, 0},
   {0, 0, 0, 0, 0, 10},
   {0, 0, 0, 0, 0, 5},
   {0, 0, 0, 0, 0, 10},
   {0, 0, 0, 0, 0, 0}
};

bool bfs(int rGraph[MAX_VERTICES][MAX_VERTICES], int s, int t, int parent[MAX_VERTICES]) {
   bool visited[MAX_VERTICES];
   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 < MAX_VERTICES; v++) {
         if (!visited[v] && rGraph[u][v] > 0) {
            if (v == t) {
               parent[v] = u;
               return true;
            }
            q.push(v);
            parent[v] = u;
            visited[v] = true;
         }
      }
   }
   return false;
}

int ford_fulkerson(int graph[MAX_VERTICES][MAX_VERTICES], int s, int t) {
   int u, v;
   int rGraph[MAX_VERTICES][MAX_VERTICES];
   for (u = 0; u < MAX_VERTICES; u++)
      for (v = 0; v < MAX_VERTICES; v++)
         rGraph[u][v] = graph[u][v];
   int parent[MAX_VERTICES];
   int max_flow = 0;
   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]);
      }
      for (v = t; v != s; v = parent[v]) {
         u = parent[v];
         rGraph[u][v] -= path_flow;
         rGraph[v][u] += path_flow;
      }
      max_flow += path_flow;
   }
   return max_flow;
}


int main() {
   int source = 0;
   int sink = 5;
   int max_flow = ford_fulkerson(adj, source, sink);
   cout << "Maximum flow from source to sink is " << max_flow << endl;
   return 0;
}

Output

Following is the output of the above code:

Maximum flow from source to sink is 20

import java.util.*;
public class NetworkFlow {
   static final int MAX_VERTICES = 6;
   static int adj[][] = {
      {0, 10, 15, 0, 0, 0},
      {0, 0, 0, 5, 10, 0},
      {0, 0, 0, 0, 0, 10},
      {0, 0, 0, 0, 0, 5},
      {0, 0, 0, 0, 0, 10},
      {0, 0, 0, 0, 0, 0}
   };

   static int fordFulkerson(int graph[][], int s, int t) {
      int u, v;
      int rGraph[][] = new int[MAX_VERTICES][MAX_VERTICES];
      for (u = 0; u < MAX_VERTICES; u++)
         for (v = 0; v < MAX_VERTICES; v++)
            rGraph[u][v] = graph[u][v];
      int parent[] = new int[MAX_VERTICES];
      int max_flow = 0;
      while (bfs(rGraph, s, t, parent)) {
         int path_flow = Integer.MAX_VALUE;
         for (v = t; v != s; v = parent[v]) {
            u = parent[v];
            path_flow = Math.min(path_flow, rGraph[u][v]);
         }
         for (v = t; v != s; v = parent[v]) {
            u = parent[v];
            rGraph[u][v] -= path_flow;
            rGraph[v][u] += path_flow;
         }
         max_flow += path_flow;
      }
      return max_flow;
   }

   static boolean bfs(int rGraph[][], int s, int t, int parent[]) {
      boolean visited[] = new boolean[MAX_VERTICES];
      for (int i = 0; i < MAX_VERTICES; ++i)
         visited[i] = false;
      Queue<Integer> q = new LinkedList<Integer>();
      q.add(s);
      visited[s] = true;
      parent[s] = -1;
      while (!q.isEmpty()) {
         int u = q.poll();
         for (int v = 0; v < MAX_VERTICES; v++) {
            if (!visited[v] && rGraph[u][v] > 0) {
               if (v == t) {
                  parent[v] = u;
                  return true;
               }
               q.add(v);
               parent[v] = u;
               visited[v] = true;
            }
         }
        }
        return false;
    }

    public static void main(String[] args) {
        int source = 0;
        int sink = 5;
        int max_flow = fordFulkerson(adj, source, sink);
        System.out.println("Maximum flow from source to sink is " + max_flow);
    }
}

Output

Following is the output of the above code:

Maximum flow from source to sink is 20

MAX_VERTICES = 6

adj = [
   [0, 10, 15, 0, 0, 0],
   [0, 0, 0, 5, 10, 0],
   [0, 0, 0, 0, 0, 10],
   [0, 0, 0, 0, 0, 5],
   [0, 0, 0, 0, 0, 10],
   [0, 0, 0, 0, 0, 0]
]

def bfs(rGraph, s, t, parent):
   visited = [False] * MAX_VERTICES
   queue = []
   queue.append(s)
   visited[s] = True
   parent[s] = -1
   while queue:
      u = queue.pop(0)
      for v in range(MAX_VERTICES):
         if not visited[v] and rGraph[u][v] > 0:
            if v == t:
               parent[v] = u
               return True
            queue.append(v)
            parent[v] = u
            visited[v] = True
   return False

def ford_fulkerson(graph, s, t):
    rGraph = [[0] * MAX_VERTICES for _ in range(MAX_VERTICES)]
    for u in range(MAX_VERTICES):
        for v in range(MAX_VERTICES):
            rGraph[u][v] = graph[u][v]
    parent = [-1] * MAX_VERTICES
    max_flow = 0
    while bfs(rGraph, s, t, parent):
        path_flow = float('inf')
        v = t
        while v != s:
            u = parent[v]
            path_flow = min(path_flow, rGraph[u][v])
            v = parent[v]
        v = t
        while v != s:
            u = parent[v]
            rGraph[u][v] -= path_flow
            rGraph[v][u] += path_flow
            v = parent[v]
        max_flow += path_flow
    return max_flow

source = 0
sink = 5
max_flow = ford_fulkerson(adj, source, sink)
print("Maximum flow from source to sink is", max_flow)

Output

Following is the output of the above code:

Maximum flow from source to sink is 20

Applications of Network Flow Problems

These problems arent just theoretical. They show up everywhere! Here are some areas where we use them:

  • Transportation Networks: Traffic, buses, trainsanything that moves people or goods. We use network flow problems to manage how stuff moves around in these systems.
  • Communication Networks: Data, video calls, web trafficall of that depends on network flow. By solving these problems, we can figure out how to route the data in the most efficient way.
  • Supply Chains: Getting goods and materials from one place to another is a classic flow problem. We use these algorithms to optimize how resources move through a supply chain.
  • Fluid Systems: Think water pipes or oil pipelines. We use network flow problems to manage the flow of liquids or gases in these systems.

By solving network flow problems, engineers and researchers can tweak and improve systems where resources flow from one place to another. Whether its traffic, data, or anything in between, these problems help optimize flow in the best way possible.

Conclusion

In this tutorial, we talked about network flow problems and how they help us figure out the best way to move stuff from one place to another. We use algorithms to find the maximum flow in a network, respecting the capacities of each edge. These problems show up in all sorts of systems, from transportation to communication to supply chains. By solving network flow problems, we can optimize how resources move around in these systems, making them more efficient and effective.

Print Page
Previous
Next
Advertisements