ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 20 Jul 2016 11:01:39 +0200Lovasz numberhttps://ask.sagemath.org/question/8313/lovasz-number/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 listSat, 10 Sep 2011 23:26:05 +0200https://ask.sagemath.org/question/8313/lovasz-number/Comment by slelievre for <p>I found this link:</p>
<p><a href="http://sage.math.washington.edu/tmp/sage-2.8.12.alpha0/doc/ref/module-sage.graphs.graph-database.html">http://sage.math.washington.edu/tmp/s...</a></p>
<p>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???</p>
<p>Thanks</p>
<p><strong>BUMP:</strong> 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 :)</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/8313/lovasz-number/?comment=34152#post-id-34152Note: 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](http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_database.html) .Wed, 20 Jul 2016 11:01:39 +0200https://ask.sagemath.org/question/8313/lovasz-number/?comment=34152#post-id-34152Comment by G-Sage for <p>I found this link:</p>
<p><a href="http://sage.math.washington.edu/tmp/sage-2.8.12.alpha0/doc/ref/module-sage.graphs.graph-database.html">http://sage.math.washington.edu/tmp/s...</a></p>
<p>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???</p>
<p>Thanks</p>
<p><strong>BUMP:</strong> 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 :)</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/8313/lovasz-number/?comment=19161#post-id-19161@kcrisman Sorry, I don't know much. What would that tell us? :)Mon, 27 Aug 2012 16:49:23 +0200https://ask.sagemath.org/question/8313/lovasz-number/?comment=19161#post-id-19161Comment by kcrisman for <p>I found this link:</p>
<p><a href="http://sage.math.washington.edu/tmp/sage-2.8.12.alpha0/doc/ref/module-sage.graphs.graph-database.html">http://sage.math.washington.edu/tmp/s...</a></p>
<p>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???</p>
<p>Thanks</p>
<p><strong>BUMP:</strong> 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 :)</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/8313/lovasz-number/?comment=19167#post-id-19167It's conceivable that that is pure Python code?Mon, 27 Aug 2012 10:44:08 +0200https://ask.sagemath.org/question/8313/lovasz-number/?comment=19167#post-id-19167Comment by kcrisman for <p>I found this link:</p>
<p><a href="http://sage.math.washington.edu/tmp/sage-2.8.12.alpha0/doc/ref/module-sage.graphs.graph-database.html">http://sage.math.washington.edu/tmp/s...</a></p>
<p>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???</p>
<p>Thanks</p>
<p><strong>BUMP:</strong> 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 :)</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/8313/lovasz-number/?comment=19156#post-id-19156Try 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.Tue, 28 Aug 2012 10:29:44 +0200https://ask.sagemath.org/question/8313/lovasz-number/?comment=19156#post-id-19156Answer by kcrisman for <p>I found this link:</p>
<p><a href="http://sage.math.washington.edu/tmp/sage-2.8.12.alpha0/doc/ref/module-sage.graphs.graph-database.html">http://sage.math.washington.edu/tmp/s...</a></p>
<p>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???</p>
<p>Thanks</p>
<p><strong>BUMP:</strong> 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 :)</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/8313/lovasz-number/?answer=12636#post-id-12636Here's a more [updated link](http://sagemath.org/doc/reference/sage/graphs/graph_database.html) 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.Sat, 10 Sep 2011 23:47:51 +0200https://ask.sagemath.org/question/8313/lovasz-number/?answer=12636#post-id-12636Answer by Jason Grout for <p>I found this link:</p>
<p><a href="http://sage.math.washington.edu/tmp/sage-2.8.12.alpha0/doc/ref/module-sage.graphs.graph-database.html">http://sage.math.washington.edu/tmp/s...</a></p>
<p>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???</p>
<p>Thanks</p>
<p><strong>BUMP:</strong> 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 :)</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/8313/lovasz-number/?answer=12637#post-id-12637I 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.Sun, 11 Sep 2011 00:17:53 +0200https://ask.sagemath.org/question/8313/lovasz-number/?answer=12637#post-id-12637Answer by dstahlke for <p>I found this link:</p>
<p><a href="http://sage.math.washington.edu/tmp/sage-2.8.12.alpha0/doc/ref/module-sage.graphs.graph-database.html">http://sage.math.washington.edu/tmp/s...</a></p>
<p>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???</p>
<p>Thanks</p>
<p><strong>BUMP:</strong> 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 :)</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/8313/lovasz-number/?answer=12973#post-id-12973Here 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.
<code>
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))
</code>
Mon, 05 Dec 2011 19:30:38 +0100https://ask.sagemath.org/question/8313/lovasz-number/?answer=12973#post-id-12973Comment by kcrisman for <p>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.</p>
<p><code></code></p><code>
<p>import cvxopt.base
import cvxopt.solvers</p>
<p># 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.'''</p>
<p>Gc = G.complement()
n = Gc.num_verts()
m = Gc.num_edges()</p>
<p># This case needs to be handled specially.
if n == 1: return 1.0</p>
<p>d = m+n
c = -cvxopt.base.matrix([0.0]<em>(n-1) + [2.0]</em>(d-n))
Xrow = [i<em>(1+n) for i in xrange(n-1)] + \
[b+a</em>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<em>n, d-1))
for i in xrange(n-1): X[n</em>n-1, i] = -1.0
sol = cvxopt.solvers.sdp(c, Gs=[-X], hs=[-cvxopt.base.matrix([0.0]<em>(n</em>n-1) + [-1.0], (n,n))])
v = 1.0 + cvxopt.base.matrix(-c, (1, d-1)) * sol['x']</p>
<p>return v[0]</p>
<p># 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)</p>
<p>#print lovasz_theta(graphs.CycleGraph(5))</p>
</code><p><code></code></p>
https://ask.sagemath.org/question/8313/lovasz-number/?comment=20749#post-id-20749But YANAL. :)Tue, 06 Dec 2011 09:00:59 +0100https://ask.sagemath.org/question/8313/lovasz-number/?comment=20749#post-id-20749Comment by kcrisman for <p>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.</p>
<p><code></code></p><code>
<p>import cvxopt.base
import cvxopt.solvers</p>
<p># 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.'''</p>
<p>Gc = G.complement()
n = Gc.num_verts()
m = Gc.num_edges()</p>
<p># This case needs to be handled specially.
if n == 1: return 1.0</p>
<p>d = m+n
c = -cvxopt.base.matrix([0.0]<em>(n-1) + [2.0]</em>(d-n))
Xrow = [i<em>(1+n) for i in xrange(n-1)] + \
[b+a</em>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<em>n, d-1))
for i in xrange(n-1): X[n</em>n-1, i] = -1.0
sol = cvxopt.solvers.sdp(c, Gs=[-X], hs=[-cvxopt.base.matrix([0.0]<em>(n</em>n-1) + [-1.0], (n,n))])
v = 1.0 + cvxopt.base.matrix(-c, (1, d-1)) * sol['x']</p>
<p>return v[0]</p>
<p># 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)</p>
<p>#print lovasz_theta(graphs.CycleGraph(5))</p>
</code><p><code></code></p>
https://ask.sagemath.org/question/8313/lovasz-number/?comment=19155#post-id-19155Note 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. Tue, 28 Aug 2012 10:30:41 +0200https://ask.sagemath.org/question/8313/lovasz-number/?comment=19155#post-id-19155Comment by G-Sage for <p>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.</p>
<p><code></code></p><code>
<p>import cvxopt.base
import cvxopt.solvers</p>
<p># 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.'''</p>
<p>Gc = G.complement()
n = Gc.num_verts()
m = Gc.num_edges()</p>
<p># This case needs to be handled specially.
if n == 1: return 1.0</p>
<p>d = m+n
c = -cvxopt.base.matrix([0.0]<em>(n-1) + [2.0]</em>(d-n))
Xrow = [i<em>(1+n) for i in xrange(n-1)] + \
[b+a</em>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<em>n, d-1))
for i in xrange(n-1): X[n</em>n-1, i] = -1.0
sol = cvxopt.solvers.sdp(c, Gs=[-X], hs=[-cvxopt.base.matrix([0.0]<em>(n</em>n-1) + [-1.0], (n,n))])
v = 1.0 + cvxopt.base.matrix(-c, (1, d-1)) * sol['x']</p>
<p>return v[0]</p>
<p># 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)</p>
<p>#print lovasz_theta(graphs.CycleGraph(5))</p>
</code><p><code></code></p>
https://ask.sagemath.org/question/8313/lovasz-number/?comment=19153#post-id-19153@kcrisman Wow, thanks a lot!Tue, 28 Aug 2012 13:45:14 +0200https://ask.sagemath.org/question/8313/lovasz-number/?comment=19153#post-id-19153Comment by Jason Grout for <p>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.</p>
<p><code></code></p><code>
<p>import cvxopt.base
import cvxopt.solvers</p>
<p># 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.'''</p>
<p>Gc = G.complement()
n = Gc.num_verts()
m = Gc.num_edges()</p>
<p># This case needs to be handled specially.
if n == 1: return 1.0</p>
<p>d = m+n
c = -cvxopt.base.matrix([0.0]<em>(n-1) + [2.0]</em>(d-n))
Xrow = [i<em>(1+n) for i in xrange(n-1)] + \
[b+a</em>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<em>n, d-1))
for i in xrange(n-1): X[n</em>n-1, i] = -1.0
sol = cvxopt.solvers.sdp(c, Gs=[-X], hs=[-cvxopt.base.matrix([0.0]<em>(n</em>n-1) + [-1.0], (n,n))])
v = 1.0 + cvxopt.base.matrix(-c, (1, d-1)) * sol['x']</p>
<p>return v[0]</p>
<p># 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)</p>
<p>#print lovasz_theta(graphs.CycleGraph(5))</p>
</code><p><code></code></p>
https://ask.sagemath.org/question/8313/lovasz-number/?comment=20751#post-id-20751nice! 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.Tue, 06 Dec 2011 02:02:26 +0100https://ask.sagemath.org/question/8313/lovasz-number/?comment=20751#post-id-20751