#10899: is_chordal can raise TypeError
----------------------------+-----------------------------------------------
Reporter: dsm | Owner: jason, ncohen, rlm
Type: defect | Status: new
Priority: major | Milestone:
Component: graph theory | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------+-----------------------------------------------
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()".
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10899>
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.
