#10899: is_chordal can raise TypeError
----------------------------+-----------------------------------------------
Reporter: dsm | Owner: jason, ncohen, rlm
Type: defect | Status: needs_review
Priority: major | Milestone:
Component: graph theory | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
----------------------------+-----------------------------------------------
Changes (by brunellus):
* status: new => needs_review
Comment:
OK, this was quite easy -- the problem was that lex_BFS fails to generate
correct tree. If we consider Graph(1), lex_BFS correctly computes order
[1], but as a tree it return empty DiGraph, where it sould return
DiGraph(1). Then is_chordal fails, because it asks for order of the vertex
1, that is not in the DiGraph. It is somehow unfortunate that out_degree
function couldn't detect this problem and respond with a more apropriate
error message.
So, why does lex_BFS fail to construct the proper tree? It takes the
proper edges and adds them to the empty DiGraph. But that is not
sufficient when the tree shouldn't contain any edges, as it is in the case
of Graph(1). So the whole patch I wrote consist of single line, that adds
vertices to the newly created tree too.
I tried to run the crash test code from the ticket description and it
didn't find any failing case.
{{{
0 total graphs: 1 (crashed: False, connected: True) = 1
1 total graphs: 1 (crashed: False, connected: True) = 1
2 total graphs: 2 (crashed: False, connected: False) = 1 (crashed: False,
connected: True) = 1
3 total graphs: 4 (crashed: False, connected: False) = 2 (crashed: False,
connected: True) = 2
4 total graphs: 11 (crashed: False, connected: False) = 5 (crashed: False,
connected: True) = 6
5 total graphs: 34 (crashed: False, connected: False) = 13 (crashed:
False, connected: True) = 21
6 total graphs: 156 (crashed: False, connected: False) = 44 (crashed:
False, connected: True) = 112
7 total graphs: 1044 (crashed: False, connected: False) = 191 (crashed:
False, connected: True) = 853
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10899#comment:4>
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].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
