Opened 8 years ago

Closed 8 years ago

#11738 closed defect (fixed)

Various issues in is_interval and is_chordal

Reported by: ddestrada Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-4.7.2
Component: graph theory Keywords: interval chordal
Cc: ncohen Merged in: sage-4.7.2.alpha3
Authors: Diego de Estrada Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

There is a bug in the return line of is_chordal when asked for a certificate and the graph has more than one connected component.

Also, here there is an enhancement to avoid the explicit generation of subsets in is_interval and is_chordal, which is expensive, using issubset() instead.

Apply only :

Attachments (4)

is_chordal_bugfix.patch (706 bytes) - added by ddestrada 8 years ago.
is_chordal_optimization.patch (2.4 KB) - added by ddestrada 8 years ago.
is_interval_fixes.patch (1.4 KB) - added by ddestrada 8 years ago.
trac_11738.patch (3.6 KB) - added by ncohen 8 years ago.

Download all attachments as: .zip

Change History (11)

comment:1 follow-up: Changed 8 years ago by ncohen

  • Description modified (diff)
  • Status changed from new to needs_review

Hellooooo Diego !

I just tried to aply your patches, and noticed a small problem : you worked on files located in the build/ directory, and those files we usully do not touch (they are not even tracked by HG). When you modify Sage's sources, you should work in the sage/ folder instead of the build/ folder, and modifyth corresponding files. Then, when you load Sage, you should type "sage -br branch_name" to let it know that some files have been modified. As they are made right now, your patches modify files that will be overwritten when Sage is rebuilt :-)

Then, I noticed that you were reversing the default order of the lex-BFS tree. That's a default choice, so I do not think it makes much of a difference, but I was worried that it may break doctests in Sage. All the examples of code you see in Sage's documentation are actually automated tests that let us check our modifications to not create new bugs. It's dead useful, but it also means that when you reverse this kind of ordering one of the doctest may expect 1 2 3 4 5 and receive 5 4 3 2 1 :-)

Then again, I did not test this because of the "build/" thing :-)

http://www.sagemath.org/doc/developer/doctesting.html

Nathann

P.S. : Oh, and do nt forget to set the Trac ticket's status to needs_review when necessary, otherwise it does not appear in thelist of tickets needing care and they can be forgotten forever this way ! (some of my tickets disappeared for a few months because of such a mistake before) :-)

comment:2 Changed 8 years ago by ncohen

  • Status changed from needs_review to needs_work

comment:3 Changed 8 years ago by ddestrada

  • Description modified (diff)
  • Status changed from needs_work to needs_review

Changed 8 years ago by ddestrada

Changed 8 years ago by ddestrada

Changed 8 years ago by ddestrada

comment:4 in reply to: ↑ 1 Changed 8 years ago by ddestrada

Replying to ncohen: Thank you Nathann. I have undone the reversal of the tree and fixed "build/" thing.

comment:5 Changed 8 years ago by ncohen

  • Authors set to Diego de Estrada
  • Description modified (diff)
  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to positive_review

Hello Diego !

Thank you for your modifications ! :-)

While reviewing your patches I folded them into a unique one, so that it will be easier for the release manager to merge. It passed all tests and fixed some of my mistakes, thank you very much for it !

I will shortly update #11735 so that it can be applied on top of this patch, and quickly fix the current bug (by the way, if you are willing to review #11735 after that.. :-D). Another patch will follow #11735 as a result of the discussion with Jan mentionned there. At least with #11735 we will have a "sounder" version implementation, no danger of having a bad result returned, but that will have to be patched too :-)

It's getting fixed, guys !!!!

(and thank you again !)

Nathann

Changed 8 years ago by ncohen

comment:6 Changed 8 years ago by ncohen

  • Description modified (diff)

comment:7 Changed 8 years ago by leif

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