Created
September 7, 2013 21:03
-
-
Save landau/6479274 to your computer and use it in GitHub Desktop.
Min Cut Graph
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 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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment