is_chordal can raise TypeError

[sagetrac-dsm]

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.

CC: @gvol @sagetrac-brunellus @jasongrout

Component: graph theory

Keywords: sd35.5

Author: Lukáš Lánský

Reviewer: Paul Zimmermann

Merged: sage-5.0.beta2

Issue created by migration from https://trac.sagemath.org/ticket/10899

[sagetrac-brunellus]

comment:4

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

[sagetrac-brunellus]

Attachment: trac_10899_lex_BFS_repair.patch.gz

[zimmermann6]

comment:5

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

Paul

[zimmermann6]

Changed keywords from none to sd35.5

[sagetrac-brunellus]

Attachment: trac_10899_lex_BFS_repair.2.patch.gz

[sagetrac-brunellus]

comment:6

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

[zimmermann6]

comment:7

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

[zimmermann6]

Work Issues: add exemple from description

[zimmermann6]

comment:8

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

Paul

[sagetrac-brunellus]

comment:9

Attachment: trac_10899_lex_BFS_repair.3.patch.gz

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

[sagetrac-brunellus]

comment:10

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". :-)

[zimmermann6]

comment:11

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

thank you, great work!

Paul

[zimmermann6]

Author: Lukáš Lánský

[zimmermann6]

Changed work issues from add exemple from description to none

[zimmermann6]

Reviewer: Paul Zimmermann

[jasongrout]

comment:12

Replying to @sagetrac-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.

[jdemeyer]

Merged: sage-5.0.beta2