lovasz.py

import csv
import picos as pic
import cvxopt as cvx
import numpy as np

def main():

    def parse(name):
        with open(name, 'r') as fp:
            reader = csv.reader(fp, delimiter=',', skipinitialspace=True)
            for a, b in reader:
                yield int(a), int(b)

    edges = list(parse('johnson8-4-4.csv'))
    nvertices = max(map(max, edges)) + 1
    print '|V|={0}, |E|={1}'.format(nvertices, len(edges))

    p = pic.Problem()
    C = cvx.matrix(-1. * np.ones((nvertices, nvertices)))
    C = pic.new_param('C', C)
    X = p.add_variable('X', (nvertices, nvertices), vtype='symmetric')

    p.add_constraint( ('I' | X) == 1.)
    for i, j in edges:
        p.add_constraint(X[i, j] == 0.)

    p.add_constraint(X >> 0)
    p.set_objective('min', C | X)
    p.solve()


if __name__ == '__main__':
    main()