Opened 6 years ago
Closed 6 years ago
#17787 closed defect (fixed)
Wrong result returned by Graph.is_interval
Reported by: | ncohen | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.5 |
Component: | graph theory | Keywords: | |
Cc: | dcoudert, was, dimpase | Merged in: | |
Authors: | Nathann Cohen | Reviewers: | Dima Pasechnik |
Report Upstream: | N/A | Work issues: | |
Branch: | b937842 (Commits) | Commit: | b937842be6daaa63611f4ce4fef2238fcff65200 |
Dependencies: | Stopgaps: |
Description (last modified by )
It has been reported by Damian Bogdanowicz on sage-devel [1] that the interval graph recognition agorithm returns a wrong result:
sage: Graph('GvGNp?').is_interval() True
This graph is not an interval graph as it contains an asteroidal triple (1,5,7).
The fix is rather short: some 'partial' pq-trees were handled like 'full' ones and that was wrong. As an additional check, we get the expected [2] number of interval graphs up to n=9 (takes ~10mn)
sage: n = 8 sage: count = [0]*(n+1) sage: for g in graphs(n, augment='vertices',property= lambda x:x.is_interval()): ....: count[g.order()] += 1 sage: count [1, 1, 2, 4, 10, 27, 92, 369, 1807, 10344]
Nathann
P.S.: The class, however, could definitely benefit from a more general rewrite. Another ticket (already half-written) will adress that and make the documentation and method names more explicit.
[1] https://groups.google.com/forum/#!topic/sage-combinat-devel/DnULBrlkgBc [2] http://oeis.org/A005975
Change History (6)
comment:1 Changed 6 years ago by
- Branch set to u/ncohen/17787
- Status changed from new to needs_review
comment:2 Changed 6 years ago by
- Commit set to b937842be6daaa63611f4ce4fef2238fcff65200
comment:3 Changed 6 years ago by
- Description modified (diff)
comment:4 Changed 6 years ago by
- Reviewers set to Dima Pasechnik
- Status changed from needs_review to positive_review
LGTM
comment:5 Changed 6 years ago by
Wow. Thanks ! :-)
Nathann
comment:6 Changed 6 years ago by
- Branch changed from u/ncohen/17787 to b937842be6daaa63611f4ce4fef2238fcff65200
- Resolution set to fixed
- Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
trac #17787: Wrong result returned by Graph.is_interval