Opened 7 years ago

Closed 21 months 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) Commit: 61e7f47c28907a604e19513ebd3ea8d505ed4103
Dependencies: Stopgaps: #14173

Description (last modified by jdemeyer)

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)

trac_13744.patch (31.5 KB) - added by ncohen 7 years ago.
13744_rebased.patch (35.4 KB) - added by jdemeyer 7 years ago.

Download all attachments as: .zip

Change History (37)

comment:1 Changed 7 years ago by ncohen

  • Report Upstream changed from N/A to Reported upstream. No feedback yet.

comment:2 Changed 7 years ago by ncohen

  • Authors set to Nathann Cohen
  • Description modified (diff)
  • Report Upstream changed from Reported upstream. No feedback yet. to N/A
  • Status changed from new to needs_review

Changed 7 years ago by ncohen

comment:3 Changed 7 years ago by robertwb

  • Status changed from needs_review to positive_review

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...)

comment:4 Changed 7 years ago by 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

comment:5 follow-up: Changed 7 years ago by vbraun

  • 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: Changed 7 years ago by 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

comment:7 in reply to: ↑ 6 Changed 7 years ago by 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!

comment:8 Changed 7 years ago by jdemeyer

  • 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 7 years ago by 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])])
**********************************************************************

comment:10 Changed 7 years ago by ncohen

T_T

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

Nathann

Changed 7 years ago by jdemeyer

comment:11 Changed 7 years ago by jdemeyer

  • Description modified (diff)

comment:12 Changed 7 years ago by jdemeyer

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

comment:13 Changed 7 years ago by jdemeyer

  • 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 7 years ago by jdemeyer

  • Milestone changed from sage-5.6 to sage-5.7

comment:15 Changed 7 years ago by jdemeyer

  • 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 7 years ago by 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

comment:17 Changed 7 years ago by jdemeyer

It still crashes randomly on some systems...

comment:18 Changed 6 years ago by lftabera

  • Stopgaps set to #14173

comment:19 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:20 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:21 Changed 5 years ago by ncohen

  • Branch set to u/ncohen/13744
  • Cc azi added

With a branch...

Nathann

comment:22 Changed 5 years ago by git

  • Commit set to 61e7f47c28907a604e19513ebd3ea8d505ed4103

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

61e7f47trac #13744: Bug in modular_decomposition

comment:23 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:24 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:25 Changed 4 years ago by leif

  • Milestone changed from sage-6.4 to sage-6.7

Ping...

comment:26 Changed 4 years ago by ncohen

  • 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: Changed 4 years ago by ncohen

  • 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: Changed 4 years ago by 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.)

comment:29 in reply to: ↑ 28 Changed 4 years ago by 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

comment:30 Changed 4 years ago by jmantysalo

  • Cc jmantysalo added

CC'ing myself because of #19215.

comment:31 Changed 3 years ago by jdemeyer

See also #22281.

comment:32 Changed 2 years ago by dimpase

  • 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 #23487.

Last edited 2 years ago by dimpase (previous) (diff)

comment:33 follow-up: Changed 22 months ago by dimpase

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

comment:34 in reply to: ↑ 33 Changed 22 months ago by 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.

comment:35 Changed 21 months ago by embray

  • Resolution set to wontfix
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.