Opened 9 years ago
Closed 9 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: |
Status badges
Description (last modified by )
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)
Change History (6)
comment:1 Changed 9 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 9 years ago by
- Milestone sage-4.7.3 deleted
Changed 9 years ago by
comment:3 Changed 9 years ago by
- 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 9 years ago by
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 9 years ago by
- Merged in set to sage-4.8.alpha5
- Resolution set to fixed
- Status changed from positive_review to closed
Milestone sage-4.7.3 deleted