Lovasz number

Question

I found this link:

http://sage.math.washington.edu/tmp/sage-2.8.12.alpha0/doc/ref/module-sage.graphs.graph-database.html

It talks about a graph database. My question isn't really about this database, but the fact that this database has the Lovasz number makes me wonder if Sage can calculate the Lovasz number of a graph???

Thanks

BUMP: Did any one get the code (in the answer below) to work? It calls an error when I run it. And, I have no idea what the code is doing so I can't really figure out the error :)

File "/tmp/tmp0_qsPp/___code___.py", line 21, in lovasz_theta
    c = -cvxopt.base.matrix([_sage_const_0p0 ]*(n-_sage_const_1 ) + [_sage_const_2p0 ]*(d-n))
TypeError: invalid type in list

Accepted Answer

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))

nice! if we get permission to release it in GPL, can you post a patch to trac? On the other hand, as I understand it, short pieces of code are not copyrightable. Many projects say that it's okay to copy small bits of code, like less than 10 lines. It looks like this function is about 10 lines long, so it's probably okay to include it in Sage.
Jason Grout (Dec 06 '11)
Note that this is probably pure Python. A workaround I found when searching for the error @G-Sage got is to do RealNumber = float ; Integer = int after importing the modules, if you wanted to do this inside of Sage.
kcrisman (Aug 28 '12)

Answer 2

I did not use Sage to calculate the lovasz numbers in the database (I calculated this data before I knew about Sage!). It was a long time ago, and I couldn't find the program I used to calculate the information when I looked just now. It was probably at least related to one of the popular free semidefinite programming toolboxes from several years ago. IIRC, one of the sdp toolkits came with a theta function example program or something.

Answer 3

Here's a more updated link for this, which should stay up-to-date.

My very uneducated guess is that you can USE Sage to do this, but that it's not built in. Hopefully Jason Grout will see this - he is the source of this database, at least in part.

Lovasz number

3 Answers:

Your answer

Question tools

Tags:

Stats:

Related questions