"""
ssp.py: model for the stable set problem

Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012
"""

from gurobipy import *

def ssp(V,E):
    """ssp -- model for the stable set problem
    Parameters:
        - V: set/list of nodes in the graph
        - E: set/list of edges in the graph
    Returns a model, ready to be solved.
    """
    model = Model("ssp")
    x = {}
    for i in V:
        x[i] = model.addVar(vtype="B", name="x(%s)"%i)        
    model.update()
    
    for (i,j) in E:
        model.addConstr(x[i] + x[j] <= 1, "Edge(%s,%s)"%(i,j))

    model.setObjective(quicksum(x[i] for i in V), GRB.MAXIMIZE)

    model.update()
    model.__data = x
    return model
            

import random
def make_data(n,prob):
    """make_data: prepare data for a random graph
    Parameters:
       - n: number of vertices
       - prob: probability of existence of an edge, for each pair of vertices
    Returns a tuple with a list of vertices and a list edges.
       """
    V = range(1,n+1)
    E = [(i,j) for i in V for j in V if i < j and random.random() < prob]
    return V,E


if __name__ == "__main__":
    random.seed(1)
    V,E = make_data(100,.5)

    model = ssp(V,E)
    model.optimize()
    print "Opt.value=",model.ObjVal
    x = model.__data
    print "maximum stable set:"
    print [i for i in V if x[i].X > 0.5]