Sage: Ticket #10899: is_chordal can raise TypeError
https://trac.sagemath.org/ticket/10899
<p>
is_chordal often -- but not always -- raises a <a class="missing wiki">TypeError?</a> on disconnected graphs (and the one-vertex graph) in 4.6.2:
</p>
<pre class="wiki">sage: G = Graph()
sage: G.is_chordal()
True
sage: G = Graph(1)
sage: G.is_chordal()
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
/Users/mcneil/Desktop/<ipython console> in <module>()
/Applications/sage/local/lib/python2.6/site-packages/sage/graphs/generic_graph.pyc in is_chordal(self, certificate)
9480 for v in peo:
9481
-> 9482 if t_peo.out_degree(v)>0 and g.neighbors(v) not in neighbors_subsets[t_peo.neighbor_out_iterator(v).next()]:
9483
9484 if certificate:
/Applications/sage/local/lib/python2.6/site-packages/sage/graphs/digraph.pyc in out_degree(self, vertices, labels)
1147 return di
1148 else:
-> 1149 return list(self.out_degree_iterator(vertices, labels=labels))
1150
1151 def out_degree_iterator(self, vertices=None, labels=False):
/Applications/sage/local/lib/python2.6/site-packages/sage/graphs/digraph.pyc in out_degree_iterator(self, vertices, labels)
1192 yield (v, d)
1193 else:
-> 1194 for v in vertices:
1195 d = 0
1196 for e in self.outgoing_edge_iterator(v):
TypeError: 'int' object is not iterable
</pre><pre class="wiki">def crash(g):
try:
g.is_chordal(); return False
except TypeError:
return True
from collections import defaultdict
for n in [0..7]:
gcount = 0
res = defaultdict(int)
for g in graphs(n):
gcount += 1
cr = crash(g)
res[(cr, g.is_connected())] += 1
print n, 'total graphs:', gcount,
for k in sorted(res):
print '(crashed: %s, connected: %s) = %d' % (k[0], k[1], res[k]),
print
0 total graphs: 1 (crashed: False, connected: True) = 1
1 total graphs: 1 (crashed: True, connected: True) = 1
2 total graphs: 2 (crashed: False, connected: True) = 1 (crashed: True, connected: False) = 1
3 total graphs: 4 (crashed: False, connected: True) = 2 (crashed: True, connected: False) = 2
4 total graphs: 11 (crashed: False, connected: False) = 1 (crashed: False, connected: True) = 6 (crashed: True, connected: False) = 4
5 total graphs: 34 (crashed: False, connected: False) = 3 (crashed: False, connected: True) = 21 (crashed: True, connected: False) = 10
6 total graphs: 156 (crashed: False, connected: False) = 17 (crashed: False, connected: True) = 112 (crashed: True, connected: False) = 27
7 total graphs: 1044 (crashed: False, connected: False) = 97 (crashed: False, connected: True) = 853 (crashed: True, connected: False) = 94
</pre><p>
See trac <a class="closed ticket" href="https://trac.sagemath.org/ticket/8284" title="defect: IntervalGraph generator and a bug in is_chordal (closed: fixed)">#8284</a>. The above also causes problems for is_interval, which at one point tries "if not self.is_chordal()".
</p>
<p>
Apply <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/10899/trac_10899_lex_BFS_repair.3.patch" title="Attachment 'trac_10899_lex_BFS_repair.3.patch' in Ticket #10899">trac_10899_lex_BFS_repair.3.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/10899/trac_10899_lex_BFS_repair.3.patch" title="Download"></a> to the Sage library.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/10899
Trac 1.1.6iandrusThu, 24 Mar 2011 00:44:14 GMTcc set
https://trac.sagemath.org/ticket/10899#comment:1
https://trac.sagemath.org/ticket/10899#comment:1
<ul>
<li><strong>cc</strong>
<em>iandrus</em> added
</li>
</ul>
TicketbrunellusFri, 02 Dec 2011 22:11:45 GMTcc changed
https://trac.sagemath.org/ticket/10899#comment:2
https://trac.sagemath.org/ticket/10899#comment:2
<ul>
<li><strong>cc</strong>
<em>brunellus</em> added
</li>
</ul>
TicketjasonSat, 03 Dec 2011 21:28:27 GMTcc changed
https://trac.sagemath.org/ticket/10899#comment:3
https://trac.sagemath.org/ticket/10899#comment:3
<ul>
<li><strong>cc</strong>
<em>jason</em> added
</li>
</ul>
TicketbrunellusWed, 07 Dec 2011 23:37:22 GMTstatus changed
https://trac.sagemath.org/ticket/10899#comment:4
https://trac.sagemath.org/ticket/10899#comment:4
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
<p>
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 <a class="missing wiki">DiGraph?</a>, where it sould return <a class="missing wiki">DiGraph?</a>(1). Then is_chordal fails, because it asks for order of the vertex 1, that is not in the <a class="missing wiki">DiGraph?</a>. It is somehow unfortunate that out_degree function couldn't detect this problem and respond with a more apropriate error message.
</p>
<p>
So, why does lex_BFS fail to construct the proper tree? It takes the proper edges and adds them to the empty <a class="missing wiki">DiGraph?</a>. 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.
</p>
<p>
I tried to run the crash test code from the ticket description and it didn't find any failing case.
</p>
<pre class="wiki">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
</pre>
TicketbrunellusWed, 07 Dec 2011 23:37:41 GMTattachment set
https://trac.sagemath.org/ticket/10899
https://trac.sagemath.org/ticket/10899
<ul>
<li><strong>attachment</strong>
set to <em>trac_10899_lex_BFS_repair.patch</em>
</li>
</ul>
TicketzimmermaTue, 10 Jan 2012 14:54:42 GMTkeywords set
https://trac.sagemath.org/ticket/10899#comment:5
https://trac.sagemath.org/ticket/10899#comment:5
<ul>
<li><strong>keywords</strong>
<em>sd35.5</em> added
</li>
</ul>
<p>
all doctests pass on top of 4.8.alpha6 on a 64-bit machine.
</p>
<p>
Paul
</p>
TicketbrunellusTue, 10 Jan 2012 20:37:10 GMTattachment set
https://trac.sagemath.org/ticket/10899
https://trac.sagemath.org/ticket/10899
<ul>
<li><strong>attachment</strong>
set to <em>trac_10899_lex_BFS_repair.2.patch</em>
</li>
</ul>
TicketbrunellusTue, 10 Jan 2012 20:39:11 GMT
https://trac.sagemath.org/ticket/10899#comment:6
https://trac.sagemath.org/ticket/10899#comment:6
<p>
Great! The new version differs only in technical details of the documentation.
</p>
TicketzimmermaWed, 11 Jan 2012 09:45:20 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/10899#comment:7
https://trac.sagemath.org/ticket/10899#comment:7
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>add exemple from description</em>
</li>
</ul>
<p>
please could you add also as doctest the example from the description?
</p>
<pre class="wiki">sage: Graph(1).is_chordal()
True
</pre><p>
Note: one could wonder whether <code>0 vertices</code> should be <code>0 vertex</code> below:
</p>
<pre class="wiki">sage: Graph().lex_BFS(tree=True)
([], Digraph on 0 vertices)
</pre><p>
Note 2: while reviewing that ticket I discovered that the syntax <code>Graph(n)</code> was not
documented. I will open a new ticket for that.
</p>
<p>
Paul
</p>
TicketzimmermaWed, 11 Jan 2012 09:49:26 GMT
https://trac.sagemath.org/ticket/10899#comment:8
https://trac.sagemath.org/ticket/10899#comment:8
<p>
the issue about undocumented <code>Graph(n)</code> is now at <a class="closed ticket" href="https://trac.sagemath.org/ticket/12293" title="defect: Graph(n) is not documented (closed: fixed)">#12293</a>.
</p>
<p>
Paul
</p>
TicketbrunellusWed, 11 Jan 2012 16:51:41 GMTattachment set
https://trac.sagemath.org/ticket/10899
https://trac.sagemath.org/ticket/10899
<ul>
<li><strong>attachment</strong>
set to <em>trac_10899_lex_BFS_repair.3.patch</em>
</li>
</ul>
TicketbrunellusWed, 11 Jan 2012 16:54:18 GMT
https://trac.sagemath.org/ticket/10899#comment:9
https://trac.sagemath.org/ticket/10899#comment:9
<p>
I added the requested doctest and a small part of the presented testing program.
</p>
TicketbrunellusWed, 11 Jan 2012 17:03:30 GMT
https://trac.sagemath.org/ticket/10899#comment:10
https://trac.sagemath.org/ticket/10899#comment:10
<p>
English is not my first language, so I'm not sure whether "graph on 0 vertices" sounds weird. Wikipedia says:
</p>
<p>
"Languages having only a singular and plural form may still differ in their treatment of zero. For example, in English, German, Dutch, Italian, Spanish and Portuguese, the plural form is used for zero or more than one, and the singular for one thing only. By contrast, in French, the singular form is used for zero."
</p>
<p>
I guess that some very polite piece of software could write something like "Digraph on no vertices". :-)
</p>
TicketzimmermaWed, 11 Jan 2012 17:10:58 GMTstatus, description changed; reviewer, author set; work_issues deleted
https://trac.sagemath.org/ticket/10899#comment:11
https://trac.sagemath.org/ticket/10899#comment:11
<ul>
<li><strong>work_issues</strong>
<em>add exemple from description</em> deleted
</li>
<li><strong>reviewer</strong>
set to <em>Paul Zimmermann</em>
</li>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/10899?action=diff&version=11">diff</a>)
</li>
<li><strong>author</strong>
set to <em>Lukáš Lánský</em>
</li>
</ul>
<blockquote class="citation">
<p>
I added the requested doctest and a small part of the presented testing program.
</p>
</blockquote>
<p>
thank you, great work!
</p>
<p>
Paul
</p>
TicketjasonThu, 12 Jan 2012 15:12:27 GMT
https://trac.sagemath.org/ticket/10899#comment:12
https://trac.sagemath.org/ticket/10899#comment:12
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10899#comment:10" title="Comment 10">brunellus</a>:
</p>
<blockquote class="citation">
<p>
English is not my first language, so I'm not sure whether "graph on 0 vertices" sounds weird. Wikipedia says:
</p>
</blockquote>
<p>
"0 vertices" is the correct English.
</p>
TicketjdemeyerSun, 15 Jan 2012 10:44:51 GMTmilestone set
https://trac.sagemath.org/ticket/10899#comment:13
https://trac.sagemath.org/ticket/10899#comment:13
<ul>
<li><strong>milestone</strong>
set to <em>sage-5.0</em>
</li>
</ul>
TicketjdemeyerMon, 23 Jan 2012 13:57:56 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/10899#comment:14
https://trac.sagemath.org/ticket/10899#comment:14
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-5.0.beta2</em>
</li>
</ul>
Ticket