Opened 9 years ago

Closed 8 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 zimmerma)

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)

trac_10899_lex_BFS_repair.patch (1.2 KB) - added by brunellus 8 years ago.
trac_10899_lex_BFS_repair.2.patch (1.2 KB) - added by brunellus 8 years ago.
trac_10899_lex_BFS_repair.3.patch (1.7 KB) - added by brunellus 8 years ago.

Download all attachments as: .zip

Change History (17)

comment:1 Changed 9 years ago by iandrus

  • Cc iandrus added

comment:2 Changed 8 years ago by brunellus

  • Cc brunellus added

comment:3 Changed 8 years ago by jason

  • Cc jason added

comment:4 Changed 8 years ago by brunellus

  • Status changed from new to needs_review

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.

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

Changed 8 years ago by brunellus

comment:5 Changed 8 years ago by zimmerma

  • Keywords sd35.5 added

all doctests pass on top of 4.8.alpha6 on a 64-bit machine.

Paul

Changed 8 years ago by brunellus

comment:6 Changed 8 years ago by brunellus

Great! The new version differs only in technical details of the documentation.

comment:7 Changed 8 years ago by zimmerma

  • 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 8 years ago by zimmerma

the issue about undocumented Graph(n) is now at #12293.

Paul

Changed 8 years ago by brunellus

comment:9 Changed 8 years ago by brunellus

I added the requested doctest and a small part of the presented testing program.

comment:10 follow-up: Changed 8 years ago by brunellus

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 8 years ago by zimmerma

  • Authors set to Lukáš Lánský
  • 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 8 years ago by jason

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 8 years ago by jdemeyer

  • Milestone set to sage-5.0

comment:14 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.0.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.