search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.39k stars 473 forks source link

tests for graphs failing #35157

Closed GMS103 closed 1 year ago

GMS103 commented 1 year ago

Is there an existing issue for this?

Did you read the documentation and troubleshoot guide?

Environment

- **OS**: macOS 11.7.4, macOS 12.6.3, macOS 13.2.1
- **Sage Version**: 10.0.beta0

Steps To Reproduce

Running make ptestlong gives

sage -t --long --warn-long 57.8 --random-seed=290645697385203691838308049816374839723 src/sage/graphs/generators/families.py  # 3 doctests failed
sage -t --long --warn-long 57.8 --random-seed=290645697385203691838308049816374839723 src/sage/graphs/graph_generators.py  # 1 doctest failed

as follows (the last 3 seem cosmetic, but not the first).

Expected Behavior

All tests passed!

Actual Behavior

% ./sage -t --long --warn-long 57.8 --random-seed=290645697385203691838308049816374839723 src/sage/graphs/generators/families.py
Running doctests with ID 2023-02-18-18-10-46-bcc2e4c0.
Git branch: develop
Git ref: 10.0.beta0-12-gfbb412787f
Running with SAGE_LOCAL='…/sage/local' and SAGE_VENV='…/sage/local/var/lib/sage/venv-python3.11'
Using --optional=homebrew,pip,sage,sage_spkg
Features to be detected: 4ti2,benzene,bliss,buckygen,conway_polynomials,csdp,cvxopt,database_cremona_ellcurve,database_cremona_mini_ellcurve,database_cubic_hecke,database_jones_numfield,database_knotinfo,dvipng,gfan,graphviz,imagemagick,jupymake,kenzo,latte_int,lrslib,mcqd,meataxe,msolve,nauty,palp,pandoc,pdf2svg,pdftocairo,phitigra,plantri,polytopes_db,polytopes_db_4d,pynormaliz,python_igraph,rubiks,sage.combinat,sage.geometry.polyhedron,sage.graphs,sage.groups,sage.misc.cython,sage.plot,sage.rings.number_field,sage.rings.padics,sage.rings.real_double,sage.symbolic,sage_numerical_backends_coin,sagemath_doc_html,sphinx,tdlib
Doctesting 1 file.
sage -t --long --warn-long 57.8 --random-seed=290645697385203691838308049816374839723 src/sage/graphs/generators/families.py
**********************************************************************
File "src/sage/graphs/generators/families.py", line 3652, in sage.graphs.generators.families.nauty_gentreeg
Failed example:
    [len(list(graphs.nauty_gentreeg(str(i)))) for i in range(1, 15)]
Expected:
    [1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159]
Got:
    [1, 0, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159]
**********************************************************************
File "src/sage/graphs/generators/families.py", line 3662, in sage.graphs.generators.families.nauty_gentreeg
Failed example:
    print(next(gen))
Expected:
    >A ...gentreeg Z=2:3 D=3 n=4
Got:
    >A /opt/homebrew/bin/gentreeg Z=0:0 D=0 n=0
    <BLANKLINE>
**********************************************************************
File "src/sage/graphs/generators/families.py", line 3689, in sage.graphs.generators.families.nauty_gentreeg
Failed example:
    list(graphs.nauty_gentreeg("3", debug=True))
Expected:
    ['>A ...gentreeg Z=2:2 D=2 n=3\n', Graph on 3 vertices]
Got:
    ['>A /opt/homebrew/bin/gentreeg Z=0:0 D=0 n=0\n', Graph on 3 vertices]
**********************************************************************
1 item had failures:
   3 of  16 in sage.graphs.generators.families.nauty_gentreeg
    [476 tests, 3 failures, 10.07 s]
----------------------------------------------------------------------
sage -t --long --warn-long 57.8 --random-seed=290645697385203691838308049816374839723 src/sage/graphs/generators/families.py  # 3 doctests failed
----------------------------------------------------------------------
Total time for all tests: 10.2 seconds
    cpu time: 9.2 seconds
    cumulative wall time: 10.1 seconds
Features detected for doctesting: sage.groups

and

% ./sage -t --long --warn-long 57.8 --random-seed=290645697385203691838308049816374839723 src/sage/graphs/graph_generators.py
Running doctests with ID 2023-02-18-18-11-18-4cc34614.
Git branch: develop
Git ref: 10.0.beta0-12-gfbb412787f
Running with SAGE_LOCAL='…/sage/local' and SAGE_VENV='…/sage/local/var/lib/sage/venv-python3.11'
Using --optional=homebrew,pip,sage,sage_spkg
Features to be detected: 4ti2,benzene,bliss,buckygen,conway_polynomials,csdp,cvxopt,database_cremona_ellcurve,database_cremona_mini_ellcurve,database_cubic_hecke,database_jones_numfield,database_knotinfo,dvipng,gfan,graphviz,imagemagick,jupymake,kenzo,latte_int,lrslib,mcqd,meataxe,msolve,nauty,palp,pandoc,pdf2svg,pdftocairo,phitigra,plantri,polytopes_db,polytopes_db_4d,pynormaliz,python_igraph,rubiks,sage.combinat,sage.geometry.polyhedron,sage.graphs,sage.groups,sage.misc.cython,sage.plot,sage.rings.number_field,sage.rings.padics,sage.rings.real_double,sage.symbolic,sage_numerical_backends_coin,sagemath_doc_html,sphinx,tdlib
Doctesting 1 file.
sage -t --long --warn-long 57.8 --random-seed=290645697385203691838308049816374839723 src/sage/graphs/graph_generators.py
**********************************************************************
File "src/sage/graphs/graph_generators.py", line 968, in sage.graphs.graph_generators.GraphGenerators.nauty_geng
Failed example:
    list(graphs.nauty_geng("-c3", debug=True))
Expected:
    ['>E Usage: ...geng [-cCmtfbd#D#] [-uygsnh] [-lvq] ...
Got:
    ['>E Usage: geng [-cCmtfkbd#D#] [-uygsnh] [-lvq] \n']
**********************************************************************
1 item had failures:
   1 of  18 in sage.graphs.graph_generators.GraphGenerators.nauty_geng
    [124 tests, 1 failure, 4.85 s]
----------------------------------------------------------------------
sage -t --long --warn-long 57.8 --random-seed=290645697385203691838308049816374839723 src/sage/graphs/graph_generators.py  # 1 doctest failed
----------------------------------------------------------------------
Total time for all tests: 5.1 seconds
    cpu time: 4.3 seconds
    cumulative wall time: 4.8 seconds
Features detected for doctesting: sage.symbolic

Additional Information

No response

mkoeppe commented 1 year ago

Where's your nauty coming from? (See config.log)

Related (maybe dup): #34133

GMS103 commented 1 year ago

It is coming from Homebrew, as indicated in https://doc.sagemath.org/html/en/installation/source.html

macOS package installation If you use the Homebrew package manager, you can install the following:

brew install arb bdw-gc boost bzip2 cddlib cmake curl ecl flint fplll freetype gcc gd gengetopt gfortran glpk gmp gpatch gsl libatomic_ops libffi libiconv libmpc libpng meson mpfi mpfr nauty ncurses ninja ntl openblas openssl pari pari-elldata pari-galdata pari-galpol pari-seadata pcre pkg-config ppl primecount primesieve python3 qhull readline singular sqlite suite-sparse tox xz zeromq zlib

and Homebrew is up to date. Namely:

% brew info nauty
[…]
==> nauty: stable 2.8.6 (bottled)
Automorphism groups of graphs and digraphs
https://pallini.di.uniroma1.it/
/opt/homebrew/Cellar/nauty/2.8.6 (79 files, 9.1MB) *
Poured from bottle using the formulae.brew.sh API on 2023-02-18 at 16:54:53
From: https://github.com/Homebrew/homebrew-core/blob/HEAD/Formula/nauty.rb
License: Apache-2.0
==> Analytics
install: 116 (30 days), 319 (90 days), 1,280 (365 days)
install-on-request: 57 (30 days), 133 (90 days), 620 (365 days)
build-error: 0 (30 days)

I attach one config.log. config.log Perhaps I should add that this is on Apple Silicon Macs ("M" series).

GMS103 commented 1 year ago

FWIW, after ./configure --without-system-nauty one has that make ptestlong succeeds.

dcoudert commented 1 year ago

The issues with nauty_gentreeg are bugs introduced in version 2.8.6 that have already been reported upstream (https://mailman.anu.edu.au/pipermail/nauty/2023-January.txt).

With nauty 2.7.r1 (current version for Sagemath)

MAC-04017247:nauty27r1 dcoudert$ ./gentreeg 1
>A ./gentreeg Z=0:0 D=0 n=1
:@
>Z 1 trees generated in 0.00 sec
MAC-04017247:nauty27r1 dcoudert$ ./gentreeg 2
>A ./gentreeg Z=1:1 D=1 n=2
:An
>Z 1 trees generated in 0.00 sec
MAC-04017247:nauty27r1 dcoudert$ ./gentreeg 3
>A ./gentreeg Z=2:2 D=2 n=3
:Bc
>Z 1 trees generated in 0.00 sec

With nauty 2.8.6

MAC-04017247:nauty2_8_6 dcoudert$ ./gentreeg 1
>A ./gentreeg Z=0:0 D=0 n=0
:@
>Z 1 trees generated in 0.00 sec
MAC-04017247:nauty2_8_6 dcoudert$ ./gentreeg 2
>A ./gentreeg Z=0:0 D=0 n=0
>Z 0 trees generated in 0.00 sec
MAC-04017247:nauty2_8_6 dcoudert$ ./gentreeg 3
>A ./gentreeg Z=0:0 D=0 n=0
:Bc
>Z 1 trees generated in 0.00 sec

The issues with geng are due to the introduction of new parameters in version 2.8.6, as documented in https://pallini.di.uniroma1.it/changes24-28.txt. We will have to update the doctests when we will upgrade to a newer version:

  - geng got sigificantly faster for connected graphs with a
    small number of edges.  However, if you want trees the program
    gentreeg is still much faster.  There are also new options:
      -k  generate graphs without K4
      -T  generate chordal graphs
      -S  generate split graphs
      -P  generate perfect graphs
      -F  generate claw-free graphs
    All the options can be used in combination unless the program
    complains.

So we have to wait for the release of a corrected version of nauty. Meanwhile, we may restrict versions to 2.7.r1.

dimpase commented 1 year ago

Has this been reported to Homebrew? They probably don't know that they ship a buggy version. (Brendan McKay sent me a patch for 2.8.6 some time ago)

dcoudert commented 1 year ago

No.

EmmanuelCharpentier commented 1 year ago

I reported this for about 5 Sagemath beta (last time here) on Debian testing and Debian's nauty, which is 2.8.6.

dcoudert commented 1 year ago

As also discussed in #34133, a temporary solution is to restrict nauty to version 2.7.r1. Unfortunately, I don't know how to modify the build scripts to do that.

dimpase commented 1 year ago

fortunately, Gentoo has patched 2.8.6 - their package is sci-mathematics/nauty-2.8.6-r1. However, pkg-config still reports 2.8.6 (well, not sure whether this is a Gentoo bug, or nauty bug, or neither)

The best would be to test the output of gentreeg 2 for correctness. Somehow, it goes (mostly) to stderr, so one needs |&, not just | in the pipe.

$ gentreeg 2 |& grep "Z 1 trees"
>Z 1 trees generated in 0.00 sec

(there will be no output in the buggy case)

dimpase commented 1 year ago

No.

well, dear macOS users, please pay you open source dues and report bugs ;-)

GMS103 commented 1 year ago

Done here (but I am not sure it is the good place):

https://github.com/Homebrew/homebrew-core/issues/125101

Guillermo

On Wed, 8 Mar 2023 at 00:59, Dima Pasechnik @.***> wrote:

Has this been reported to Homebrew? They probably don't know that they ship a buggy version. (Brendan McKay sent me a patch for 2.8.6 some time ago)

dimpase commented 1 year ago

Fixed in Homebrew: https://github.com/Homebrew/homebrew-core/pull/125117

GMS103 commented 1 year ago

I still get some failing tests. The patched nauty from Homebrew is version 2.8.6_1. It gives

% gentreeg 2
>A gentreeg Z=0:0 D=0 n=0
:An
>Z 1 trees generated in 0.00 sec
% gentreeg 3
>A gentreeg Z=0:0 D=0 n=0
:Bc
>Z 1 trees generated in 0.00 sec
% gentreeg 4
>A gentreeg Z=0:0 D=0 n=0
:Cdf
:Ccf
>Z 2 trees generated in 0.00 sec
%

which does not seem correct to me.

dimpase commented 1 year ago

Huh? On 2 vertices - 1 tree: o---o ($A_2$ diagram). As well as on 2: o---o---o - $A_3$-diagram. There are 2 non-isomorphic trees on 4 vertices: 3-path, i.e. $A_4$-diagram, and a claw with 3 fingers, i.e. $D_4$ diagram. What's wrong here?

It's https://oeis.org/A000055

GMS103 commented 1 year ago

Sorry, Dima, this is what I mean (from make ptestlong).

**********************************************************************
File "src/sage/graphs/generators/families.py", line 3662, in sage.graphs.generators.families.nauty_gentreeg
Failed example:
    print(next(gen))
Expected:
    >A ...gentreeg Z=2:3 D=3 n=4
Got:
    >A /opt/homebrew/bin/gentreeg Z=0:0 D=0 n=0
    <BLANKLINE>
**********************************************************************
File "src/sage/graphs/generators/families.py", line 3689, in sage.graphs.generators.families.nauty_gentreeg
Failed example:
    list(graphs.nauty_gentreeg("3", debug=True))
Expected:
    ['>A ...gentreeg Z=2:2 D=2 n=3\n', Graph on 3 vertices]
Got:
    ['>A /opt/homebrew/bin/gentreeg Z=0:0 D=0 n=0\n', Graph on 3 vertices]
**********************************************************************
dimpase commented 1 year ago

OK, more things to replace with ... (they changed the meaning of parameter Z=)

GMS103 commented 1 year ago

For other people arriving here, I quote Dima:

Actually, one can patch 2.8.6, as reported by upstream: https://mailman.anu.edu.au/pipermail/nauty/2023-January.txt

GMS103 commented 1 year ago

Sorry, my PR arrives too late (I did not see Gonzalo's).

dcoudert commented 1 year ago

I marked PR #35327 as duplicate, but I don't know if it is enough.

mkoeppe commented 1 year ago

Can this be closed?

GMS103 commented 1 year ago

I think so. Should/Could I do it?