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: | sage-duplicate/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 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
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 follow-up: ↓ 6 Changed 8 years ago by
- Reviewers set to Robert Bradshaw
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.
comment:6 in reply to: ↑ 5 ; follow-up: ↓ 7 Changed 8 years ago by
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
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 -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!
comment:8 Changed 8 years ago by
- Status changed from positive_review to needs_work
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. ------------------------------------------------------------------------
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/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])]) **********************************************************************
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 sage-5.6 to sage-5.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/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])]) **********************************************************************
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 sage-5.11 to sage-5.12
comment:20 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.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 sage-6.2 to sage-6.3
comment:24 Changed 7 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:26 Changed 6 years ago by
- Milestone changed from sage-6.7 to sage-duplicate/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 follow-up: ↓ 28 Changed 6 years ago by
- Milestone changed from sage-duplicate/invalid/wontfix to sage-6.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 ; follow-up: ↓ 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 sage-6.7 to sage-duplicate/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 follow-up: ↓ 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...)