ford fulkerson

#include <limits.h>

#include <iostream>

#include <queue>

using namespace std;

#define V 4

#define WHITE 0

#define GRAY 1

#define BLACK 2

// Using BFS as a searching algorithm

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

    int color[V];

    int distance[V];

   

    // Initialize color and distance arrays

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

        color[i] = WHITE;

        distance[i] = INT_MAX;

        parent[i] = -1;

    }

    queue<int> q;

    q.push(s);

    color[s] = GRAY;

    distance[s] = 0;

    while (!q.empty()) {

        int u = q.front();

        q.pop();

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

            if (color[v] == WHITE && rGraph[u][v] > 0) {

                q.push(v);

                color[v] = GRAY;

                distance[v] = distance[u] + 1;

                parent[v] = u;

            }

        }

        color[u] = BLACK;

    }

    return (color[t] == BLACK);

}

// Applying Ford-Fulkerson algorithm

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

    int u, v;

    int rGraph[V][V]; // Residual graph

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

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

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

    int parent[V]; // Stores the path

    int max_flow = 0; // There is no flow initially

    // Augment the flow while there is a path from source to sink

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

        int path_flow = INT_MAX;

        // Find the maximum flow through the path found.

        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;

}

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;

}