karger.py

import time
import random
import copy


# j4f
def runtime(func, args):
    now = time.time()
    func(args)
    return time.time() - now


class Graph(object):
    def __init__(self):
        self.nodes = []
        self.edges = []

    def collapse_graph(self, edge=None):
        if edge is None:
            edge = random.choice(self.edges)
        if edge[0] in self.nodes and edge[1] in self.nodes:
            for point in edge: self.nodes.remove(point)
            self.nodes.append(edge)
            self.edges.remove(edge if edge in self.edges else list(reversed(edge)))
        else:
            if edge[0] in self.nodes:
                node0 = edge[0]
                self.nodes.remove(node0)
                node1 = [i for i in self.nodes if isinstance(i, list) and edge[1] in i][0]
                loops = [[node0, b] for b in node1]
                self.nodes.remove(node1)
                node1.append(node0)
                self.nodes.append(node1)
            elif edge[1] in self.nodes:
                node1 = edge[1]
                self.nodes.remove(node1)
                node0 = [i for i in self.nodes if isinstance(i, list) and edge[0] in i][0]
                loops = [[a, node1] for a in node0]
                self.nodes.remove(node0)
                node0.append(node1)
                self.nodes.append(node0)
            else:
                node0 = [i for i in self.nodes if isinstance(i, list) and edge[0] in i][0]
                self.nodes.remove(node0)
                node1 = [i for i in self.nodes if isinstance(i, list) and edge[1] in i][0]
                loops = [[a, b] for a in node0 for b in node1]
                self.nodes.remove(node1)
                node0.extend(node1)
                self.nodes.append(node0)
            for loop_edge in loops:
                if loop_edge in self.edges:
                    self.edges.remove(loop_edge)
                elif list(reversed(loop_edge)) in self.edges:
                    self.edges.remove(list(reversed(loop_edge)))


def init_graph(graph_list):
    graph = Graph()
    for node in graph_list:
        graph.nodes.append(node[0])
        for d_node in node[1:]:
            edge = [node[0], d_node]
            if edge not in graph.edges and list(reversed(edge)) not in graph.edges:
                graph.edges.append(edge)
    return graph


if __name__ == '__main__':
    with open('test2.txt') as f:
        data = f.readlines()
    data = [[int(num) for num in row.rstrip().split(' ')] for row in data]

    mincut = float('inf')
    cuts = []
    for _ in xrange(50):
        graph = init_graph(data)
        while len(graph.nodes) > 2:
            graph.collapse_graph()
        if len(graph.edges) < mincut:
            mincut = len(graph.edges)
            cut = graph.edges
    print mincut
    print cut