#17787: Wrong result returned by Graph.is_interval
-------------------------+-------------------------------------------------
Reporter: | Owner:
ncohen | Status: needs_review
Type: | Milestone: sage-6.5
defect | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: | b937842be6daaa63611f4ce4fef2238fcff65200
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
u/ncohen/17787 |
Dependencies: |
-------------------------+-------------------------------------------------
Description changed by ncohen:
Old description:
> 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:
>
> 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
New description:
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
--
--
Ticket URL: <http://trac.sagemath.org/ticket/17787#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
