<jupyter_start><jupyter_text>Min Cut AlgorithmThe 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,......,etcYour 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.<jupyter_code>import numpy as np
import copy
import tqdm


FILE = "kargerMinCut.txt"
SEP = "\t"

# FILE = "input_random_14_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))

 
# Test

print ("Number of edges:", len(min_cut_edges))

# print (min_cut_idx_to_edge)
# print (min_cut_edges_to_idx)
def get_num_vertices(graph):
    return len(graph.items())

def remove_edge(graph, edges, edge):
    """
        let (u,v) = edge
        
        1) remove ("u-v") from the edge list
        2) copy all edges from v to u, except dups
        4) remove vertex v from graph
    """
    
    u,v = edge.split("-")
    #print ("u={},v={}".format(u, v))
    
    #1. Remove all edges v-u
    edges[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)
        edges[get_edge_id(k,u)] += edges[get_edge_id(v,k)]
        
        edges[get_edge_id(v,k)] = 0
        
           
    #3. Remove vertex v
    graph[u].remove(v)
    graph.pop(v)

def get_random_edge(edges):
        
    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
        
    return key 

def get_num_edges(edges):
    N = 0
    for key, d in edges.items():
        N += d
        
    return N
    
def RandomContract(graph, edges):    
    while get_num_vertices(graph) > 2:
        edge = get_random_edge(edges)    
        #print ("Remove next edge", edge, "Num Vertices", get_num_vertices(graph))
        remove_edge(graph, edges, edge)


    return get_num_edges(edges)
    
# Example graph

"""
1   2
*---*
| / |
|/  |
*---*
3   4
"""
graph = {
    "1":["2", "3"],
    "2":["1", "3", "4"],
    "3":["1","2", "4"],
    "4":["2", "3"]
}
myedges = {
    "1-2":1,
    "1-3":1,
    "2-3":1,
    "3-4":1,
    "2-4":1
}
# edge =(get_random_edge(myedges))

edge = "3-1"
print ("REMOVE edge", edge)

print ("before",graph)
remove_edge(graph, myedges, edge )
print ("new graph:",graph)
print ("edges:",myedges)
print ("num_edges",get_num_edges(myedges))
print ("num_vertices",get_num_vertices(graph))

    
edge = "2-3"
print ("REMOVE edge", edge)

remove_edge(graph, myedges, edge )
print ("new graph:",graph)
print ("edges:",myedges)
print ("num_edges",get_num_edges(myedges))
print ("num_vertices",get_num_vertices(graph))


# 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"]
}
myedges = {
    "1-2":1,
    "1-3":1,
    "2-3":1,
    "3-4":1,
    "2-4":1
}
# edge =(get_random_edge(myedges))

print (RandomContract(graph, myedges))
print ("new graph:",graph)
print ("edges:",myedges)
print ("num_edges",get_num_edges(myedges))
print ("num_vertices",get_num_vertices(graph))




np.random.seed(9)

graph = dict()
myedges = dict()

graph = copy.deepcopy(min_cut_data)
myedges = copy.deepcopy(min_cut_edges)

mincut = RandomContract(graph, myedges)
print ("Mincut", mincut)
#print (list(edges.keys()))
#np.random.seed(1)

N = get_num_vertices(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 = {}
#     myedges = {}

    graph = copy.deepcopy(min_cut_data)
    myedges = copy.deepcopy(min_cut_edges)

    mincut = RandomContract(graph, myedges)
    #print ("Mincut", mincut, "seed", i)
    
    if mincut < new_min:
        print ("new min", mincut)
        new_min = mincut
        
    mincuts.append(mincut)
    
print (min(mincuts))
print (i)<jupyter_output>5949
{'fraction_non_alphanumeric': 0.13708708708708708, 'fraction_numerical': 0.01981981981981982, 'mean_word_length': 2.7150027886224204, 'pattern_counts': {'":': 18, '<': 7, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '425387', 'license': 'MIT', 'n_tokens_mistral': 2465, 'n_tokens_neox': 2364, 'n_words': 691, 'path': 'min-cut/min-cut.ipynb', 'repo_name': 'jazracherif/algorithms', 'size': '6660'}