Implementation of Edmond-Karps and Ford-Fulkerson algorithms for modeling a primary P2P network

main.py

from collections import deque

"""
    Both algorithms find the maximum flow in a network
    The Ford Fulkerson method's running time can vary significantly depending on the chosen augmenting paths
    which may lead to exponential performance in the worst case
    In contrast, Edmonds Karp always selects the shortest augmenting path (using BFS)
    @author Parsa Amini
"""

# Edge structure for residual graph
class Edge:
    def __init__(self, to, capacity, rev):
        """
        Parameters
        ----------
        to: Destination node
        capacity: Remaining capacity
        rev: Index of reverse edge
        """
        self.to = to              
        self.capacity = capacity  
        self.rev = rev            


class MaxFlow:
    def __init__(self, n: float, names: list):
        """
        Parameters
        ----------
        n: number of vertices
        names: Node name mapping (index -> name) 
        """
        self.graph = [[] for _ in range(n)]
        self.names = names

    # Add forward and backward (residual) edges
    def add_edge(self, u, v, capacity):
        forward = Edge(v, capacity, len(self.graph[v]))
        backward = Edge(u, 0, len(self.graph[u]))
        self.graph[u].append(forward)
        self.graph[v].append(backward)

    # ---------------- Edmonds-Karp (BFS approach) ----------------
    def bfs(self, s, t, parent):
        queue = deque([s])
        parent[s] = (-1, -1)

        while queue:
            u = queue.popleft()
            for i, edge in enumerate(self.graph[u]):
                if edge.capacity > 0 and parent[edge.to] is None:
                    parent[edge.to] = (u, i)
                    if edge.to == t:
                        return True
                    queue.append(edge.to)
        return False

    def edmonds_karp(self, s, t):
        flow = 0
        iteration = 1

        while True:
            parent = [None] * len(self.graph)
            if not self.bfs(s, t, parent):
                break

            # Find bottleneck and path
            path = []
            path_flow = float('inf')
            v = t
            while v != s:
                u, idx = parent[v]
                path.append(self.names[v])
                path_flow = min(path_flow, self.graph[u][idx].capacity)
                v = u
            path.append(self.names[s])
            path.reverse()

            print(f"[Edmonds-Karp] Path {iteration}: {' -> '.join(path)}")
            print(f"Bottleneck: {path_flow}\n")

            # Update residual capacities
            v = t
            while v != s:
                u, idx = parent[v]
                edge = self.graph[u][idx]
                edge.capacity -= path_flow
                self.graph[v][edge.rev].capacity += path_flow
                v = u

            flow += path_flow
            iteration += 1

        return flow

    # ---------------- Ford-Fulkerson (DFS approach) ----------------
    def dfs(self, u, t, f, visited, path):
        if u == t:
            return f

        visited[u] = True

        for i, edge in enumerate(self.graph[u]):
            if edge.capacity > 0 and not visited[edge.to]:
                path.append(self.names[edge.to])
                pushed = self.dfs(
                    edge.to,
                    t,
                    min(f, edge.capacity),
                    visited,
                    path
                )
                if pushed > 0:
                    edge.capacity -= pushed
                    self.graph[edge.to][edge.rev].capacity += pushed
                    return pushed
                path.pop()

        return 0

    def ford_fulkerson(self, s, t):
        flow = 0
        iteration = 1

        while True:
            visited = [False] * len(self.graph)
            path = [self.names[s]]
            pushed = self.dfs(s, t, float('inf'), visited, path)

            if pushed == 0:
                break

            print(f"[Ford-Fulkerson] Path {iteration}: {' -> '.join(path)}")
            print(f"Bottleneck: {pushed}\n")

            flow += pushed
            iteration += 1

        return flow


# Node mapping:
# 0: S (Source)
# 1: A
# 2: B
# 3: C
# 4: D
# 5: T (Sink)
node_names = ['S', 'A', 'B', 'C', 'D', 'T']


# building the graph
def build_blockchain_graph():
    mf = MaxFlow(6, node_names)

    mf.add_edge(0, 1, 10)  # S -> A
    mf.add_edge(0, 2, 10)  # S -> B

    mf.add_edge(1, 3, 4)   # A -> C
    mf.add_edge(1, 4, 8)   # A -> D

    mf.add_edge(2, 3, 6)   # B -> C
    mf.add_edge(2, 4, 2)   # B -> D

    mf.add_edge(3, 5, 10)  # C -> T
    mf.add_edge(4, 5, 10)  # D -> T

    return mf



print("===== Edmonds-Karp =====\n")
mf_ek = build_blockchain_graph()
maxflow_ek = mf_ek.edmonds_karp(0, 5)
print("Max Flow (Edmonds-Karp):", maxflow_ek)

print("\n===== Ford-Fulkerson =====\n")
mf_ff = build_blockchain_graph()
maxflow_ff = mf_ff.ford_fulkerson(0, 5)
print("Max Flow (Ford-Fulkerson):", maxflow_ff)