dinic_algorithm.py

class Edge:
    def __init__(self, v, flow, capacity, reverse_edge):
        self.v = v
        self.flow = flow
        self.capacity = capacity
        self.reverse_edge = reverse_edge

class Graph:
    def __init__(self, vertices):
        self.adjacency = [[] for _ in range(vertices)]
        self.vertices = vertices
        self.levels = [0] * vertices

    def add_edge(self, u, v, capacity):
        forward_edge = Edge(v, 0, capacity, len(self.adjacency[v]))
        backward_edge = Edge(u, 0, 0, len(self.adjacency[u]))
        self.adjacency[u].append(forward_edge)
        self.adjacency[v].append(backward_edge)

    def bfs(self, source, sink):
        for i in range(self.vertices):
            self.levels[i] = -1
        self.levels[source] = 0
        queue = [source]
        while queue:
            u = queue.pop(0)
            for edge in self.adjacency[u]:
                if self.levels[edge.v] < 0 and edge.flow < edge.capacity:
                    self.levels[edge.v] = self.levels[u] + 1
                    queue.append(edge.v)
        return self.levels[sink] >= 0

    def send_flow(self, u, flow, sink, start):
        if u == sink:
            return flow
        while start[u] < len(self.adjacency[u]):
            edge = self.adjacency[u][start[u]]
            if self.levels[edge.v] == self.levels[u] + 1 and edge.flow < edge.capacity:
                current_flow = min(flow, edge.capacity - edge.flow)
                temp_flow = self.send_flow(edge.v, current_flow, sink, start)
                if temp_flow > 0:
                    edge.flow += temp_flow
                    self.adjacency[edge.v][edge.reverse_edge].flow -= temp_flow
                    return temp_flow
            start[u] += 1
        return 0

    def dinic_maxflow(self, source, sink):
        if source == sink:
            return -1
        max_flow = 0
        while self.bfs(source, sink):
            start = [0] * (self.vertices + 1)
            while True:
                flow = self.send_flow(source, float('inf'), sink, start)
                if flow == 0:
                    break
                max_flow += flow
        return max_flow

# Create a graph and add edges
graph = Graph(6)
graph.add_edge(0, 1, 16)
graph.add_edge(0, 2, 13)
graph.add_edge(1, 2, 10)
graph.add_edge(1, 3, 12)
graph.add_edge(2, 1, 4)
graph.add_edge(2, 4, 14)
graph.add_edge(3, 2, 9)
graph.add_edge(3, 5, 20)
graph.add_edge(4, 3, 7)
graph.add_edge(4, 5, 4)

# Calculate the maximum flow
maximum_flow = graph.dinic_maxflow(0, 5)
print("Maximum flow:", maximum_flow)