Last active
March 11, 2024 02:04
-
-
Save zaksamalik/457adbf0d60c1d4486484c1fac0a95f5 to your computer and use it in GitHub Desktop.
Karger Algorithm to Find Min Cut Using Adjacency List
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from os.path import expanduser | |
import random | |
import time | |
import numpy as np | |
def swap_converged_nodes(adjacency_list, node, converged_node, vertex): | |
""" Replace converged node with vertex (i.e. super node) in all adjacency list entries after converging. | |
Args: | |
adjacency_list (dict): adjacency list where key = vertex, value = list of nodes having an edge with vertex | |
node (int): target vertex (node) key in adjacency list to replace converged node with vertex values | |
converged_node (int): value of converged node | |
vertex (int): value of vertex that node was converged into. | |
Returns: | |
Nothing: This is an in-place function. | |
""" | |
adjacency_list[node] = [vertex if n == converged_node else n for n in adjacency_list[node] if n != node] | |
def karger_min_cut(adjacency_list): | |
""" Implementation of Karger minimum cut algorithm using an adjacency list (dictionary). | |
Args: | |
adjacency_list (dict): adjacency list where key = vertex, value = list of nodes having an edge with vertex | |
Returns: | |
adjacency_list (dict): filtered for results of minimum cut algorithm. | |
""" | |
while len(adjacency_list) > 2: | |
# randomly select edge vertex and node to be merged into vertex | |
vertex = random.choice(list(adjacency_list)) | |
converged_node = random.choice(adjacency_list[vertex]) | |
# converge node into vertex and remove node from adjacency list | |
edge_nodes_from_converged_node = [n for n in adjacency_list[converged_node] if n != vertex] | |
adjacency_list[vertex] = [n for n in adjacency_list[vertex] if n != converged_node] | |
adjacency_list[vertex] += edge_nodes_from_converged_node | |
adjacency_list.pop(converged_node) | |
# swap converged node with vertex in all adjacency list vertices that shared an edge with converged node | |
for node in list(set(edge_nodes_from_converged_node)): | |
swap_converged_nodes(adjacency_list, node, converged_node, vertex) | |
return adjacency_list | |
def main(): | |
# get input graph as adjacency list | |
input_adjacency_list = {} | |
file_path = expanduser('~/kargerMinCut.txt') | |
with open(file_path) as f: | |
for line in f: | |
line_values = [int(i) for i in line.split()] | |
k = line_values[0] | |
v = [i for i in line_values[1:] if i != k] | |
v.sort() | |
input_adjacency_list[k] = v | |
start = time.time() | |
results = [] | |
for i in range(200): | |
adjacency_list = input_adjacency_list.copy() | |
results.append(karger_min_cut(adjacency_list)) | |
end = time.time() | |
min_cuts = [] | |
for result in results: | |
keys = list(result.keys()) | |
min_cuts.append(len(result[keys[0]])) | |
print('Min cut: ' + str(min(min_cuts))) | |
print('~~~~~~~~~~~~~~~~~~~~~~~') | |
print('Total Runtime: ' + str(round(end - start, 6)) + ' seconds') | |
print('~~~~~~~~~~~~~~~~~~~~~~~') | |
run_times = [] | |
for i in range(200): | |
adjacency_list = input_adjacency_list.copy() | |
start = time.time() | |
karger_min_cut(adjacency_list) | |
end = time.time() | |
run_times.append(end - start) | |
print('Mean run time per iteration: ' + str(np.mean(run_times))) | |
print('Median run time per iteration: ' + str(np.median(run_times))) | |
print('Min run time per iteration: ' + str(min(run_times))) | |
print('Max run time per iteration: ' + str(max(run_times))) | |
if __name__ == '__main__': | |
main() |
Hi Huzaifg,
I think this line helps remove the edge between the converged node and the vertex to be merged with, i.e., the self loop, if any.
Thank you for sharing the code :D Your code helped me realize I was choosing 2 random vertices (even the ones not connecting), thus my outputs were chaotic.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Hello!
Isnt this line of the code redundant?
adjacency_list[vertex] = [n for n in adjacency_list[vertex] if n != converged_node]
Since we are anyways poping the converged node in the last line?