The file kargerMinCut.txt contains the adjacency list representation of a simple undirected graph. There are 200 vertices labeled 1 to 200. The first column in the file represents the vertex label, and the particular row (other entries except the first column) tells all the vertices that the vertex is adjacent to. So for example, the 6th row looks like : "6 155 56 52 120 ......". This just means that the vertex with label 6 is adjacent to (i.e., shares an edge with) the vertices with labels 155,56,52,120,......,etc
Your task is to code up and run the randomized contraction algorithm for the min cut problem and use it on the above graph to compute the min cut. (HINT: Note that you'll have to figure out an implementation of edge contractions. Initially, you might want to do this naively, creating a new graph from the old every time there's an edge contraction. But you should also think about more efficient implementations.) (WARNING: As per the video lectures, please make sure to run the algorithm many times with different random seeds, and remember the smallest cut that you ever find.) Write your numeric answer in the space provided. So e.g., if your answer is 5, just type 5 in the space provided.
In [9]:
import numpy as np
import copy
import tqdm
FILE = "kargerMinCut.txt"
SEP = "\t"
# FILE = "input_random_13_50.txt"
# SEP = " "
def get_edge_id(l,m):
l = int(l)
m = int(m)
a,b = (l,m) if l<m else (m,l)
return str(a)+"-"+str(b)
def get_edge_id_create_if_absent(edge_index, l,m):
edge_id = get_edge_id(l,m)
if edge_index not in index:
l = len(index)
index[edge_index] = l
ret = l
else:
ret = index[edge_index]
return ret
fp = open(FILE, "r+")
# Data Structures
min_cut_data = dict() # Adjacancy List as a dictionary
min_cut_edges = [] # List of Edges
min_cut_edges_to_idx = {} # Edge Id to List index
min_cut_idx_to_edge = {} # Edge Id to List index
for line in (fp.readlines()):
row = line.strip().split(SEP)
min_cut_data[row[0]] = row[1:]
N = len(min_cut_data) # Number of Vertices
# Create edge list
for key, dt in min_cut_data.items():
all_keys = min_cut_edges_to_idx.keys()
for d in dt:
edge_id = get_edge_id(key,d)
if edge_id not in min_cut_edges_to_idx:
l = len(min_cut_edges_to_idx)
min_cut_edges_to_idx[edge_id] = l
min_cut_edges.append(1)
min_cut_idx_to_edge[l] = edge_id
print (np.sum(min_cut_edges))
In [ ]:
# Test
print ("Number of edges:", len(min_cut_edges))
#print (min_cut_idx_to_edge)
# print (min_cut_edges_to_idx)
In [2]:
class randomContractObj(object):
def __init__(self, graph, edges, edge_id_to_idx, idx_to_edge_id):
self.graph = graph
self.edges = edges
self.edge_id_to_idx = edge_id_to_idx
self.idx_to_edge_id = idx_to_edge_id
def get_edge_create_if_absent(self, edge_id):
#print ("get Edge", edge_id, self.edge_id_to_idx)
if edge_id in self.edge_id_to_idx:
return self.edge_id_to_idx[edge_id]
else:
l = len(self.edge_id_to_idx)
self.edge_id_to_idx[edge_id] = l
self.edges.append(0)
self.idx_to_edge_id[l] = edge_id
#print ("add edge-id {} with index {}".format(edge_id, l))
return l
def get_num_vertices(self):
return len(self.graph.items())
def remove_edge(self, edge):
"""
let (u,v) = edge
Consider u as the anchor
1) remove ("u-v") from the edge list
2) Merge step: copy all outgoing edges from v to node u, except those already there
4) remove vertex v from graph
"""
u,v = edge.split("-")
#print ("u={},v={}".format(u, v))
#1. Remove all edges v-u
self.edges[self.edge_id_to_idx[get_edge_id(u,v)]] = 0
#2. Update adjacency lists of each k and v
#print ("Remove", v, graph[v])
for k in graph[v]:
if k == u:
continue
#print (("neighbor {} of {}").format(k, v))
# UPDATE GRAPH Structure: Remove v from the adj list of all its neighbours
#print ("graph", k, graph[k])
graph[k].remove(v)
if u not in graph[k]:
graph[k].append(u)
# add the neighbor in the vertice of u
if k not in graph[u]:
graph[u].append(k)
# UPDATE EDGE STRUCTURE remove all edges from edge list
#edges.setdefault(get_edge_id(k,u), 0)
idx = self.get_edge_create_if_absent(get_edge_id(k,u))
self.edges[idx] += edges[self.edge_id_to_idx[get_edge_id(v,k)]]
self.edges[self.edge_id_to_idx[get_edge_id(v,k)]] = 0
#3. Remove vertex v
self.graph[u].remove(v)
self.graph.pop(v)
def get_random_edge(self):
# r = np.random.randint(0, get_num_edges(edges))
# i = 0
# for key, d in edges.items():
# if d == 0:
# continue
# if r - i <= d:
# return key
# i += d
dist = np.asarray(self.edges) / np.sum(self.edges)
i = np.random.multinomial(1, dist)
key = self.idx_to_edge_id[np.nonzero(i)[0][0]]
return key
def get_num_edges(self):
# N = 0
# for key, d in edges.items():
# N += d
# return N
return np.sum(self.edges)
def run_RandomContract(self):
while self.get_num_vertices() > 2:
edge = self.get_random_edge()
#print ("Remove next edge", edge, "Num Vertices", get_num_vertices(graph))
self.remove_edge(edge)
return self.get_num_edges()
In [ ]:
# Example graph
"""
1 2
*---*
| / |
|/ |
*---*
3 4
"""
graph = {
"1":["2", "3"],
"2":["1", "3", "4"],
"3":["1","2", "4"],
"4":["2", "3"]
}
edges = [
1, #"1-2"
1, #"1-3"
1, #"2-3"
1, #"3-4"
1 #"2-4"
]
edge_id_to_idx = {
"1-2":0,
"1-3":1,
"2-3":2,
"3-4":3,
"2-4":4
}
idx_to_edge_id = {
0:"1-2",
1:"1-3",
2:"2-3",
3:"3-4",
4:"2-4"
}
# edge =(get_random_edge(myedges))
rc = randomContractObj(graph, edges, edge_id_to_idx, idx_to_edge_id)
edge = "3-1"
print ("REMOVE edge", edge)
print ("before", graph)
rc.remove_edge(edge )
print ("new graph:", rc.graph)
print ("edges:", rc.edges)
print ("num_edges",rc.get_num_edges())
print ("num_vertices",rc.get_num_vertices())
edge = "2-3"
print ("REMOVE edge", edge)
rc.remove_edge(edge)
print ("new graph:",rc.graph)
print ("edges:",rc.edges)
print ("num_edges",rc.get_num_edges())
print ("num_vertices",rc.get_num_vertices())
"""
Expected Results
REMOVE edge 3-1
before {'2': ['1', '3', '4'], '4': ['2', '3'], '3': ['1', '2', '4'], '1': ['2', '3']}
new graph: {'2': ['3', '4'], '4': ['2', '3'], '3': ['2', '4']}
edges: {'2-3': 2, '1-2': 0, '1-3': 0, '3-4': 1, '2-4': 1}
num_edges 4
num_vertices 3
REMOVE edge 2-3
new graph: {'2': ['4'], '4': ['2']}
edges: {'2-3': 0, '1-2': 0, '1-3': 0, '3-4': 0, '2-4': 2}
num_edges 2
num_vertices 2
In [132]:
"""
In [ ]:
# Example graph
np.random.seed(2)
"""
1 2
*---*
| / |
|/ |
*---*
3 4
"""
graph = {
"1":["2", "3"],
"2":["1", "3", "4"],
"3":["1","2", "4"],
"4":["2", "3"]
}
edges = [
1, #"1-2"
1, #"1-3"
1, #"2-3"
1, #"3-4"
1 #"2-4"
]
edge_id_to_idx = {
"1-2":0,
"1-3":1,
"2-3":2,
"3-4":3,
"2-4":4
}
idx_to_edge_id = {
0:"1-2",
1:"1-3",
2:"2-3",
3:"3-4",
4:"2-4"
}
# edge =(get_random_edge(myedges))
rc = randomContractObj(graph, edges, edge_id_to_idx, idx_to_edge_id)
print (rc.run_RandomContract())
print ("new graph:",rc.graph)
print ("edges:",rc.edges)
print ("num_edges",rc.get_num_edges())
print ("num_vertices",rc.get_num_vertices())
"""
Expected
new graph: {'2': ['1'], '1': ['2']}
edges: {'2-3': 0, '1-2': 2, '1-3': 0, '3-4': 0, '2-4': 0}
num_edges 2
num_vertices 2
"""
In [ ]:
np.random.seed()
graph = dict() # Adjacancy List as a dictionary
edges = [] # List of Edges
edges_to_idx = {} # Edge Id to List index
idx_to_edge = {} # Edge Id to List index
graph = copy.deepcopy(min_cut_data)
edges = copy.deepcopy(min_cut_edges)
edges_to_idx = copy.deepcopy(min_cut_edges_to_idx)
idx_to_edge = copy.deepcopy(min_cut_idx_to_edge)
rc = randomContractObj(graph, edges, edges_to_idx, idx_to_edge)
print ("Mincut", rc.run_RandomContract())
In [10]:
#print (list(edges.keys()))
#np.random.seed(1)
def run_iteration(mygraph, myedges, myedges_to_idx, myidx_to_edge):
rc = randomContractObj(mygraph, myedges, myedges_to_idx, myidx_to_edge)
mincut = rc.run_RandomContract()
return mincut
N = len(min_cut_data)
TOTAL = int(N**2 * np.log(N))
print ("TOTAL", TOTAL)
mincuts = []
new_min = 2*N
for i in tqdm.tqdm(range(TOTAL)):
#np.random.seed(i)
graph = dict() # Adjacancy List as a dictionary
edges = [] # List of Edges
edges_to_idx = {} # Edge Id to List index
idx_to_edge = {} # Edge Id to List index
graph = copy.deepcopy(min_cut_data)
edges = copy.deepcopy(min_cut_edges)
edges_to_idx = copy.deepcopy(min_cut_edges_to_idx)
idx_to_edge = copy.deepcopy(min_cut_idx_to_edge)
mincut = run_iteration(graph, edges, edges_to_idx, idx_to_edge)
#print ("Mincut", mincut, "seed", i)
# rc = randomContractObj(graph, edges, edges_to_idx, idx_to_edge)
# mincut = rc.run_RandomContract()
if mincut < new_min:
print ("new min", mincut)
new_min = mincut
mincuts.append(mincut)
print (min(mincuts))
In [ ]:
print (i)
In [ ]:
In [ ]: