id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
10899 is_chordal can raise TypeError dsm jason ncohen rlm "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/ in ()
/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." defect closed major sage-5.0 graph theory fixed sd35.5 iandrus brunellus jason sage-5.0.beta2 Lukáš Lánský Paul Zimmermann N/A