Error in function Graph.odd_girth()

[01e340b9-26d1-43e0-a194-d9a8889e621b]

Hi, I'm doing some computations based on enumerating graphs via "nauty_geng()", which enumerate all graphs of a given order.

For each graph, among other few things, I test the odd girth of the generated graphs (see code below). The code runs fine for some hours (i.e. it is able to perform the odd_girth() test for many millions graphs), but after some time it fails, with an error message indicating there is a problem in Graph.odd_girth(). The error messages indicate a possible relation with matrices and/or primes (see below).

Unfortunately since the code runs fine for some hours and only fails after a long time, I cannot reproduce the bug without doing the whole computation.

Note: I realise that I am using the precompiled version 5.8 of sage that comes with the ubuntu repository (ubuntu 12.04). So maybe this is fixed in newer versions... In any case I will now use the latest release. EDIT: the same bug happens with Sage 6.4 (run on another computer).

Here is my code:

def OG7_NOhomC5(begin,end):
    F=[]
    C5=graphs.CycleGraph(5)
    for n in [begin .. end]: #range for orders
        for g in graphs.nauty_geng("%s -c -t -d2 -D6"%n):
            if g.girth()==4 and g.odd_girth()>=7:
                maps=g.has_homomorphism_to(C5)
                if maps == False:
                    F += [(g.graph6_string())]
                    print ' found :-)',F

And I called:

OG7_NOhomC5(13,13)

OG7_NOhomC5(14,14)

OG7_NOhomC5(15,15)

in three different worksheets of the notebook interface.

And here are 2 different tracebacks that stopped the computation of "OG7_NOhomC5(13,13)" and "OG7_NOhomC5(14,14)", both have an error located in "odd_girth()". Note that "OG7_NOhomC5(15,15)" has not stopped, and is still running after about 8 hours.

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_3.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("T0c3X05PaG9tQzUoMTQsMTQp"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>

  File "/tmp/tmpPMZ4j_/___code___.py", line 3, in <module>
    exec compile(u'OG7_NOhomC5(_sage_const_14 ,_sage_const_14 )
  File "", line 1, in <module>

  File "/tmp/tmp1XHck_/___code___.py", line 10, in OG7_NOhomC5
    if g.girth()==_sage_const_4  and g.odd_girth()>=_sage_const_7 :
  File "/usr/lib/sagemath/local/lib/python2.7/site-packages/sage/graphs/graph.py", line 2388, in odd_girth
    ch = ((self.am()).charpoly()).coeffs()
  File "matrix_integer_dense.pyx", line 1042, in sage.matrix.matrix_integer_dense.Matrix_integer_dense.charpoly (sage/matrix/matrix_integer_dense.c:11571)
  File "matrix_integer_dense.pyx", line 1099, in sage.matrix.matrix_integer_dense.Matrix_integer_dense._charpoly_linbox (sage/matrix/matrix_integer_dense.c:12253)
  File "matrix_integer_dense.pyx", line 1121, in sage.matrix.matrix_integer_dense.Matrix_integer_dense._poly_linbox (sage/matrix/matrix_integer_dense.c:12534)
RuntimeError: Segmentation fault

you are running out of primes. 1000 coprime primes foundTraceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_4.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("T0c3X05PaG9tQzUoMTMsMTMp"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>

  File "/tmp/tmpRfy2qw/___code___.py", line 3, in <module>
    exec compile(u'OG7_NOhomC5(_sage_const_13 ,_sage_const_13 )
  File "", line 1, in <module>

  File "/tmp/tmp1inrim/___code___.py", line 10, in OG7_NOhomC5
    if g.girth()==_sage_const_4  and g.odd_girth()>=_sage_const_7 :
  File "/usr/lib/sagemath/local/lib/python2.7/site-packages/sage/graphs/graph.py", line 2392, in odd_girth
    if ch[i] != 0:
IndexError: list index out of range

Component: graph theory

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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:1

Could you provide an instruction that triggers that bug ? We cannot do much with a function when we do not know how it should be called. Also, you cannot ask us to 'run computations for hours' in order to check it. Thanks for your understanding,

Nathann

[01e340b9-26d1-43e0-a194-d9a8889e621b]

Description changed:

--- 
+++ 
@@ -1,5 +1,9 @@
 Hi,
-I'm doing some computations based on enumerating graphs via "nauty_geng()". There, I test the odd girth of the generated graphs, and after several hours of graph enumeration, the computations stop ith errors. The errors seem to come from the function "odd_girth()" associated to the "Graph" class, with, according to the error message, a possible relation with matrices and primes (see below).
+I'm doing some computations based on enumerating graphs via "nauty_geng()", which enumerate all graphs of a given order.
+
+For each graph, among other few things, I test the odd girth of the generated graphs (see code below). The code runs fine for some hours (i.e. it is able to perform the odd_girth() test for many millions graphs), but after some time it fails, with an error message indicating there is a problem in Graph.odd_girth(). The error messages indicate a possible relation with matrices and/or primes (see below).
+
+Unfortunately since the code runs fine for some hours and only fails after a long time, I cannot reproduce the bug without doing the whole computation.

 Note: I realise that I am using the precompiled version 5.8 of sage that comes with the ubuntu repository (ubuntu 12.04). So maybe this is fixed in newer versions... In any case I will now use the latest release.

@@ -16,13 +20,25 @@
                 if maps == False:
                     F += [(g.graph6_string())]
                     print ' found :-)',F
+```

+And I called:
+
+```
+OG7_NOhomC5(13,13)
+```
+
+```
 OG7_NOhomC5(14,14)

+ +OG7_NOhomC5(15,15) +

+in three different worksheets of the notebook interface.

-And here are 2 different tracebacks, both with an error located in "odd_girth()": +And here are 2 different tracebacks that stopped the computation, both have an error located in "odd_girth()":

 Traceback (most recent call last):

[01e340b9-26d1-43e0-a194-d9a8889e621b]

comment:3

Replying to @nathanncohen:

Could you provide an instruction that triggers that bug ? We cannot do much with a function when we do not know how it should be called. Also, you cannot ask us to 'run computations for hours' in order to check it. Thanks for your understanding,

I clarified my text, is it more clear now?

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:4

Yes, thanks. Could you give us the graphs g that your code found such that g.odd_girth produces a bug ?

Nathann

[01e340b9-26d1-43e0-a194-d9a8889e621b]

Description changed:

--- 
+++ 
@@ -38,7 +38,7 @@

 in three different worksheets of the notebook interface.

-And here are 2 different tracebacks that stopped the computation, both have an error located in "odd_girth()":
+And here are 2 different tracebacks that stopped the computation of "OG7_NOhomC5(13,13)" and "OG7_NOhomC5(14,14)", both have an error located in "odd_girth()". Note that "OG7_NOhomC5(15,15)" has not stopped, and is still running after about 8 hours.

Traceback (most recent call last):

[01e340b9-26d1-43e0-a194-d9a8889e621b]

comment:5

Replying to @nathanncohen:

Yes, thanks. Could you give us the graphs g that your code found such that g.odd_girth produces a bug ?

OK, so here is one graph of order 15 for which there was an error: :NqA?PRGSqgbG\AWbIWyGaESp~

And another one of order 14 (for this one, I got the "running out of prime" error): code>:MoAG\`oAQ@RFR?PAecKhbg</code

Edit: a third one, of order 13 this time: :Lm?K@RHGhbrGS{PdKb

For all of them, calling odd_girth() is not a problem. Note that they all have odd girth 5. Maybe this is a problem with the amount of calls to "odd_girth()" that are done?

[01e340b9-26d1-43e0-a194-d9a8889e621b]

Description changed:

--- 
+++ 
@@ -6,6 +6,7 @@
 Unfortunately since the code runs fine for some hours and only fails after a long time, I cannot reproduce the bug without doing the whole computation.

 Note: I realise that I am using the precompiled version 5.8 of sage that comes with the ubuntu repository (ubuntu 12.04). So maybe this is fixed in newer versions... In any case I will now use the latest release.
+EDIT: the same bug happens with Sage 6.4 (run on another computer).

 Here is my code:

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:7

This seems related to #15535 and #12883

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:8

Yeah it sees related to the number of calls, as other persons seem to have met the same problem when computing many characteristic polynomials :-/

Nathann

[01e340b9-26d1-43e0-a194-d9a8889e621b]

comment:9

OK, thanks... At least it seems to be a known bug.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:10

This ticket corresponds to the bug reported at #15535. Should be closed as a 'duplicate'.

Nathann