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))
It's conceivable that that is pure Python code?
@kcrisman Sorry, I don't know much. What would that tell us? :)
Try it with "python" selected in the notebook, not "sage". The problem is that cvxopt only takes very basic Python types for its lists, I guess. So when "Sage" types like `RealNumber`s come into play, cvxopt breaks. Using the program below with Sage tries to turn floats like `0.0` into "real numbers" like in Sage.
Note: the link in the question is no longer working, the current location for the corresponding page is:
http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_database.html .