FORD FULKERSON

#include <iostream>

#include <climits>

#include <cstring>

#include <queue>

using namespace std;

#define V 4

// Using BFS as a searching algorithm

bool bfs(int rGraph[V][V], int s, int t, int parent[]) {

  // Initialize the visited array to false

  bool visited[V];

  memset(visited, 0, sizeof(visited));

  // Create a queue and push the source vertex into it

  queue<int> q;

  q.push(s);

  visited[s] = true;

  parent[s] = -1;

  // Loop until the queue is empty

  while (!q.empty()) {

    // Get the front vertex from the queue

    int u = q.front();

    q.pop();

    // Loop through all the adjacent vertices of the current vertex

    for (int v = 0; v < V; v++) {

      // If the adjacent vertex is not visited and there is an edge between the current vertex and the adjacent vertex

      if (visited[v] == false && rGraph[u][v] > 0) {

        // Push the adjacent vertex into the queue

        q.push(v);

        // Set the parent of the adjacent vertex to the current vertex

        parent[v] = u;

        // Mark the adjacent vertex as visited

        visited[v] = true;

      }

    }

  }

  // Return true if there is a path from source to sink in the residual graph

  return (visited[t] == true);

}

// Applying fordfulkerson algorithm

int fordFulkerson(int graph[V][V], int s, int t) {

  int u, v;

  // Create a residual graph

  int rGraph[V][V];

  for (u = 0; u < V; u++)

    for (v = 0; v < V; v++)

      rGraph[u][v] = graph[u][v];

  // Initialize the parent array and the maximum flow

  int parent[V];

  int max_flow = 0;

  // Loop until there is no augmenting path from source to sink in the residual graph

  while (bfs(rGraph, s, t, parent)) {

    // Initialize the path flow to infinity

    int path_flow = INT_MAX;

    // Find the minimum capacity along the augmenting path

    for (v = t; v != s; v = parent[v]) {

      u = parent[v];

      path_flow = min(path_flow, rGraph[u][v]);

    }

    // Update the residual graph by subtracting the path flow from the capacity of the edges in the augmenting path

    for (v = t; v != s; v = parent[v]) {

      u = parent[v];

      rGraph[u][v] -= path_flow;

      rGraph[v][u] += path_flow; // Reverse edge

    }

    // Add the path flow to the maximum flow

    max_flow += path_flow;

  }

  // Return the maximum flow

  return max_flow;

}

int main() {

  int graph[V][V];

  // Input the adjacency matrix

  cout << "Enter the adjacency matrix:" << endl;

  for (int i = 0; i < V; ++i) {

    for (int j = 0; j < V; ++j) {

      cin >> graph[i][j];

    }

  }

  // Print the maximum flow from source to sink

  cout << "Max Flow: " << fordFulkerson(graph, 0, V-1) << endl;

  return 0;

}