Flow Networks

Flow networks are a special kind of graph that are used for representing the flow of data or resources from one point to another. They are used in a variety of applications, including transportation networks, communication networks, and computer networks. In this chapter, we will discuss the basic concepts of flow networks and how they are used in data structures.

What is a Flow Network?

A flow network is a directed graph in which each edge has a capacity and a flow. The capacity of an edge represents the maximum amount of flow that can pass through it, while the flow of an edge represents the actual amount of flow passing through it. The flow of an edge must be less than or equal to its capacity.

Flow networks are used to model the flow of data or resources from a source to a sink. The source is the starting point of the flow, while the sink is the ending point. The goal of a flow network is to maximize the flow from the source to the sink while respecting the capacities of the edges.

Flow Network Example

Let's consider a simple flow network with a source, a sink, and some intermediate nodes. The edges of the flow network have capacities and flows as shown below:

        10(5)
    A --------> B
    |           |
   5(3)        8(6)
    |           |
    v           v
    C --------> D
        7(4)    | 6(4)
                v
                E
                | 4(4)
                v
                F

The flow network represents the flow of data from the source A to the sink F. The goal is to maximize the flow from A to F while respecting the capacities of the edges. In this example, the maximum flow from A to F is 10, which is achieved by sending 5 units of flow along edge AB, 3 units along edge AC, 6 units along edge BD, 4 units along edge CE, and 4 units along edge EF.

• Edge AB: Capacity = 10, Flow = 5
• Edge AC: Capacity = 5, Flow = 3
• Edge BD: Capacity = 8, Flow = 6
• Edge CE: Capacity = 7, Flow = 4
• Edge DE: Capacity = 6, Flow = 4
• Edge EF: Capacity = 4, Flow = 4

Flow Network Algorithms

There are several algorithms that can be used to find the maximum flow in a flow network. Some of the most common algorithms include:

1. Ford-Fulkerson Algorithm
2. Edmonds-Karp Algorithm
3. Dinic's Algorithm
4. Push-Relabel Algorithm

These algorithms use different techniques to find the maximum flow in a flow network. They are based on the concept of augmenting paths, which are paths from the source to the sink that can carry additional flow. By finding augmenting paths and increasing the flow along them.

Ford-Fulkerson Algorithm to Find Maximum Flow

Let's take a look at the Ford-Fulkerson algorithm, which is one of the most popular algorithms for finding the maximum flow in a flow network. The algorithm works by finding augmenting paths from the source to the sink and increasing the flow along these paths.

The steps of the Ford-Fulkerson algorithm are as follows:

1. Initialize the flow of each edge to 0.
2. While there is an augmenting path from the source to the sink:
    a. Find an augmenting path using a depth-first search or breadth-first search.
    b. Determine the maximum flow that can be sent along the augmenting path.
    c. Increase the flow along the augmenting path by the maximum flow.
3. Return the maximum flow.

By following these steps, the Ford-Fulkerson algorithm can find the maximum flow in a flow network. The algorithm terminates when there are no more augmenting paths from the source to the sink.

Code for Ford-Fulkerson Algorithm

Here's an example code snippet for the Ford-Fulkerson algorithm in C, C++, Java, and Python:

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#include <string.h>


#define V 6

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

   int queue[V];
   int front = 0, rear = 0;
   queue[rear++] = s;
   visited[s] = true;
   parent[s] = -1;

   while (front != rear) {
      int u = queue[front++];
      for (int v = 0; v < V; v++) {
         if (!visited[v] && rGraph[u][v] > 0) {
            queue[rear++] = v;
            parent[v] = u;
            visited[v] = true;
         }
      }
   }

   return visited[t];
}

int fordFulkerson(int graph[V][V], int s, int t) {
   int u, v;
   int rGraph[V][V];
   for (u = 0; u < V; u++)
      for (v = 0; v < V; v++)
         rGraph[u][v] = graph[u][v];

   int parent[V];
   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 = path_flow < rGraph[u][v] ? 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 graph[V][V] = {
      {0, 10, 5, 0, 0, 0},
      {0, 0, 0, 8, 0, 0},
      {0, 0, 0, 0, 7, 0},
      {0, 0, 0, 0, 6, 6},
      {0, 0, 0, 0, 0, 4},
      {0, 0, 0, 0, 0, 0}
   };

   printf("The maximum possible flow is %d\n", fordFulkerson(graph, 0, 5));

   return 0;
}

The maximum possible flow is 10

#include <iostream>
#include <limits.h>
#include <queue>
#include <string.h>

#define V 6

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

   std::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 < V; v++) {
         if (!visited[v] && rGraph[u][v] > 0) {
            q.push(v);
            parent[v] = u;
            visited[v] = true;
         }
      }
   }

   return visited[t];
}

int fordFulkerson(int graph[V][V], int s, int t) {
   int u, v;
   int rGraph[V][V];
   for (u = 0; u < V; u++)
      for (v = 0; v < V; v++)
         rGraph[u][v] = graph[u][v];

   int parent[V];
   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 = std::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 graph[V][V] = {
      {0, 10, 5, 0, 0, 0},
      {0, 0, 0, 8, 0, 0},
      {0, 0, 0, 0, 7, 0},
      {0, 0, 0, 0, 6, 6},
      {0, 0, 0, 0, 0, 4},
      {0, 0, 0, 0, 0, 0}
   };

   std::cout << "The maximum possible flow is " << fordFulkerson(graph, 0, 5) << std::endl;

   return 0;
}

The maximum possible flow is 10

import java.util.LinkedList;
import java.util.Queue;

public class FordFulkerson {
   static final int V = 6;

   boolean bfs(int rGraph[][], int s, int t, int parent[]) {
      boolean visited[] = new boolean[V];
      Queue<Integer> q = new LinkedList<>();
      q.add(s);
      visited[s] = true;
      parent[s] = -1;

      while (!q.isEmpty()) {
         int u = q.poll();
         for (int v = 0; v < V; v++) {
            if (!visited[v] && rGraph[u][v] > 0) {
               q.add(v);
               parent[v] = u;
               visited[v] = true;
            }
         }
      }

      return visited[t];
   }

   int fordFulkerson(int graph[][], int s, int t) {
      int u, v;
      int rGraph[][] = new int[V][V];
      for (u = 0; u < V; u++)
         for (v = 0; v < V; v++)
            rGraph[u][v] = graph[u][v];

      int parent[] = new int[V];
      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;
            }

            public static void main(String[] args) {
            int graph[][] = {
            {0, 10, 5, 0, 0, 0},
            {0, 0, 0, 8, 0, 0},
            {0, 0, 0, 0, 7, 0},
            {0, 0, 0, 0, 6, 6},
            {0, 0, 0, 0, 0, 4},
            {0, 0, 0, 0, 0, 0}
            };

            FordFulkerson m = new FordFulkerson();

            System.out.println("The maximum possible flow is " + m.fordFulkerson(graph, 0, 5));
            }
            }

The maximum possible flow is 10

V = 6

def bfs(rGraph, s, t, parent):
   visited = [False] * V
   queue = []
   queue.append(s)
   visited[s] = True
   parent[s] = -1

   while queue:
      u = queue.pop(0)
      for v in range(V):
         if not visited[v] and rGraph[u][v] > 0:
            queue.append(v)
            parent[v] = u
            visited[v] = True

   return visited[t]

def fordFulkerson(graph, s, t):
    rGraph = [graph[i][:] for i in range(V)]
    parent = [-1] * V
    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

graph = [
    [0, 10, 5, 0, 0, 0],
    [0, 0, 0, 8, 0, 0],
    [0, 0, 0, 0, 7, 0],
    [0, 0, 0, 0, 6, 6],
    [0, 0, 0, 0, 0, 4],
    [0, 0, 0, 0, 0, 0]
]

print("The maximum possible flow is", fordFulkerson(graph, 0, 5))

The maximum possible flow is 10

Applications of Flow Networks

Flow networks are used in a variety of applications, including:

• Transportation networks: Flow networks can be used to model the flow of traffic on roads, railways, and other transportation systems.
• Communication networks: Flow networks can be used to model the flow of data in computer networks, telecommunication networks, and other communication systems.
• Supply chain networks: Flow networks can be used to model the flow of goods, materials, and resources in supply chain networks.
• Fluid networks: Flow networks can be used to model the flow of fluids in pipelines, water distribution systems, and other fluid systems.

By using flow networks, engineers and researchers can analyze and optimize the flow of data or resources in a wide range of applications. Flow networks are a powerful tool for modeling complex systems and finding efficient solutions to flow-related problems.

Conclusion

In this chapter, we discussed the concept of flow networks and how they are used in data structures. We also explored the Ford-Fulkerson algorithm, which is one of the most popular algorithms for finding the maximum flow in a flow network. By understanding flow networks and the algorithms used to analyze them, you can solve a wide range of flow-related problems in various domains.