edmonds-karp

import numpy as np
import collections

def formatter():
    input = open("C:\\Users\\kalls\\OneDrive\\Dokument\\EDAF05-labs-public-master\\6railwayplanning\\data\\sample\\1.in")
    numbers = input.readline().split()
    N = int(numbers[0]) #Number of nodes (cities)
    M = int(numbers[1]) #Number of edges (connections)
    C = int(numbers[2]) #Number of flow (students/soldiers)
    P = int(numbers[3]) #Number of routes
    dict1 = {}
    dict2 = {}  # We create dictionaries here
    edgelist = []
    for i in range(0, N):
        dict1.update({i: []})
        dict2.update({i: []})  # And fill them with keys, one for each node
    for j in range(0,M):
        edge = input.readline().split()
        dict1[int(edge[0])].append({int(edge[1]):int(edge[2])})
        dict2[int(edge[1])].append({int(edge[0]):int(edge[2])})
        edgelist.append((edge[0],edge[1]))
    removelist = []
    for k in range (0,P):
        edgenr = input.readline()
        removelist.append(edgelist[edgenr])
    for i in dict1:  # Here we combine the dictionaries into one
        if dict2[i] == []:
            continue
        elif dict1[i] == []:
            dict1[i] = dict2[i]
        else:
            # We add all edges in dict2 to the list in dict1
            for j in range(0, len(dict2[i])):
                dict1[i].append(dict2[i][j])
        

    return N,M,C,P,dict1,removelist

class Graph:
    """This class represents a directed graph using adjacency matrix representation."""

    def __init__(self, graph):
        self.graph = graph  # residual graph
        self.row = len(graph)

    def bfs(self, s, t, parent):
        """Returns true if there is a path from source 's' to sink 't' in
        residual graph. Also fills parent[] to store the path."""

        # Mark all the vertices as not visited
        visited = [False] * self.row

        # Create a queue for BFS
        queue = collections.deque()

        # Mark the source node as visited and enqueue it
        queue.append(s)
        visited[s] = True

        # Standard BFS loop
        while queue:
            u = queue.popleft()

            # Get all adjacent vertices of the dequeued vertex u
            # If an adjacent has not been visited, then mark it
            # visited and enqueue it
            for ind, val in enumerate(self.graph[u]):
                if (visited[ind] == False) and (val > 0):
                    queue.append(ind)
                    visited[ind] = True
                    parent[ind] = u

        # If we reached sink in BFS starting from source, then return
        # true, else false
        return visited[t]

    # Returns the maximum flow from s to t in the given graph
    def edmonds_karp(self, source, sink):

        # This array is filled by BFS and to store path
        parent = [-1] * self.row

        max_flow = 0  # There is no flow initially

        # Augment the flow while there is path from source to sink
        while self.bfs(source, sink, parent):

            # Find minimum residual capacity of the edges along the
            # path filled by BFS. Or we can say find the maximum flow
            # through the path found.
            path_flow = float("Inf")
            s = sink
            while s != source:
                path_flow = min(path_flow, self.graph[parent[s]][s])
                s = parent[s]

            # Add path flow to overall flow
            max_flow += path_flow

            # update residual capacities of the edges and reverse edges
            # along the path
            v = sink
            while v != source:
                u = parent[v]
                self.graph[u][v] -= path_flow
                self.graph[v][u] += path_flow
                v = parent[v]

        return max_flow

if __name__ == '__main__':
    N,M,C,P,dict,removelist = formatter()