Detect a bottleneck of a graph, i.e., Min-Cut, using the Max-flow algorithm. In other words, the algorithm should find a set of edges F ⊆ E such that there is minimum cut (S, T) such that the edges in F cross the cut. (In the direction S → T). The program takes as an input a network presented as a weighted graph G =(V, E, w) where w is interpreted as the capacities. The source s is the vertex that has the smallest number of any vertex that has outgoing edges. Usually this is 1, but it could be 0. The vertex with the largest number with incoming edges is considered t. I.e., the input doesn’t separately specify the source and the sink. Edges should be pairs of vertices (direction matters) given in a list or set but Order of vertices does not matter. implement a class FlowNetwork(G),whose constructor takes in the graph and which implements the method MinCut(),that returns the list of edges that is required.
Need help to review the code. If the code aligns with the question above. if not what change is needed.
Need help to review the code. If the code aligns with the question above. if not what change is needed.
from collections import defaultdict, deque
import networkx as nx
class FlowNetwork:
def _init_(self, graph):
self.graph = graph
self.residual_graph = defaultdict(dict)
for u, v, capacity in graph.edges(data=True):
self.residual_graph[u][v] = capacity['capacity']
self.residual_graph[v][u] = 0 # Add reverse edge with 0 capacity
def find_min_cut(self, source, sink):
visited = set()
stack = [source]
visited.add(source)
# DFS to find reachable nodes from the source in the residual graph
while stack:
current_node = stack.pop()
for neighbor, capacity in self.residual_graph[current_node].items():
if neighbor not in visited and capacity > 0:
stack.append(neighbor)
visited.add(neighbor)
min_cut_edges = []
for u, v, capacity in self.graph.edges(data=True):
if u in visited and v not in visited and self.residual_graph[u][v] == 0:
min_cut_edges.append((u, v, capacity['capacity']))
return min_cut_edges
def ford_fulkerson(self, source, sink):
max_flow = 0
path = self.bfs(source, sink)
while path:
# Find the minimum capacity in the augmenting path
min_capacity = min(self.residual_graph[u][v] for u, v in path)
# Update the residual graph
for u, v in path:
self.residual_graph[u][v] -= min_capacity
self.residual_graph[v][u] += min_capacity
max_flow += min_capacity
path = self.bfs(source, sink)
return max_flow
def bfs(self, source, sink):
queue = deque([(source, [source])])
while queue:
current_node, path = queue.popleft()
for neighbor, capacity in self.residual_graph[current_node].items():
if capacity > 0 and neighbor not in path:
if neighbor == sink:
return list(zip(path, path[1:] + [neighbor]))
queue.append((neighbor, path + [neighbor]))
return None
def MinCut(self):
source = min(self.graph.nodes)
sink = max(self.graph.nodes)
max_flow = self.ford_fulkerson(source, sink)
# Find the minimum cut using the residual graph
min_cut_edges = self.find_min_cut(source, sink)
return min_cut_edges, max_flow
def read_graph_from_file(file_path):
graph = nx.DiGraph()
with open(file_path, 'r') as file:
for line in file:
parts = line.strip().split(':')
node = parts[0].strip()
graph.add_node(node)
if len(parts) > 1:
edge_list = parts[1].strip().split()
for edge in edge_list:
neighbor, capacity = edge.strip('()').split(',')
graph.add_edge(node, neighbor, capacity=int(capacity))
return graph
# Example usage with the provided test material:
file_path = r'C:\Users\s2400100\OneDrive - Business College Helsinki\Desktop\test.txt'
graph = read_graph_from_file(file_path)
flow_network = FlowNetwork(graph)
min_cut_edges, max_flow = flow_network.MinCut()
print("Minimum cut edges:", min_cut_edges)
print("Maximum flow:", max_flow)