pricing_vc.py

import networkx as nx
import matplotlib.pyplot as plt
import integral_vc


class PricingVC:
    """
      Class to implement Pricing Algorithm for a graph
    """

    def vc_pricing(self, graph):
        """
          Method to identify the vertex cover using the pricing algorithm
          Parameters:
            Graph
          Return: 
            Ratio of total cost of vertex cover to the optimal cost generated by the Integer Program
          Logic:
            Assign prices as 0 to the edges based on the cost of the vertices linked to it.
            Assign tighness of each vertex as 0
            Iterate through each edge and check if the vertices are tight. 
              If not tight, assign the value to the edge that makes one of the vertices tight
            Vertex cover is the vertices that are identified as tightly bound.
        """
        vc_result = []
        edge_price = {}
        vertex_tightness = [0 for i in range(len(graph.nodes))]
        for e in graph.edges:
            edge_price[e] = 0
        nx.set_edge_attributes(graph, edge_price, name="price")

        for e in graph.edges:
            from_vertex = e[0]
            to_vertex = e[1]
            v1_balance = graph.nodes[from_vertex]["cost"] - \
                vertex_tightness[from_vertex]
            v2_balance = graph.nodes[to_vertex]["cost"] - \
                vertex_tightness[to_vertex]
            # print(f"{from_vertex} --> {v1_balance}")
            # print(f"{to_vertex} --> {v2_balance}")
            if v1_balance == 0 or v2_balance == 0:
                continue
            if v1_balance < v2_balance:
                graph[from_vertex][to_vertex]["price"] += v1_balance
                vertex_tightness[from_vertex] += v1_balance
                vertex_tightness[to_vertex] += v1_balance
                vc_result.append(from_vertex)
                # print(f"Adding vertex {from_vertex}")
            else:
                graph[from_vertex][to_vertex]["price"] += v2_balance
                vertex_tightness[from_vertex] += v2_balance
                vertex_tightness[to_vertex] += v2_balance
                vc_result.append(to_vertex)
                # print(f"Adding vertex {to_vertex}")

        # print(vc_result)
        vc_cost = 0
        for i in vc_result:
            vc_cost += graph.nodes[i]["cost"]
        integral = integral_vc.IntegralVC()
        opt_cost = integral.vc_integral(graph)
        return round(vc_cost/opt_cost, 3)


if __name__ == "__main__":
    pvc = Pricing_VC()
    pvc.vc_pricing()