# edmonds-karp

unknown

plain_text

2 years ago

3.8 kB

1

Indexable

Never

^{}

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()