Revision history [back]

Here you go. I've tested this against all of the graphs in the graph database. This code is adapted from someone's thesis which I found online. I cannot find the author's email address to ask if it can be made GPL or similar.

 import cvxopt.base
    import cvxopt.solvers
 # Adapted from Program 4.2, page 44, of the dissertation of Constantinos
    # Skarakis, http://keithbriggs.info/documents/Skarakis_MSc.pdf
    def lovasz_theta(G):
        '''Computes the Lovasz theta function for a graph.'''
 Gc = G.complement()
        n = Gc.num_verts()
        m = Gc.num_edges()
 # This case needs to be handled specially.
        if n == 1: return 1.0
 d = m+n
        c = -cvxopt.base.matrix([0.0](n-1) + [2.0](d-n))
        Xrow = [i(1+n) for i in xrange(n-1)] + \
            [b+an for (a, b, _w) in Gc.edge_iterator()]
        Xcol = range(n-1) + range(d-1)[n-1:]
        X = cvxopt.base.spmatrix(1.0, Xrow, Xcol, (nn, d-1))
        for i in xrange(n-1): X[nn-1, i] = -1.0
        sol = cvxopt.solvers.sdp(c, Gs=[-X], hs=[-cvxopt.base.matrix([0.0](nn-1) + [-1.0], (n,n))])
        v = 1.0 + cvxopt.base.matrix(-c, (1, d-1)) * sol['x']
 return v[0]
 # Some options I like to set.
    # http://abel.ee.ucla.edu/cvxopt/userguide/coneprog.html#algorithm-parameters
    cvxopt.solvers.options['show_progress'] = False
    cvxopt.solvers.options['abstol'] = float(1e-10)
    cvxopt.solvers.options['reltol'] = float(1e-10)
 #print lovasz_theta(graphs.CycleGraph(5))