1 | initial version |

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+a*n 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, (n*n, d-1))
for i in xrange(n-1): X[n*n-1, i] = -1.0
sol = cvxopt.solvers.sdp(c, Gs=[-X], hs=[-cvxopt.base.matrix([0.0]*(n*n-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))

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.