Opened 8 years ago
Closed 3 years ago
#13744 closed defect (wontfix)
Bug in modular_decomposition
Reported by:  ncohen  Owned by:  jason, ncohen, rlm 

Priority:  major  Milestone:  sageduplicate/invalid/wontfix 
Component:  graph theory  Keywords:  
Cc:  azi, jmantysalo  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Robert Bradshaw, Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  u/ncohen/13744 (Commits, GitHub, GitLab)  Commit:  61e7f47c28907a604e19513ebd3ea8d505ed4103 
Dependencies:  Stopgaps:  #14173 
Description (last modified by )
Paulo Seijas reported the following bug on sagesupport [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/sagesupport/Iha5__c_h44
Apply: 13744_rebased.patch
Attachments (2)
Change History (37)
comment:1 Changed 8 years ago by
 Report Upstream changed from N/A to Reported upstream. No feedback yet.
comment:2 Changed 8 years ago by
 Description modified (diff)
 Report Upstream changed from Reported upstream. No feedback yet. to N/A
 Status changed from new to needs_review
Changed 8 years ago by
comment:3 Changed 8 years ago by
 Status changed from needs_review to positive_review
comment:4 Changed 8 years ago by
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
comment:5 followup: ↓ 6 Changed 8 years ago by
 Reviewers set to Robert Bradshaw
Is there anybody who still believes that nonEnglish 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.
comment:6 in reply to: ↑ 5 ; followup: ↓ 7 Changed 8 years ago by
Is there anybody who still believes that nonEnglish 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
comment:7 in reply to: ↑ 6 Changed 8 years ago by
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 fextendedidentifiers
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!
comment:8 Changed 8 years ago by
 Status changed from positive_review to needs_work
On sage.math (64bit Linux x86_64):
sage t force_lib devel/sage/sage/graphs/modular_decomposition/modular_decomposition.pyx /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libcsage.so(print_backtrace+0x31)[0x2ba5db141207] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libcsage.so(sigdie+0x14)[0x2ba5db141239] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libcsage.so(sage_signal_handler+0x216)[0x2ba5db140e16] /lib/libpthread.so.0[0x2ba5d90657d0] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/python/sitepackages/sage/graphs/modular_decomposition/modular_decomposition.so(algo2+0x459)[0x2ba607191f09] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/python/sitepackages/sage/graphs/modular_decomposition/modular_decomposition.so(decomposition_modulaire+0x67)[0x2ba607192e97] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/python/sitepackages/sage/graphs/modular_decomposition/modular_decomposition.so[0x2ba6071943e9] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x5ed8)[0x2ba5d8d5be98] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x855)[0x2ba5d8d5cfb5] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCode+0x32)[0x2ba5d8d5d0f2] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x515f)[0x2ba5d8d5b11f] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x855)[0x2ba5d8d5cfb5] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0[0x2ba5d8cdf9bc] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyObject_Call+0x53)[0x2ba5d8cb7bc3] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0[0x2ba5d8cc530f] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyObject_Call+0x53)[0x2ba5d8cb7bc3] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x3fcd)[0x2ba5d8d59f8d] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x855)[0x2ba5d8d5cfb5] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x5420)[0x2ba5d8d5b3e0] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x855)[0x2ba5d8d5cfb5] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0[0x2ba5d8cdf9bc] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyObject_Call+0x53)[0x2ba5d8cb7bc3] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0[0x2ba5d8cc530f] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyObject_Call+0x53)[0x2ba5d8cb7bc3] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x3fcd)[0x2ba5d8d59f8d] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x855)[0x2ba5d8d5cfb5] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x5420)[0x2ba5d8d5b3e0] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x855)[0x2ba5d8d5cfb5] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0[0x2ba5d8cdfab3] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyObject_Call+0x53)[0x2ba5d8cb7bc3] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0[0x2ba5d8cc530f] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyObject_Call+0x53)[0x2ba5d8cb7bc3] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x3fcd)[0x2ba5d8d59f8d] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x855)[0x2ba5d8d5cfb5] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x5420)[0x2ba5d8d5b3e0] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x855)[0x2ba5d8d5cfb5] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x5420)[0x2ba5d8d5b3e0] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x855)[0x2ba5d8d5cfb5] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x5420)[0x2ba5d8d5b3e0] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x855)[0x2ba5d8d5cfb5] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyEval_EvalCode+0x32)[0x2ba5d8d5d0f2] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyRun_FileExFlags+0xb0)[0x2ba5d8d7f790] /release/buildbot/sage/sage1/sage_binary/build/sage5.6.beta1/local/lib/libpython2.7.so.1.0(PyRun_SimpleFileExFlags+0xdf)[0x2ba5d8d8022f] /release/buildbot/sage/sage1/sage_binary/build/sage5.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. 
comment:9 Changed 8 years ago by
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/bsd1/bsd_full/build/sage5.6.beta1/devel/sagemain/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])]) **********************************************************************
comment:10 Changed 8 years ago by
T_T
And it still passes all tests on my machine.... :/
Nathann
Changed 8 years ago by
comment:11 Changed 8 years ago by
 Description modified (diff)
comment:12 Changed 8 years ago by
Well, I still get the crash on sage.math, although not always.
comment:13 Changed 8 years ago by
 Status changed from needs_work to positive_review
Currently, I don't manage to reproduce the problem so I'm putting back positive review for now.
comment:14 Changed 8 years ago by
 Milestone changed from sage5.6 to sage5.7
comment:15 Changed 8 years ago by
 Status changed from positive_review to needs_work
On bsd
(OS X 10.6):
sage t long force_lib devel/sage/sage/graphs/graph.py ********************************************************************** File "/Users/buildbot/build/sage/bsd1/bsd_full/build/sage5.7.beta0/devel/sagemain/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/bsd1/bsd_full/build/sage5.7.beta0/devel/sagemain/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/bsd1/bsd_full/build/sage5.7.beta0/devel/sagemain/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])]) **********************************************************************
comment:16 Changed 8 years ago by
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
comment:17 Changed 8 years ago by
It still crashes randomly on some systems...
comment:18 Changed 8 years ago by
 Stopgaps set to #14173
comment:19 Changed 8 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:20 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:21 Changed 7 years ago by
 Branch set to u/ncohen/13744
 Cc azi added
With a branch...
Nathann
comment:22 Changed 7 years ago by
 Commit set to 61e7f47c28907a604e19513ebd3ea8d505ed4103
Branch pushed to git repo; I updated commit sha1. New commits:
61e7f47  trac #13744: Bug in modular_decomposition

comment:23 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:24 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:26 Changed 6 years ago by
 Milestone changed from sage6.7 to sageduplicate/invalid/wontfix
 Status changed from needs_work to positive_review
Oh right.
To be closed as wontfix, as the new code is still incorrect and triggers segfault on mac OS X (see #17950)
comment:27 followup: ↓ 28 Changed 6 years ago by
 Milestone changed from sageduplicate/invalid/wontfix to sage6.7
 Status changed from positive_review to needs_work
Arg no.. I can't do that, as this is the ticket linked with the stopgap. Leif, what did you ping this ticket for ?
comment:28 in reply to: ↑ 27 ; followup: ↓ 29 Changed 6 years ago by
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.)
comment:29 in reply to: ↑ 28 Changed 6 years ago by
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
comment:31 Changed 4 years ago by
See also #22281.
comment:32 Changed 4 years ago by
 Milestone changed from sage6.7 to sageduplicate/invalid/wontfix
 Reviewers changed from Robert Bradshaw to Robert Bradshaw, Dima Pasechnik
 Status changed from needs_work to positive_review
The work on fixing this issue will be completed on #13744.
comment:33 followup: ↓ 34 Changed 3 years ago by
this should be closed now, as #23487 is done.
comment:34 in reply to: ↑ 33 Changed 3 years ago by
comment:35 Changed 3 years ago by
 Resolution set to wontfix
 Status changed from positive_review to closed
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...)