Min Cut Graph

min-cut.py

from random import choice
from copy import deepcopy


class MinCutGraph(object):
    def __init__(self, create_graph_fn):
        if not hasattr(create_graph_fn, '__call__'):
            raise TypError('Expected `create_graph_fn` to be a func')

        self.graph = create_graph_fn()
        if not isinstance(self.graph, dict): raise TypeError('Expected method to return')

        self.n = len(self.graph.keys())

    def is_edges(self, edges):
        return isinstance(edges, list) and len(edges) > 0

    def get_edges(self, v):
        edges = self.graph.get(v)
        assert self.is_edges(edges), 'Expected edges to be a list'
        return edges

    def get_vertices(self):
        v1 = choice(self.graph.keys())
        edges = self.get_edges(v1)
        # Select an edge from possible adjacent edges
        v2 = choice(edges)
        return v1, v2

    def merge_edges(self, v1, v2):
        edges1 = self.get_edges(v1)
        edges2 = self.get_edges(v2)
        [edges1.append(edge) for edge in edges2]

    def remove_vertex(self, v):
        assert v is not None
        
        if self.graph.has_key(v) is not None:
            del self.graph[v]

    def convert_vertex(self, v2, v1):
        assert v2 is not None, 'Expected a vertex to be passed in for `v2`'
        assert v1 is not None, 'Expected a vertex to be passed in for `v1`'
        assert v1 != v2, 'Expected `v1` and `v2` to be unique'

        for edges in self.graph.values():
            for i in xrange(len(edges)):
                if edges[i] == v2:
                    edges[i] = v1

    def remove_loops(self, v):
        assert v is not None
        edges = self.get_edges(v)
        self.graph[v] = filter(lambda val: val != v, edges)

    def get_min_cut(self):
        self._get_min_cut()
        return len(self.graph.values()[0])

    def _get_min_cut(self):
        # TODO test if 2 vertices

        # iterate while number of vertices is greater than 2
        while self.n > 2:
            v1, v2 = self.get_vertices()
            self.merge_edges(v1, v2)
            self.remove_vertex(v2)
            self.convert_vertex(v2, v1)
            self.remove_loops(v1)
            self.n -= 1


def create_simple_graph():
    graph = {}
    for line in open('min-cut.txt', 'r'):
        edges = line.rstrip().split('-')
        vertex = edges.pop(0)
        # First value in line is the vertex
        # the rest of the values are
        graph[vertex] = edges
    return graph

def create_dijkstra_graph():
    graph = {}
    for line in open('dijkstraData.txt', 'r'):
        line = line.rstrip().split('\t')
        vertex = line.pop(0)
        edges = [tup.split(',')[0] for tup in line]
        graph[vertex] = edges
    return graph

#graph = MinCutGraph(create_dijkstra_graph)
#cuts = [graph.get_min_cut()]
n = sum(1 for line in open('dijkstraData.txt', 'r'))
graphs = [MinCutGraph(create_dijkstra_graph) for i in xrange(n)]
cuts = [graph.get_min_cut() for graph in graphs]
print min(cuts)

n = sum(1 for line in open('min-cut.txt', 'r'))
graphs = [MinCutGraph(create_simple_graph) for i in xrange(n)]
cuts = [graph.get_min_cut() for graph in graphs]
print min(cuts)