# 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")
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):
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):
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()

```