Ford-Fulkerson Method

#include <algorithm>
#include <climits>
#include <iostream>
#include <stdexcept>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

using Capacity = long long;
using Edge = tuple<string, string, Capacity>;
using Matrix = unordered_map<string, unordered_map<string, Capacity>>;

struct Result {
    Capacity value;
    unordered_set<string> sourceSide;
};

Result fordFulkerson(const vector<Edge>& edges,
                     const string& source, const string& sink) {
    if (source == sink) throw invalid_argument("source and sink must differ");

    Matrix residual;
    unordered_map<string, vector<string>> adjacency;
    auto link = [&](const string& u, const string& v) {
        auto& neighbors = adjacency[u];
        if (find(neighbors.begin(), neighbors.end(), v) == neighbors.end())
            neighbors.push_back(v);
    };

    for (const auto& [u, v, capacity] : edges) {
        if (capacity < 0) throw invalid_argument("negative capacity");
        residual[u][v] += capacity;  // parallel edges are aggregated
        residual[v][u] += 0;
        link(u, v);
        link(v, u);
    }
    adjacency[source];
    adjacency[sink];

    Capacity value = 0;
    while (true) {
        unordered_map<string, string> parent{{source, source}};
        vector<string> stack{source};

        while (!stack.empty() && !parent.count(sink)) {
            string u = stack.back();
            stack.pop_back();
            for (const string& v : adjacency[u]) {
                if (residual[u][v] > 0 && !parent.count(v)) {
                    parent[v] = u;
                    stack.push_back(v);
                }
            }
        }
        if (!parent.count(sink)) break;

        Capacity delta = LLONG_MAX;
        for (string v = sink; v != source; v = parent.at(v))
            delta = min(delta, residual[parent.at(v)][v]);

        for (string v = sink; v != source; v = parent.at(v)) {
            const string& u = parent.at(v);
            residual[u][v] -= delta;
            residual[v][u] += delta;
        }
        value += delta;
    }

    unordered_set<string> sourceSide{source};
    vector<string> stack{source};
    while (!stack.empty()) {
        string u = stack.back();
        stack.pop_back();
        for (const string& v : adjacency[u]) {
            if (residual[u][v] > 0 && !sourceSide.count(v)) {
                sourceSide.insert(v);
                stack.push_back(v);
            }
        }
    }
    return {value, sourceSide};
}

int main() {
    vector<Edge> edges = {
        {"S", "A", 3}, {"S", "B", 2}, {"A", "T", 2},
        {"B", "T", 3}, {"A", "B", 1}
    };
    Result result = fordFulkerson(edges, "S", "T");
    cout << "Max flow: " << result.value << " Cut source side:";
    for (const string& v : result.sourceSide) cout << ' ' << v;
    cout << '\n';
}

import java.util.*;

class FordFulkerson {
    record Edge(String from, String to, long capacity) {}
    record Result(long value, Set<String> sourceSide) {}

    static Result maxFlow(List<Edge> edges, String source, String sink) {
        if (source.equals(sink))
            throw new IllegalArgumentException("source and sink must differ");

        Map<String, Map<String, Long>> residual = new LinkedHashMap<>();
        Map<String, Set<String>> adjacency = new LinkedHashMap<>();

        for (Edge edge : edges) {
            if (edge.capacity() < 0)
                throw new IllegalArgumentException("negative capacity");
            residual.computeIfAbsent(edge.from(), k -> new LinkedHashMap<>())
                    .merge(edge.to(), edge.capacity(), Long::sum);
            residual.computeIfAbsent(edge.to(), k -> new LinkedHashMap<>())
                    .putIfAbsent(edge.from(), 0L);
            adjacency.computeIfAbsent(edge.from(), k -> new LinkedHashSet<>())
                    .add(edge.to());
            adjacency.computeIfAbsent(edge.to(), k -> new LinkedHashSet<>())
                    .add(edge.from());
        }
        adjacency.computeIfAbsent(source, k -> new LinkedHashSet<>());
        adjacency.computeIfAbsent(sink, k -> new LinkedHashSet<>());

        long value = 0;
        while (true) {
            Map<String, String> parent = new HashMap<>();
            parent.put(source, source);
            Deque<String> stack = new ArrayDeque<>();
            stack.push(source);

            while (!stack.isEmpty() && !parent.containsKey(sink)) {
                String u = stack.pop();
                for (String v : adjacency.getOrDefault(u, Set.of())) {
                    long spare = residual.getOrDefault(u, Map.of()).getOrDefault(v, 0L);
                    if (spare > 0 && !parent.containsKey(v)) {
                        parent.put(v, u);
                        stack.push(v);
                    }
                }
            }
            if (!parent.containsKey(sink)) break;

            long delta = Long.MAX_VALUE;
            for (String v = sink; !v.equals(source); v = parent.get(v)) {
                String u = parent.get(v);
                delta = Math.min(delta, residual.get(u).get(v));
            }
            for (String v = sink; !v.equals(source); v = parent.get(v)) {
                String u = parent.get(v);
                residual.get(u).merge(v, -delta, Long::sum);
                residual.get(v).merge(u, delta, Long::sum);
            }
            value += delta;
        }

        Set<String> sourceSide = new LinkedHashSet<>();
        Deque<String> stack = new ArrayDeque<>();
        sourceSide.add(source);
        stack.push(source);
        while (!stack.isEmpty()) {
            String u = stack.pop();
            for (String v : adjacency.getOrDefault(u, Set.of())) {
                long spare = residual.getOrDefault(u, Map.of()).getOrDefault(v, 0L);
                if (spare > 0 && sourceSide.add(v)) stack.push(v);
            }
        }
        return new Result(value, sourceSide);
    }

    public static void main(String[] args) {
        List<Edge> edges = List.of(
            new Edge("S", "A", 3), new Edge("S", "B", 2),
            new Edge("A", "T", 2), new Edge("B", "T", 3),
            new Edge("A", "B", 1)
        );
        Result result = maxFlow(edges, "S", "T");
        System.out.println("Max flow: " + result.value()
                           + " Cut source side: " + result.sourceSide());
        // Max flow: 5 Cut source side: [S]
    }
}