Problem with lovasz theta number of a graph

[Sihuang Hu]

Hi guys,

When I try to compute the lovasz theta number of some graph, it says that ValueError: could not convert string to float: failed.:

G = graphs.CycleGraph(7)
V = Set(G.vertices())
L = []
for s in V.subsets():
  L.append(G.subgraph(s))

L[68].lovasz_theta()
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-53-0ad2fb49c2b1> in <module>()
----> 1 L[Integer(68)].lovasz_theta()

/home/shhu/Documents/SageMath/local/lib/python2.7/site-packages/sage/graphs/lovasz_theta.pyc in lovasz_theta(graph)
     78     tf.close()
     79     lines = subprocess.check_output([os.path.join(SAGE_LOCAL, 'bin', 'theta'), tf_name])
---> 80     return float(lines.split()[-1])

ValueError: could not convert string to float: failed.

Thanks in advance!

[Vincent Delecroix]

The error you get is quite strange. On my computer with sage-7.1 I got

sage: graphs.CycleGraph(7).lovasz_theta()
Traceback (most recent call last):
...
PackageNotFoundError: the package 'csdp' was not found. You can install
it by running 'sage -i csdp' in a shell

Which is very explicit about what to do... could you install the csdp
package and try again?

On 10/05/16 06:58, Sihuang Hu wrote:
> Hi guys,
>
> When I try to compute the lovasz theta number of some graph, it says that
>

> *ValueError: could not convert string to float: failed.:*G =

[Sihuang Hu]

Thanks for the comments.
I have installed package 'csdp' before. I got this error after I installed it.

在 2016年5月10日星期二 UTC+3下午3:32:59，vdelecroix写道：

[Dima Pasechnik]

What is your L[68] ?

This is probably something like a graph without edges...

On Tuesday, May 10, 2016 at 1:53:17 PM UTC+1, Sihuang Hu wrote:

Thanks for the comments.
I have installed package 'csdp' before. I got this error after I installed it.

在 2016年5月10日星期二 UTC+3下午3:32:59，vdelecroix写道：

The error you get is quite strange. On my computer with sage-7.1 I got

sage: graphs.CycleGraph(7).lovasz_theta()

Traceback (most recent call last): ur ...

[Sihuang Hu]

The adjacency matrix of the graph is

[0 1 0 0]
[1 0 0 0]
[0 0 0 1]
[0 0 1 0]


在 2016年5月10日星期二 UTC+3下午4:30:06，Dima Pasechnik写道：

[Dima Pasechnik]

all this works for me just fine:

sage: g=Graph([[0,1],[2,3]])

sage: g.lovasz_theta()

2.0

sage: G = graphs.CycleGraph(7)

sage: V = Set(G.vertices())

sage: L = []

sage: for s in V.subsets():

....:       L.append(G.subgraph(s))

....:     

sage: L[68].lovasz_theta()

2.0

Can you try the following:

sage: g=Graph([[0,1],[2,3]])

sage: g.lovasz_theta()

[Sihuang Hu]

It didn't work for me. :(

sage: g=Graph([[0,1],[2,3]])
sage: g.lovasz_theta()

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)

<ipython-input-2-1d4d0397a94f> in <module>()
----> 1 g.lovasz_theta()

/home/shhu/Documents/SageMath/local/lib/python2.7/site-packages/sage/graphs/lovasz_theta.pyc in lovasz_theta(graph)
     78     tf.close()
     79     lines = subprocess.check_output([os.path.join(SAGE_LOCAL, 'bin', 'theta'), tf_name])
---> 80     return float(lines.split()[-1])

ValueError: could not convert string to float: failed.

在 2016年5月10日星期二 UTC+3下午6:33:50，Dima Pasechnik写道：

[Dima Pasechnik]

and on other graphs either?

(e.g. on graphs.CycleGraph(7))

Start sage prompt (sage -sh) and check that you have the program called theta available:

$ sage -sh

Starting subshell with Sage environment variables set.  Don't forget

to exit when you are done.  Beware:

 * Do not do anything with other copies of Sage on your system.

 * Do not use this for installing Sage packages using "sage -i" or for

   running "make" at Sage's root directory.  These should be done

   outside the Sage shell.

Bypassing shell configuration files...

Note: SAGE_ROOT=/home/dima/software/sage

(sage-sh) dima@dimpase:~$ theta 

Usage: 

theta <graph> 

(sage-sh) dima@dimpase:~$ 

-------------

if you don't have it then reinstall csdp:

sage -f csdp

[Sihuang Hu]

$sage -sh

Starting subshell with Sage environment variables set.  Don't forget
to exit when you are done.  Beware:
 * Do not do anything with other copies of Sage on your system.
 * Do not use this for installing Sage packages using "sage -i" or for
   running "make" at Sage's root directory.  These should be done
   outside the Sage shell.

Bypassing shell configuration files...

Note: SAGE_ROOT=/home/shhu/Documents/SageMath
(sage-sh) shhu@shhu-ee-tau:Program$ theta
Usage:

theta <graph>
-----------------------------------------------------------------
I have 'csdp' installed, and this theta function works for many other graphs.
However, it doesn't work for this graph...


在 2016年5月10日星期二 UTC+3下午7:45:24，Dima Pasechnik写道：

[Dima Pasechnik]

Please edit /home/shhu/Documents/SageMath/local/lib/python2.7/site-packages/sage/graphs/lovasz_theta.py

to insert

print "output was: ", lines

after "lines = subprocess.check_output(...)"

remove /home/shhu/Documents/SageMath/local/lib/python2.7/site-packages/sage/graphs/lovasz_theta.pyc

and start Sage again.

Post the output of the result. Hopefully it will explain (perhaps it does return some 'NaN' for some

reason or something like this...)

-------------------------------------------------------

I presume you run Linux. Which version, what hadware? What Sage version?

Post the output of 

cat /proc/cpuinfo 

The next step would be to create the input file  for this graph for the executable theta and run it in the shell, 

without invoking Sage.

[Dima Pasechnik]

here is the input for theta executable:

  4

  2

  1 2

  3 4

(also attached)

save it to a file named, say, 2k2, fire up "sage -sh"

and run 

theta 2k2

I get 

$ theta 2k2 

Graph is of size 4 2 

C block 1, blocksize, 4

Checking constraint 1 

Checking constraint 2 

Checking constraint 3 

Iter:  0 Ap: 0.00e+00 Pobj:  1.0666667e+02 Ad: 0.00e+00 Dobj:  0.0000000e+00 

[... edited]

Iter: 15 Ap: 1.00e+00 Pobj:  2.0000000e+00 Ad: 9.00e-01 Dobj:  2.0000000e+00 

Success: SDP solved

Primal objective value: 2.0000000e+00 

Dual objective value: 2.0000000e+00 

Relative primal infeasibility: 1.11e-16 

Relative dual infeasibility: 2.12e-10 

Real Relative Gap: 8.56e-10 

XZ Relative Gap: 9.63e-10 

DIMACS error measures: 1.11e-16 0.00e+00 5.30e-10 0.00e+00 8.56e-10 9.63e-10

The Lovasz Theta Number is 2.0000000e+00 

Does this work for you?

[Sihuang Hu]

I just did what you suggested, and it didn't work. I got those messages:

(sage-sh) shhu@shhu-ee-tau:~$ theta 2k2
Segmentation fault (core dumped)

My Cpu information is attached.
Ubuntu 14.04LTS
SageMath Version 7.0, Release Date: 2016-01-19


在 2016年5月10日星期二 UTC+3下午11:55:55，Dima Pasechnik写道：

[Sihuang Hu]

My Cpu information is attached...

在 2016年5月11日星期三 UTC+3下午2:58:43，Sihuang Hu写道：

[Dima Pasechnik]

It does work on some graphs, still, right?

It's a high-end relatively new CPU, perhaps Atlas and/or gcc has a problem with it?

Can you post the output of 'ldd theta', i.e.

(sage-sh) dimpase@clpc171:sage$ ldd `which theta`

linux-vdso.so.1 (0x00007ffd2c34f000)

libsdp.so.0 => /home/scratch/dimpase/sage/sage/local/lib/libsdp.so.0 (0x00007f74f6ec3000)

liblapack.so.3 => /home/scratch/dimpase/sage/sage/local/lib/liblapack.so.3 (0x00007f74f65fc000)

libcblas.so.3 => /home/scratch/dimpase/sage/sage/local/lib/libcblas.so.3 (0x00007f74f63da000)

libf77blas.so.3 => /home/scratch/dimpase/sage/sage/local/lib/libf77blas.so.3 (0x00007f74f61b8000)

libatlas.so.3 => /home/scratch/dimpase/sage/sage/local/lib/libatlas.so.3 (0x00007f74f5b2a000)

libgfortran.so.3 => /lib64/libgfortran.so.3 (0x00007f74f57ca000)

libquadmath.so.0 => /lib64/libquadmath.so.0 (0x00007f74f558b000)

libm.so.6 => /lib64/libm.so.6 (0x00007f74f5288000)

libc.so.6 => /lib64/libc.so.6 (0x00007f74f4ec7000)

libpthread.so.0 => /lib64/libpthread.so.0 (0x00007f74f4caa000)

libgcc_s.so.1 => /lib64/libgcc_s.so.1 (0x00007f74f4a92000)

/lib64/ld-linux-x86-64.so.2 (0x000055f7fadea000)

as well as the CSDP installation log:

SAGE_ROOT/logs/pkgs/csdp-6.2.log

[Sihuang Hu]

Yes, it still works on many other graphs.
---------------------------------------------------------------------------------------------------------------------------
(sage-sh) shhu@shhu-ee-tau:~$ ldd `which theta`
    linux-vdso.so.1 =>  (0x00007ffea69d6000)
    libsdp.so.0 => /home/shhu/Documents/SageMath/local/lib/libsdp.so.0 (0x00007f9e721e9000)
    liblapack.so.3 => /home/shhu/Documents/SageMath/local/lib/liblapack.so.3 (0x00007f9e71907000)
    libcblas.so.3 => /home/shhu/Documents/SageMath/local/lib/libcblas.so.3 (0x00007f9e716e3000)
    libf77blas.so.3 => /home/shhu/Documents/SageMath/local/lib/libf77blas.so.3 (0x00007f9e714c2000)
    libatlas.so.3 => /home/shhu/Documents/SageMath/local/lib/libatlas.so.3 (0x00007f9e70e91000)
    libgfortran.so.3 => /home/shhu/Documents/SageMath/local/lib/libgfortran.so.3 (0x00007f9e70b73000)
    libquadmath.so.0 => /home/shhu/Documents/SageMath/local/lib/libquadmath.so.0 (0x00007f9e70936000)
    libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x00007f9e70615000)
    libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f9e7024f000)
    libpthread.so.0 => /lib/x86_64-linux-gnu/libpthread.so.0 (0x00007f9e70031000)
    libgcc_s.so.1 => /home/shhu/Documents/SageMath/local/lib/libgcc_s.so.1 (0x00007f9e6fe1b000)
    /lib64/ld-linux-x86-64.so.2 (0x00005609d1eac000)
------------------------------------------------------------------------------------------------------------------------------
The CSDP log is attached.

Thanks for your kindly help!

在 2016年5月11日星期三 UTC+3下午4:43:04，Dima Pasechnik写道：

[Dima Pasechnik]

Have you built Sage from source? If not, it could happen, in principle, that lapack/atlas/blas shipped 

do not quite work on your system...

If you built it from source, did you do anything special to build Atlas in particular?

You can also try building csdp completely separately from Sage, using Ubuntu system-supplied

libraries, and see whether theta works.

Namely, you can clone it from https://github.com/dimpase/csdp

and build as described on that page.

Sorry for not being able to help more, but as long we cannot reproduce

the error, it's hard to tell what exactly is wrong.

And of course you can use gdb to debug theta - for this you need to make

sure it's compiled with right switches, of course...

[Sihuang Hu]

I think I downloaded the binaries. Thanks for your suggestions. I will try it.

在 2016年5月11日星期三 UTC+3下午6:14:37，Dima Pasechnik写道：

[Dima Pasechnik]

On Wednesday, May 11, 2016 at 6:10:52 PM UTC+1, Sihuang Hu wrote:

I think I downloaded the binaries. Thanks for your suggestions. I will try it.

well, you might try Sage 7.1 binary, perhaps it would work better...

(or build from source, on such a machine it won't take much time, perhaps 3-4 hours)

It would be good to get to the root cause of this, just to make sure that our way of building Sage binaries

which should run on any CPU is correct.

[Dima Pasechnik]

and what does 'ldd /home/shhu/Documents/SageMath/local/lib/libsdp.so.0' say?

[Sihuang Hu]

It shows:
shhu-ee-tau ~: ldd ~/Documents/SageMath/local/lib/libsdp.so.0
    linux-vdso.so.1 =>  (0x00007ffdeb3b0000)
    liblapack.so.3 => /home/shhu/Documents/SageMath/local/lib/liblapack.so.3 (0x00007fea93a69000)
    libcblas.so.3 => /home/shhu/Documents/SageMath/local/lib/libcblas.so.3 (0x00007fea93846000)
    libf77blas.so.3 => /home/shhu/Documents/SageMath/local/lib/libf77blas.so.3 (0x00007fea93624000)
    libatlas.so.3 => /home/shhu/Documents/SageMath/local/lib/libatlas.so.3 (0x00007fea92ff3000)
    libgfortran.so.3 => /home/shhu/Documents/SageMath/local/lib/libgfortran.so.3 (0x00007fea92cd6000)
    libquadmath.so.0 => /home/shhu/Documents/SageMath/local/lib/libquadmath.so.0 (0x00007fea92a98000)
    libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x00007fea92776000)
    libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007fea923b1000)
    libpthread.so.0 => /lib/x86_64-linux-gnu/libpthread.so.0 (0x00007fea92192000)
    libgcc_s.so.1 => /home/shhu/Documents/SageMath/local/lib/libgcc_s.so.1 (0x00007fea91f7c000)
    /lib64/ld-linux-x86-64.so.2 (0x000055d4b1ff6000)


在 2016年5月12日星期四 UTC+3上午11:11:05，Dima Pasechnik写道：

[Sihuang Hu]

I installed sage 7.1 from source codes, and now it works perfectly.
Thanks very much!

在 2016年5月12日星期四 UTC+3上午11:14:38，Sihuang Hu写道：