Bug in modular_decomposition

[ncohen]

Paulo Seijas reported the following bug on sage-support [1]

sage: P = Graph('Dl_')
sage: P.is_prime()
True

It can be easily fixed by just updating the code with upstream, as it looks like the bug has been solved since our last update.

That's all this patch does.

Nathann

[1] ​https://groups.google.com/forum/?fromgroups=#!topic/sage-support/Iha5__c_h44

Apply: 13744_rebased.patch​

[robertwb]

Verified that this is the latest version of the code, and the test passes. Why is this not an spkg? (I suppose it is rather tiny...)

[ncohen]

Yep, that's the reason... I agree that making it a spkg would be cleaner, but it has only one file and it i really easier to deal with like that ... To be honest if somebody comes in and say very loud "make it a spkg" I will, but I really feel that it's just sparing everybody additonal work the way it is.

Thank you for the review !

Nathann

[vbraun]

Is there anybody who still believes that non-English variable/function names are a good idea? Only in France ;-)

Since "upstream" is just a C file without anything (not even a makefile) I don't see any point in making it a spkg.

[ncohen]

Is there anybody who still believes that non-English variable/function names are a good idea? Only in France ;-)

Come ooooooooooon.. At least there are no accents in the function's name:-P

And it is nice sometimes to name a list "liste", because list is a Python keyword :-P

Since "upstream" is just a C file without anything (not even a makefile) I don't see any point in making it a spkg.

Well, just to emphasize that it is some external code, and that it hasn't been reviewed by Sage developpers... That's the normal procedures, but I believe less and less in procedures and laws these days :-P

Nathann

[vbraun]

Replying to ncohen:

Come ooooooooooon.. At least there are no accents in the function's name:-P

Possible, though for that you would have to compile with -fextended-identifiers and use \uNNNN escapes instead of accented characters...

And it is nice sometimes to name a list "liste", because list is a Python keyword :-P

And the spelling works for French & German!

[jdemeyer]

On sage.math (64-bit Linux x86_64):

sage -t  -force_lib devel/sage/sage/graphs/modular_decomposition/modular_decomposition.pyx
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libcsage.so(print_backtrace+0x31)[0x2ba5db141207]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libcsage.so(sigdie+0x14)[0x2ba5db141239]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libcsage.so(sage_signal_handler+0x216)[0x2ba5db140e16]
/lib/libpthread.so.0[0x2ba5d90657d0]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/python/site-packages/sage/graphs/modular_decomposition/modular_decomposition.so(algo2+0x459)[0x2ba607191f09]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/python/site-packages/sage/graphs/modular_decomposition/modular_decomposition.so(decomposition_modulaire+0x67)[0x2ba607192e97]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/python/site-packages/sage/graphs/modular_decomposition/modular_decomposition.so[0x2ba6071943e9]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x5ed8)[0x2ba5d8d5be98]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x855)[0x2ba5d8d5cfb5]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCode+0x32)[0x2ba5d8d5d0f2]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x515f)[0x2ba5d8d5b11f]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x855)[0x2ba5d8d5cfb5]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0[0x2ba5d8cdf9bc]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyObject_Call+0x53)[0x2ba5d8cb7bc3]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0[0x2ba5d8cc530f]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyObject_Call+0x53)[0x2ba5d8cb7bc3]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x3fcd)[0x2ba5d8d59f8d]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x855)[0x2ba5d8d5cfb5]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x5420)[0x2ba5d8d5b3e0]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x855)[0x2ba5d8d5cfb5]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0[0x2ba5d8cdf9bc]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyObject_Call+0x53)[0x2ba5d8cb7bc3]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0[0x2ba5d8cc530f]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyObject_Call+0x53)[0x2ba5d8cb7bc3]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x3fcd)[0x2ba5d8d59f8d]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x855)[0x2ba5d8d5cfb5]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x5420)[0x2ba5d8d5b3e0]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x855)[0x2ba5d8d5cfb5]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0[0x2ba5d8cdfab3]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyObject_Call+0x53)[0x2ba5d8cb7bc3]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0[0x2ba5d8cc530f]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyObject_Call+0x53)[0x2ba5d8cb7bc3]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x3fcd)[0x2ba5d8d59f8d]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x855)[0x2ba5d8d5cfb5]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x5420)[0x2ba5d8d5b3e0]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x855)[0x2ba5d8d5cfb5]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x5420)[0x2ba5d8d5b3e0]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x855)[0x2ba5d8d5cfb5]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x5420)[0x2ba5d8d5b3e0]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x855)[0x2ba5d8d5cfb5]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCode+0x32)[0x2ba5d8d5d0f2]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyRun_FileExFlags+0xb0)[0x2ba5d8d7f790]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(PyRun_SimpleFileExFlags+0xdf)[0x2ba5d8d8022f]
/release/buildbot/sage/sage-1/sage_binary/build/sage-5.6.beta1/local/lib/libpython2.7.so.1.0(Py_Main+0xbe5)[0x2ba5d8d93845]
/lib/libc.so.6(__libc_start_main+0xf4)[0x2ba5d991a1f4]
python[0x400619]

------------------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault 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.
------------------------------------------------------------------------

[jdemeyer]

On bsd (OS X 10.6 x86_64):

sage -t  --long -force_lib devel/sage/sage/graphs/modular_decomposition/modular_decomposition.pyx
**********************************************************************
File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-5.6.beta1/devel/sage-main/sage/graphs/modular_decomposition/modular_decomposition.pyx", line 87:
    sage: modular_decomposition(g)
Expected:
    ('Serie', [0, ('Parallel', [5, ('Serie', [1, 4, 3, 2]), 6])])
Got:
    ('Serie', [0, 5, ('Parallel', [('Serie', [1, 4, 3, 2]), 6])])
**********************************************************************

[ncohen]

T_T

And it still passes all tests on my machine.... :-/

Nathann

[jdemeyer]

Well, I still get the crash on sage.math, although not always.

[jdemeyer]

Currently, I don't manage to reproduce the problem so I'm putting back positive review for now.

[jdemeyer]

On bsd (OS X 10.6):

sage -t  --long -force_lib devel/sage/sage/graphs/graph.py
**********************************************************************
File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-5.7.beta0/devel/sage-main/sage/graphs/graph.py", line 5282:
    sage: graphs.BullGraph().modular_decomposition()
Expected:
    ('Prime', [3, 4, 0, 1, 2])
Got:
    ('Prime', [('Parallel', [3, 4]), 0, 1, 2])
**********************************************************************
File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-5.7.beta0/devel/sage-main/sage/graphs/graph.py", line 5296:
    sage: g.modular_decomposition()
Expected:
    ('Serie', [0, ('Parallel', [5, ('Serie', [1, 4, 3, 2]), 6])])
Got:
    ('Serie', [0, 5, ('Parallel', [('Serie', [1, 4, 3, 2]), 6])])
**********************************************************************

sage -t  --long -force_lib devel/sage/sage/graphs/modular_decomposition/modular_decomposition.pyx
**********************************************************************
File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-5.7.beta0/devel/sage-main/sage/graphs/modular_decomposition/modular_decomposition.pyx", line 87:
    sage: modular_decomposition(g)
Expected:
    ('Serie', [0, ('Parallel', [5, ('Serie', [1, 4, 3, 2]), 6])])
Got:
    ('Serie', [0, 5, ('Parallel', [('Serie', [1, 4, 3, 2]), 6])])
**********************************************************************

[ncohen]

On my machine these doctests do not break, and the results that you get are wrong -_-

I'll forward this to the owner. With some luck it will point him toward the memory problems that you had before :-/

Nathann

[jdemeyer]

It still crashes randomly on some systems...

[ncohen]

With a branch...

Nathann

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​61e7f47

trac #13744: Bug in modular_decomposition

[leif]

Ping...

[ncohen]

Oh right.

To be closed as wontfix, as the new code is still incorrect and triggers segfault on mac OS X (see #17950)

[ncohen]

Arg no.. I can't do that, as this is the ticket linked with the stopgap. Leif, what did you ping this ticket for ?

[leif]

Replying to ncohen:

Leif, what did you ping this ticket for ?

I thought you'd rebase it on #17950, then fixing the invalid array accesses you discovered, which would probably also fix the issues on MacOS X.

(I just noticed that the "current" modular decomposition code in Sage doesn't contain those parts -- they're apparently in the newer code you were going to add here.)

[ncohen]

I thought you'd rebase it on #17950, then fixing the invalid array accesses you discovered, which would probably also fix the issues on MacOS X.

I do not know how to fix this invalid array access. I seems to be the problem, but I did not write that code myself and what I did yesterday is remind it to the authors. Hoping that they will do something about it.

Nathann

[jmantysalo]

CC'ing myself because of #19215.

[jdemeyer]

See also #22281.

[dimpase]

The work on fixing this issue will be completed on #13744.

[dimpase]

this should be closed now, as #23487 is done.

[jmantysalo]

Replying to dimpase:

this should be closed now, as #23487 is done.

Volker closes wontfix-tickets from time to time, maybe about once per release.