Opened 10 years ago
Closed 9 years ago
#10899 closed defect (fixed)
is_chordal can raise TypeError
Reported by: | dsm | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-5.0 |
Component: | graph theory | Keywords: | sd35.5 |
Cc: | iandrus, brunellus, jason | Merged in: | sage-5.0.beta2 |
Authors: | Lukáš Lánský | Reviewers: | Paul Zimmermann |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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 trac_10899_lex_BFS_repair.3.patch to the Sage library.
Attachments (3)
Change History (17)
comment:1 Changed 10 years ago by
- Cc iandrus added
comment:2 Changed 9 years ago by
- Cc brunellus added
comment:3 Changed 9 years ago by
- Cc jason added
comment:4 Changed 9 years ago by
- Status changed from new to needs_review
Changed 9 years ago by
comment:5 Changed 9 years ago by
- Keywords sd35.5 added
all doctests pass on top of 4.8.alpha6 on a 64-bit machine.
Paul
Changed 9 years ago by
comment:6 Changed 9 years ago by
Great! The new version differs only in technical details of the documentation.
comment:7 Changed 9 years ago by
- Status changed from needs_review to needs_work
- Work issues set to add exemple from description
please could you add also as doctest the example from the description?
sage: Graph(1).is_chordal() True
Note: one could wonder whether 0 vertices
should be 0 vertex
below:
sage: Graph().lex_BFS(tree=True) ([], Digraph on 0 vertices)
Note 2: while reviewing that ticket I discovered that the syntax Graph(n)
was not
documented. I will open a new ticket for that.
Paul
comment:8 Changed 9 years ago by
the issue about undocumented Graph(n)
is now at #12293.
Paul
Changed 9 years ago by
comment:9 Changed 9 years ago by
I added the requested doctest and a small part of the presented testing program.
comment:10 follow-up: ↓ 12 Changed 9 years ago by
English is not my first language, so I'm not sure whether "graph on 0 vertices" sounds weird. Wikipedia says:
"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."
I guess that some very polite piece of software could write something like "Digraph on no vertices". :-)
comment:11 Changed 9 years ago by
- Description modified (diff)
- Reviewers set to Paul Zimmermann
- Status changed from needs_work to positive_review
- Work issues add exemple from description deleted
I added the requested doctest and a small part of the presented testing program.
thank you, great work!
Paul
comment:12 in reply to: ↑ 10 Changed 9 years ago by
Replying to brunellus:
English is not my first language, so I'm not sure whether "graph on 0 vertices" sounds weird. Wikipedia says:
"0 vertices" is the correct English.
comment:13 Changed 9 years ago by
- Milestone set to sage-5.0
comment:14 Changed 9 years ago by
- Merged in set to sage-5.0.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
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.