#10899: is_chordal can raise TypeError
-------------------------------+--------------------------------------------
Reporter: dsm | Owner: jason, ncohen, rlm
Type: defect | Status: positive_review
Priority: major | Milestone:
Component: graph theory | Keywords: sd35.5
Work_issues: | Upstream: N/A
Reviewer: Paul Zimmermann | Author: Lukáš Lánský
Merged: | Dependencies:
-------------------------------+--------------------------------------------
Changes (by newvalueoldvalue):
* status: needs_work => positive_review
* reviewer: => Paul Zimmermann
* work_issues: add exemple from description =>
* author: => Lukáš Lánský
Old description:
> is_chordal often -- but not always -- raises a TypeError on disconnected
> graphs (and the one-vertex graph) in 4.6.2:
>
> {{{
> 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
> }}}
>
> {{{
> 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
>
> }}}
>
> See trac #8284. The above also causes problems for is_interval, which at
> one point tries "if not self.is_chordal()".
New description:
is_chordal often -- but not always -- raises a TypeError on disconnected
graphs (and the one-vertex graph) in 4.6.2:
{{{
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
}}}
{{{
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
}}}
See trac #8284. The above also causes problems for is_interval, which at
one point tries "if not self.is_chordal()".
Apply [attachment:trac_10899_lex_BFS_repair.3.patch] to the Sage library.
--
Comment:
> I added the requested doctest and a small part of the presented testing
program.
thank you, great work!
Paul
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10899#comment:11>
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.
