Implement those two algorithms in the following code:

import sys import random import collections

""" This code is Part 1:Vertex Cover Approximation """

def main(): filename = sys.argv[1] algo = sys.argv[2]

G = load_graph(filename)

cover = [] if algo == "greedy-vertex": cover = greedy_vertex(G) elif algo == "greedy-edge": cover = greedy_edge(G) else: print "Incorrect arguments" exit()

output_cover(cover)

def output_cover(cover): with open("approxOutput.txt", "w") as fout: for v in cover: fout.write(str(v)+" ")

def greedy_edge(adj_list): """ Implement your code for greedy edge here. It should return a list of vertices that covers every edge. """

def greedy_vertex(adj_list): """ Implement your code for greedy vertex here. It should return a list of vertices that covers every edge. """

def load_graph(filename): adj_list = collections.defaultdict(set) with open(filename, "r") as fin: for line in fin: u, v = [int(v) for v in line.strip().split()] adj_list[u].add(v) adj_list[v].add(u) return adj_list

if __name__ == "__main__": main()

Algorithm 2- Approximation Greedy Vertex INPUT: A graph G-(V,E) OUTPUT: A vertex cover in G that is at most twice the size of a minimum VC 1. 2. While El > 0 1. Select the highest degree vertex v in G 3. Remove v and all adjacent edges from G 3. Return C INPUT: A graph G-(V,E) OUTPUT: A vertex cover in G that is at most twice the size of a minimum VC 2. While IEI>0 1. Select an edge (u,v) in E Remove any edges incident to u or v in E 3. 3. Return C Algorithm 2- Approximation Greedy Vertex INPUT: A graph G-(V,E) OUTPUT: A vertex cover in G that is at most twice the size of a minimum VC 1. 2. While El > 0 1. Select the highest degree vertex v in G 3. Remove v and all adjacent edges from G 3. Return C INPUT: A graph G-(V,E) OUTPUT: A vertex cover in G that is at most twice the size of a minimum VC 2. While IEI>0 1. Select an edge (u,v) in E Remove any edges incident to u or v in E 3. 3. Return C