Opened 6 years ago

Closed 6 years ago

#14525 closed defect (fixed)

cliquer does not like the empty graph

Reported by: azi Owned by: jason, ncohen, rlm
Priority: critical Milestone: sage-5.10
Component: graph theory Keywords:
Cc: ncohen Merged in: sage-5.10.rc1
Authors: Nico Van Cleemput Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

Stupid corner case but still worth fixing. Asking for the clique number of the empty graph blows Sage off.

sage: graphs.EmptyGraph().clique_number()
cliquer file graph.c: line 31: assertion failed: (n>0)
------------------------------------------------------------------------
/home/azi/sage-5.10.beta1/local/lib/libcsage.so(print_backtrace+0x31)[0x7fa2060bc7a0]
/home/azi/sage-5.10.beta1/local/lib/libcsage.so(sigdie+0x37)[0x7fa2060bc939]
/home/azi/sage-5.10.beta1/local/lib/libcsage.so(sage_signal_handler+0x15d)[0x7fa2060bc14b]
/lib/x86_64-linux-gnu/libpthread.so.0(+0x10060)[0x7fa20a089060]
/lib/x86_64-linux-gnu/libc.so.6(gsignal+0x35)[0x7fa2096813e5]
/lib/x86_64-linux-gnu/libc.so.6(abort+0x17b)[0x7fa209684b4b]
/home/azi/sage-5.10.beta1/local/lib/libcliquer.so(+0xa38a)[0x7fa1dc2be38a]
/home/azi/sage-5.10.beta1/local/lib/python2.7/site-packages/sage/graphs/cliquer.so(+0x39a6)[0x7fa1dc4cb9a6]
/home/azi/sage-5.10.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x5999)[0x7fa20a38aa19]
/home/azi/sage-5.10.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x822)[0x7fa20a38b9a2]
/home/azi/sage-5.10.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x45ed)[0x7fa20a38966d]
/home/azi/sage-5.10.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x822)[0x7fa20a38b9a2]
/home/azi/sage-5.10.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCode+0x32)[0x7fa20a38bad2]
/home/azi/sage-5.10.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x4749)[0x7fa20a3897c9]
/home/azi/sage-5.10.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x822)[0x7fa20a38b9a2]
/home/azi/sage-5.10.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x45ed)[0x7fa20a38966d]
/home/azi/sage-5.10.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x822)[0x7fa20a38b9a2]
/home/azi/sage-5.10.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x45ed)[0x7fa20a38966d]
/home/azi/sage-5.10.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x822)[0x7fa20a38b9a2]
/home/azi/sage-5.10.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x45ed)[0x7fa20a38966d]
/home/azi/sage-5.10.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x822)[0x7fa20a38b9a2]
/home/azi/sage-5.10.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x45ed)[0x7fa20a38966d]
/home/azi/sage-5.10.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x822)[0x7fa20a38b9a2]
/home/azi/sage-5.10.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x45ed)[0x7fa20a38966d]
/home/azi/sage-5.10.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x822)[0x7fa20a38b9a2]
/home/azi/sage-5.10.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x45ed)[0x7fa20a38966d]
/home/azi/sage-5.10.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x822)[0x7fa20a38b9a2]
/home/azi/sage-5.10.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCode+0x32)[0x7fa20a38bad2]
/home/azi/sage-5.10.beta1/local/lib/libpython2.7.so.1.0(PyRun_FileExFlags+0xaa)[0x7fa20a3ad46a]
/home/azi/sage-5.10.beta1/local/lib/libpython2.7.so.1.0(PyRun_SimpleFileExFlags+0xed)[0x7fa20a3adead]
/home/azi/sage-5.10.beta1/local/lib/libpython2.7.so.1.0(Py_Main+0xc22)[0x7fa20a3c3992]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xed)[0x7fa20966c30d]
python[0x4006d1]
------------------------------------------------------------------------
Attaching gdb to process id 13317.
GNU gdb (Ubuntu/Linaro 7.3-0ubuntu2) 7.3-2011.08
Copyright (C) 2011 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
For bug reporting instructions, please see:
<http://bugs.launchpad.net/gdb-linaro/>.
(gdb) Hangup detected on fd 0
error detected on stdin

Your system GDB is an old version that does not work with pipes
Install the gdb spkg (sage -f gdb) for enhanced tracebacks.
------------------------------------------------------------------------
Unhandled SIGABRT: An abort() occurred in Sage.
This probably occurred because a *compiled* component of Sage has a bug
in it and is not properly wrapped with sig_on(), sig_off(). You might
want to run Sage under gdb with 'sage -gdb' to debug this.
Sage will now terminate.
------------------------------------------------------------------------
/usr/local/bin/sage: line 135: 13317 Aborted                 "$SAGE_ROOT/spkg/bin/sage" "$@"

Simply checking if the supplied graph is empty is going to fix this for sure.

Attachments (2)

trac_14525_cliquer_empty.patch (1.5 KB) - added by nvcleemp 6 years ago.
As requested
trac_14525-rev.patch (775 bytes) - added by ncohen 6 years ago.

Download all attachments as: .zip

Change History (11)

comment:1 Changed 6 years ago by ncohen

I am an idiot -_-

#10756

Nathann

comment:2 Changed 6 years ago by nvcleemp

  • Status changed from new to needs_review

Nobody seemed to be working on this, so I quickly fixed it. I also fixed the method to get all maximum cliques.

I didn't add my name to the authors, since this is just a minor bug fix. I don't know the policy on this. I'm sure that I can be found through the versioning system, if at some point I need to be blamed for introducing a bug.

comment:3 Changed 6 years ago by ncohen

Why would you return [g.vertices()] when g.order() is 0 ? O_o

Wouldn't return [[]] do ? O_o

And even short bugfixes have authors, and even there the author is the one who writes the patch. Soooooooooooooooo :-)

Nathann

comment:4 Changed 6 years ago by nvcleemp

I actually copied the patch for #10756, which returns g.vertices() as a maximum clique when g.order() is 0. I'd be happy to change it to [[]], but maybe then I should also change the other method to return [] just to be consistent for all three methods.

comment:5 Changed 6 years ago by ncohen

If you can, it would be nice indeed :-)

Nathann

Changed 6 years ago by nvcleemp

As requested

comment:6 Changed 6 years ago by nvcleemp

btw, the tests actually test methods different from these functions but which use those functions. I guessed this was OK, because that was also the way it was done for max_clique().

comment:7 Changed 6 years ago by ncohen

  • Authors set to Nico Van Cleemput
  • Reviewers set to Nathann Cohen

Hmmmmmm... It is correct most of the time, because sage -coverage notices that the function's name is the same, but that does not work for all_max_clique ^^;

~/sage/sage/graphs$ sage -coverage cliquer.pyx 
------------------------------------------------------------------------
SCORE cliquer.pyx: 100.0% (4 of 4)

Possibly wrong (function name doesn't occur in doctests):
     * line 95: def all_max_clique(graph)
------------------------------------------------------------------------

I just uploaded a small patch that fixes that. If you agree with it, then you can set this ticket to positive_review :-)

Nathann

Changed 6 years ago by ncohen

comment:8 Changed 6 years ago by nvcleemp

  • Status changed from needs_review to positive_review

OK, looks ok and works for me.

comment:9 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.10.rc1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.