from pulp import *

class Graph():

    "The class Graph that encodes an undirected graph. For this implementation, the graph is represented as an Adjacency Matrix."
    "The graph is initialised as an empty graph (A_{ij}=0 for all i, j) with numNodes nodes. The nodeSet contains the indices of the nodes, namely [0, ..., numNodes]."
    "It has methods add_edge and delete_edge for adding and deleting edges. The __str__ method has been defined to print the Adjacency Matrix."

    def __init__(self, numNodes):
        self.numNodes = numNodes
        self.AdjacencyMatrix = [[0 for col in range(numNodes)] for row in range(numNodes)]
        self.nodeSet = set(i for i in range(numNodes))

    def __str__(self):
        return str(self.AdjacencyMatrix)

    def add_edge(self,node1, node2):
        self.AdjacencyMatrix[node1][node2] = 1
        self.AdjacencyMatrix[node2][node1] = 1

    def delete_edge(self,node1,node2):
        self.AdjacencyMatrix[node1][node2] = 0
        self.AdjacencyMatrix[node2][node1] = 0

import random

def randomGraph(numNodes,k):
    randGraph = Graph(numNodes)

    for node in randGraph.nodeSet:
        randNodes= random.sample(range(0, numNodes-1), k)
        for otherNode in randNodes:
            if randGraph.AdjacencyMatrix[node][otherNode] == 0:
                randGraph.add_edge(node,otherNode)

    return randGraph




inputGraph = Graph(8)
inputGraph.add_edge(0,1)
inputGraph.add_edge(0,3)
inputGraph.add_edge(0,5)

inputGraph.add_edge(1,2)

inputGraph.add_edge(2,4)
inputGraph.add_edge(2,7)

inputGraph.add_edge(3,6)

inputGraph.add_edge(4,7)

inputGraph.add_edge(5,6)

inputGraph.add_edge(6,7)



print(inputGraph)


def vertexCoverMILP(inputGraph):

    prob = LpProblem("VertexCover",LpMinimize)

    x = LpVariable.dicts("x",inputGraph.nodeSet,cat=LpBinary)

    prob += lpSum(x)

    for node1 in inputGraph.nodeSet:
        for node2 in inputGraph.nodeSet:
            if inputGraph.AdjacencyMatrix[node1][node2] == 1:
                prob+= x[node1] + x[node2] >=1

    prob.solve()

    # display objective function value
    print("number of vertices in solution : %s"%prob.objective.value())


    indSet = set()
    # display solution
    for node in inputGraph.nodeSet:
        if pulp.value(x[node]) > 0.99:
            indSet.add(node)

    return indSet

testGraph = randomGraph(500,4)

print(vertexCoverMILP(testGraph))