#13546: Bug in is_perfect
-------------------------------------------+--------------------------------
Reporter: azi | Owner: jason, ncohen, rlm
Type: defect | Status: needs_work
Priority: critical | Milestone: sage-5.7
Component: graph theory | Resolution:
Keywords: is_perfect,graph theory | Work issues:
Report Upstream: N/A | Reviewers: Sébastien Labbé
Authors: Jernej Azarija | Merged in:
Dependencies: #8952 | Stopgaps:
-------------------------------------------+--------------------------------
Changes (by slabbe):
* status: needs_review => needs_work
* reviewer: => Sébastien Labbé
Comment:
Trying to understand the bug... with sage-5.6.rc0 I get:
{{{
sage: time s_907 = set(g.sparse6_string() for g in graphs.nauty_geng('7')
if g.is_perfect())
Time: CPU 29.02 s, Wall: 29.74 s
sage: len(s_907)
907
save(s_907, '907_perfect_graph.sobj')
}}}
With sage-5.6.rc0 + the patch:
{{{
sage: time s_906 = set(g.sparse6_string() for g in graphs.nauty_geng('7')
if g.is_perfect())
Time: CPU 25.30 s, Wall: 26.32 s
sage: len(s_906)
906
sage: s_907 = load('907_perfect_graph.sobj')
sage: s_906.issubset(s_907)
True
sage: len(s_907.difference(s_906))
1
sage: a = s_907.difference(s_906).pop()
sage: a
':FgGE@I@GxGs'
sage: Graph(a)
Looped multi-graph on 7 vertices
sage: Graph(a).show()
}}}
With sage-5.6.rc0 and no patch applied:
{{{
sage: for g in graphs.nauty_geng('7'):
....: if g.sparse6_string() == ':FgGE@I@GxGs':
....: break
....:
sage: g
Graph on 7 vertices
sage: g.to_dictionary()
{0: [2, 3, 4, 5], 1: [3, 4, 5, 6], 2: [0, 4, 5, 6], 3: [0, 1, 5, 6], 4:
[0, 1, 2, 6], 5: [0, 1, 2, 3], 6: [1, 2, 3, 4]}
}}}
Starting from scratch. With sage-5.6.rc0, I get True with this graph:
{{{
sage: g = Graph({0: [2, 3, 4, 5], 1: [3, 4, 5, 6], 2: [0, 4, 5, 6], 3: [0,
1, 5, 6], 4: [0, 1, 2, 6], 5: [0, 1, 2, 3], 6: [1, 2, 3, 4]})
sage: g.is_perfect()
True
}}}
Strangely, I get a runtime error if I reconstruct the graph from the
sparse string:
{{{
sage: Graph(':FgGE@I@GxGs').is_perfect()
Traceback (most recent call last):
...
RuntimeError: Segmentation fault
}}}
I don't know what this sparse string is doing... It does not seem to be
injective for instance... Anyway.
With sage-5.6.rc0 + the patch, everything is fine:
{{{
sage: Graph(':FgGE@I@GxGs').is_perfect()
False
sage: g = Graph({0: [2, 3, 4, 5], 1: [3, 4, 5, 6], 2: [0, 4, 5, 6], 3: [0,
1, 5, 6], 4: [0, 1, 2, 6], 5: [0, 1, 2, 3], 6: [1, 2, 3, 4]})
sage: g.is_perfect()
False
}}}
Can we add this previous doctest in the patch? because there is no doctest
in the patch in its actual version. It would have to be an optional one
since it depends on the optional package nauty....
There is something I still do not understand (related to sparse string).
`is_perfect` does not seem to be preserve under the passage to the
`sparse6_string`... Only 818 of the graph are still perfect after the
recovery... All this would be more easy if graphs were hashable...
Anyways...
{{{
age: time s = set(g.sparse6_string() for g in graphs.nauty_geng('7') if
g.is_perfect())
Time: CPU 24.94 s, Wall: 24.99 s
sage: L = [Graph(g).is_perfect() for g in s]
sage: all(L)
False
sage: import collections
sage: collections.Counter(L)
Counter({False: 818, True: 88})
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13546#comment:12>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
Visit this group at http://groups.google.com/group/sage-trac?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
