<jupyter_start><jupyter_text>Programming assignment 4_src: [Programming Assignment 4](https://www.coursera.org/learn/algorithms-divide-conquer/exam/AUmUg/programming-assignment-4/attempt)_<jupyter_code>import sys
sys.path.append('.')
sys.path.append('..')
from problem_loader import ProblemLoader
from helpers import obfuscate
import copy
import random
from enum import Enum
from statistics import mean
from math import log, comb
import time

data_urls = {
  'problem1': 'https://d18ky98rnyall9.cloudfront.net/_f370cd8b4d3482c940e4a57f489a200b_kargerMinCut.txt?Expires=1622505600&Signature=gemMmEleQVSofFHagOzWZ7hanib8dyiacrwf6khFPkg16KFFL~VxM8FxIfVUDK1Ut6ToU2rBLAOrf5eY-xwG0mbRBodh2y9x-t9ZZPV0Qp8w2ltj3IMMggSLSUSbnNzu7XrUYmdkuTSkHbleZWT~R8ACcHXCgiwMTQeCHmRbWuk_&Key-Pair-Id=<KEY>',
}<jupyter_output><empty_output><jupyter_text>Problem 1 DescriptionThe file 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 $6^{th}$ th  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.<jupyter_code>def preprocess_data(data):
    values = {}
    for line in list(filter(None, data.decode("utf-8").split('\r\n'))):
        elements = list(map(
            int, 
            filter(None, line.split('\t'))
        ))    
        values[elements[0]] = elements[1:]
    return values
    

values = ProblemLoader(
    data_urls['problem1'], 
    fname="graph.p", 
    preprocessor=preprocess_data
).fetch()
print(values[1])
class KargerLimits(Enum):
  limit = 0
  limit_n2logn = 1
  limit_n = 2

class Karger():
  def __init__(self):
    self.graph = None

  def cut(self):
    x, y = self.graph.keys()
    #return min(len(self.graph[x]), len(self.graph[y]))
    return len(self.graph[x])

  def contract_edge(self, x, y):  
    if x == y:
      print('warning: same x,y',x,y, self.graph[x])

    # -- merge the vertex at the edge into a single vertex
    self.graph[x].extend(self.graph[y])

    del self.graph[y]

    for k,v in self.graph.items():
      self.graph[k] = [i if i!=y else x for i in v] 
      # -- delete self loops (edge where both endpoints are the same)
      self.graph[k] = list(filter(lambda i: i != k, self.graph[k]))

  def get_edge(self):
    x = random.choice(list(self.graph.keys()))
    y = random.choice(self.graph[x])
    return x, y

  def get_limit(self, limit_type, graph):
    n = len(graph.keys())
    if limit_type == KargerLimits.limit_n:
      return n
    if limit_type == KargerLimits.limit_n2logn:
      return round(n**2 * log(n))
    if limit_type == KargerLimits.limit:
      return round(comb(n,2) * log(n))

  def find_min_cuts(self, graph, limit_type=KargerLimits.limit):
    cuts = []
    limit = self.get_limit(limit_type, graph)
    for i in range(limit): # note: technically n = limit: n^2 log(n) so we're pretty low but instructor indicates this should suffice
      # while there are more than 2 vertices
      # - pick an edge uniformly at random
      # - contract edge
      # - return cut represented by 2 final vertices
      self.graph = copy.deepcopy(graph)
      while len(self.graph) > 2:
        x, y = self.get_edge()
        self.contract_edge(x, y)
      cuts.append(self.cut())
    
    return min(cuts)


def timeit(fn, sample_size=1):
    elapsed_time = []
    for i in range(sample_size):
        t = time.process_time()
        fn()
        elapsed_time.append(time.process_time() - t)
    print(mean(elapsed_time), 'seconds')

def problem1():
    k = Karger()
    result = k.find_min_cuts(values, limit_type=KargerLimits.limit_n)
    obfuscate(result)

timeit(problem1)<jupyter_output>20.985284 seconds
{'fraction_non_alphanumeric': 0.10618101545253864, 'fraction_numerical': 0.026048565121412803, 'mean_word_length': 3.656731757451182, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 10, 'https://': 2, 'lorem ipsum': 0, 'www.': 1, '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': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '221896', 'license': 'MIT', 'n_tokens_mistral': 1601, 'n_tokens_neox': 1501, 'n_words': 447, 'path': 'week4/mincut.ipynb', 'repo_name': 'robbiemu/divide_and_conquer_coursework', 'size': '4545'}