Karger Algorithm to Find Min Cut Using Adjacency List

karger_min_cut_adjacency_list.py

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

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.