I. Implement Algorithms 2 and 3 in Python. The code must take two arguments as i
ID: 3912162 • Letter: I
Question
I. Implement Algorithms 2 and 3 in Python. The code must take two arguments as input:
1. An edge-list text file defining a graph. Each edge is listed on a line and the two vertices in the edge are separated by a space. Vertices are integers and they are not necessarily consecutive. Note: no singleton vertices can be represented in this format.
2. A string ‘greedy-vertex’ or ‘greedy-edge’ that specifies whether to run the greedy vertex or greedy edge algorithm.
II. The code must then run the algorithm and output:
1. A text file call approxOutput.txt, where each line contains a vertex in the vertex cover.
2. Generate a plot of the runtime on graphs of different sizes. Compare both algorithms on a single plot. 3. Generate a plot of the vertex cover sizes for various graphs. Compare how similar the sizes were between both approximation algorithms (plot on the same graph using different colors). The plots for the second and third parts do not have to be done programmatically; that is, the plots can be generated by plugging numbers into a charting program manually, for example.
Explanation / Answer
def greedy_vc(input_graph):
# YOUR CODE HERE
cover = []
valid, num_edge = valid_cover(input_graph, cover)
while not valid:
m = [x for x in range(0, len(num_edge)) if num_edge[x] == max(num_edge)][0]
cover.append(m)
valid, num_edge = valid_cover(input_graph, cover)
return cover
def valid_cover(graph, cover):
valid = True
num_edge = [0] * len(graph)
for i in range(0, len(graph)):
for j in range(i, len(graph)):
if graph[i][j] == 1:
if (i not in cover) and (j not in cover):
valid = False
num_edge[i] += 1
num_edge[j] += 1
return valid, num_edge
def test():
graph = [[0, 1, 1, 1, 1],
[1, 0, 0, 0, 1],
[1, 0, 0, 1, 1],
[1, 0, 1, 0, 1],
[1, 1, 1, 1, 0]]
cover = greedy_vc(graph)
print cover
# There are multiple possible right answers
assert (cover == [0, 4, 2] or
cover == [0, 4, 3] or
cover == [4, 0, 2] or
cover == [4, 0, 3])
test()