#17640: Error in function Graph.odd_girth()
--------------------------------+--------------------------
Reporter: ffoucaud | Owner:
Type: defect | Status: needs_info
Priority: major | Milestone:
Component: graph theory | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
--------------------------------+--------------------------
Description changed by ffoucaud:
Old description:
> 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).
>
> 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.
>
> 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
>
> OG7_NOhomC5(14,14)
> }}}
>
>
> And here are 2 different tracebacks, both with an error located in
> "odd_girth()":
>
> {{{
> 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
> }}}
New description:
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.
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, both
have an error located in "odd_girth()":
{{{
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
}}}
--
--
Ticket URL: <http://trac.sagemath.org/ticket/17640#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
