Opened 8 years ago

Closed 8 years ago

#11961 closed enhancement (fixed)

Fixes a bug in is_chordal -- two algorithms

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-4.8
Component: graph theory Keywords:
Cc: Merged in: sage-4.8.alpha5
Authors: Nathann Cohen, Jan Elffers Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

This ticket follows #11735, which fixes the bug reported by Jan on sage-devel [1]. It makes his alternative algorithm available in the function, so that we now have two different versions available, and still double-check the values it returns :-)

Requires : #11735

Apply : trac_11961.patch

[1] https://groups.google.com/d/topic/sage-support/rU1VTz1Ou_I/discussion

Attachments (1)

trac_11961.patch (8.0 KB) - added by ncohen 8 years ago.

Download all attachments as: .zip

Change History (6)

comment:1 Changed 8 years ago by ncohen

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

comment:2 Changed 8 years ago by jdemeyer

  • Milestone sage-4.7.3 deleted

Milestone sage-4.7.3 deleted

Changed 8 years ago by ncohen

comment:3 Changed 8 years ago by dcoudert

  • Milestone set to sage-4.8
  • Reviewers set to David Coudert
  • Status changed from needs_review to positive_review

I had no problem when installing the patch. The doc is also correctly generated.

All tests I have performed are consistent: both algorithms return the same boolean value. The certificate are not the same when several certificates are possible.

Algorithm B is a bit slower than algorithm A.

As I already said for patch #11735, significant running time improvements are possible for these linear time algorithms, but at least we have some algorithms ;)

Thank you Nathann.

comment:4 Changed 8 years ago by ncohen

Thank you for the review ! :-)

Algorithm B is a bit slower than algorithm A.

Yep. That's why it is good to have both :-)

As I already said for patch #11735, significant running time improvements are possible for these linear time algorithms, but at least we have some algorithms ;)

These codes are really standard. It would really be a shame not to implement them properly in C/C++ at some point.

Nathann

comment:5 Changed 8 years ago by jdemeyer

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