minimum cut Algorithm
The minimum cut algorithm is a graph theory-based technique used for finding the smallest set of edges that, when removed, would disconnect a connected graph into two disjoint subgraphs, effectively severing the communication between the two parts. This concept is widely used in various applications, such as network reliability, VLSI design, image segmentation, and transportation planning, among others. The algorithm mainly focuses on finding the edge connectivity between different nodes in a given graph, which ultimately helps in determining the minimum cut.
One of the most popular and efficient implementations of the minimum cut algorithm is the Karger's algorithm, which is a randomized contraction algorithm. It works by repeatedly selecting a random edge from the graph and collapsing the two vertices connected by the edge into a single vertex, all while maintaining the original graph connectivity. This process continues until only two vertices remain, representing the two disjoint subgraphs. The number of edges between these two vertices corresponds to the minimum cut. By running Karger's algorithm multiple times and selecting the smallest cut found across the iterations, the probability of finding the actual minimum cut is increased. Although Karger's algorithm does not guarantee finding the minimum cut in a single run, it has been proven to have a relatively high probability of success, making it a practical choice for various applications.
# Minimum cut on Ford_Fulkerson algorithm.
test_graph = [
[0, 16, 13, 0, 0, 0],
[0, 0, 10, 12, 0, 0],
[0, 4, 0, 0, 14, 0],
[0, 0, 9, 0, 0, 20],
[0, 0, 0, 7, 0, 4],
[0, 0, 0, 0, 0, 0],
]
def BFS(graph, s, t, parent):
# Return True if there is node that has not iterated.
visited = [False] * len(graph)
queue = [s]
visited[s] = True
while queue:
u = queue.pop(0)
for ind in range(len(graph[u])):
if visited[ind] is False and graph[u][ind] > 0:
queue.append(ind)
visited[ind] = True
parent[ind] = u
return True if visited[t] else False
def mincut(graph, source, sink):
"""This array is filled by BFS and to store path
>>> mincut(test_graph, source=0, sink=5)
[(1, 3), (4, 3), (4, 5)]
"""
parent = [-1] * (len(graph))
max_flow = 0
res = []
temp = [i[:] for i in graph] # Record original cut, copy.
while BFS(graph, source, sink, parent):
path_flow = float("Inf")
s = sink
while s != source:
# Find the minimum value in select path
path_flow = min(path_flow, graph[parent[s]][s])
s = parent[s]
max_flow += path_flow
v = sink
while v != source:
u = parent[v]
graph[u][v] -= path_flow
graph[v][u] += path_flow
v = parent[v]
for i in range(len(graph)):
for j in range(len(graph[0])):
if graph[i][j] == 0 and temp[i][j] > 0:
res.append((i, j))
return res
if __name__ == "__main__":
print(mincut(test_graph, source=0, sink=5))
