greedy_vc.py

import integral_vc


class GreedyVC:
	"""
    Class to implement Greedy Algorithm for Vertex Cover
  """

	def printVertexCover(self, graph):
		"""
      Method to identify the vertex cover and cost generated by the Greedy Algorithm
      Parameter:
        Graph
      Return:
        Ratio of total cost of vertex cover to the optimal cost generated by the Integer Program
      Logic:
        Have a boolean value 'visited' for each vertices in the graph
        Sort all the nodes based on their cost
        Iterate through the sorted nodes
          If the current node and its neighbour nodes are not visited
            Set both nodes visited as True
        Vertex Cover is the vertices that are visited
    """
		visited = [False] * len(graph.nodes)
		vc_cost = 0
		# Consider all edges one by one
		for u in sorted(graph.nodes(), key=lambda n: graph.nodes[n]['cost']):
			if not visited[u]:
				for v in graph.neighbors(u):
					if not visited[v]:
						visited[v] = True
						visited[u] = True
						break
    # Print the vertex cover

		for j in range(len(graph.nodes)):
			if visited[j]:
				vc_cost += graph.nodes[j]["cost"]
		integral = integral_vc.IntegralVC()

		opt_cost = integral.vc_integral(graph)
		return round(vc_cost/opt_cost, 3)