Ask Your Question
1

Lovasz number

asked 2011-09-10 16:26:05 -0500

G-Sage gravatar image

updated 2012-08-25 15:28:12 -0500

I found this link:

http://sage.math.washington.edu/tmp/s...

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
edit retag flag offensive close merge delete

Comments

It's conceivable that that is pure Python code?

kcrisman gravatar imagekcrisman ( 2012-08-27 03:44:08 -0500 )edit

@kcrisman Sorry, I don't know much. What would that tell us? :)

G-Sage gravatar imageG-Sage ( 2012-08-27 09:49:23 -0500 )edit
1

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.

kcrisman gravatar imagekcrisman ( 2012-08-28 03:29:44 -0500 )edit

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 .

slelievre gravatar imageslelievre ( 2016-07-20 04:01:39 -0500 )edit

3 answers

Sort by ยป oldest newest most voted
1

answered 2011-12-05 12:30:38 -0500

dstahlke gravatar image

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

edit flag offensive delete link more

Comments

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 gravatar imageJason Grout ( 2011-12-05 19:02:26 -0500 )edit

But YANAL. :)

kcrisman gravatar imagekcrisman ( 2011-12-06 02:00:59 -0500 )edit
1

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 gravatar imagekcrisman ( 2012-08-28 03:30:41 -0500 )edit

@kcrisman Wow, thanks a lot!

G-Sage gravatar imageG-Sage ( 2012-08-28 06:45:14 -0500 )edit
2

answered 2011-09-10 17:17:53 -0500

Jason Grout gravatar image

updated 2011-09-10 17:18:25 -0500

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.

edit flag offensive delete link more
1

answered 2011-09-10 16:47:51 -0500

kcrisman gravatar image

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.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

2 followers

Stats

Asked: 2011-09-10 16:26:05 -0500

Seen: 710 times

Last updated: Aug 25 '12