Opened 4 years ago

Closed 4 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 ncohen)

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

  • Branch set to u/ncohen/17787
  • Status changed from new to needs_review

comment:2 Changed 4 years ago by git

  • Commit set to b937842be6daaa63611f4ce4fef2238fcff65200

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

b937842trac #17787: Wrong result returned by Graph.is_interval

comment:3 Changed 4 years ago by ncohen

  • Description modified (diff)

comment:4 Changed 4 years ago by dimpase

  • Reviewers set to Dima Pasechnik
  • Status changed from needs_review to positive_review

LGTM

comment:5 Changed 4 years ago by ncohen

Wow. Thanks ! :-)

Nathann

comment:6 Changed 4 years ago by vbraun

  • Branch changed from u/ncohen/17787 to b937842be6daaa63611f4ce4fef2238fcff65200
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.