Graphs: more classical parameters distance regular graphs

[Ivo-Maffei]

Added three families of distance regular graphs, they are based, respectively, on bilinear forms, alternating forms and hermitian forms.

Also moved AztecDiamondGraph to families of graphs rather than basic structures.

Depends on #30303

CC: @dimpase

Component: graph theory

Author: Ivo Maffei

Branch/Commit: 9e69f0d

Reviewer: Dima Pasechnik

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

[Ivo-Maffei]

Last 10 new commits:

efa9340	some code formatting
be18963	added some sig_checks
7f4d042	code for symmetric matrices
e4957c2	added examples and tests
10f063f	fixed formatting
c4f1e6f	removed trailing whitespaces
7528f25	fixed more code formatting; allow f=None for nomal symmetric matrices
e171598	added bilinear, alternating and hermitian form graphs
7fcf73e	removed sporadic g; fixed doctests
b921ccf	removed random s

[Ivo-Maffei]

Branch: public/graphs/30312

[Ivo-Maffei]

Commit: b921ccf

[Ivo-Maffei]

comment:2

Remainder to update once #30303 and #29886 are sorted

[dimpase]

comment:3

..FormGraph should be ..FormsGraph, as these are graphs with vertex sets being sets of forms, right?

[Ivo-Maffei]

comment:4

Yes, I've changed it and also merged #30303 (with the update to 9.2.beta8).
If #29886 will take too much time, I could remove the dependency and generate the needed matrices with the ...FormsGraph method.
This is what I initially did ages ago.

Of course as soon as #29886 or something similar gets fixed, I can change back these functions to something neater.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

19b859e	moved and renamed orthogonal dual polar
d6a403b	Merge branch 9.2.beta8 into 30303
d7453fa	removed cython code; added imports
562283f	Merge branch 30303 (and sage 9.2.beta8) into 30312
503bc12	renamed functions; added meataxe flag to doctests

[sagetrac-git]

Changed commit from b921ccf to 503bc12

[sagetrac-git]

Changed commit from 503bc12 to 38577a8

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

9a3e609	reverted changes to matrix_space.py
e78c2d0	removed dependecies from symmetric generator
38577a8	fixed bug with matrix generation; added meataxe flag to tests

[Ivo-Maffei]

comment:7

Now this should work without #29886.
It's much slower but it should do for now.

[Ivo-Maffei]

Changed dependencies from #30303, #29886 to #30303

[dimpase]

comment:8

very long doctests that need more than 1 minute, say, should be tagged as # not tested - by the way, on my machine some long doctests with meataxe used crash with Memory Error, while complete if run at the sage prompt (due to doctest parallelism I guess).

Also, there is a typo: bilienar -> bilinear

[dimpase]

Reviewer: Dima Pasechnik

[sagetrac-git]

Changed commit from 38577a8 to cf5243d

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ad6944f	Merge branch 9.2.beta9 into 30312
cf5243d	fix doctests

[Ivo-Maffei]

comment:10

I added the # not tested flag and run all doctests with and without the --long flag.
They all pass in roughly 2 min.

[dimpase]

comment:44

by the way, nothing prevents you from trying to use the meataxe backend for matrices, and falling back on the default one if it's not available.

[dimpase]

comment:45

If you like to add the meataxe speed up option, please do, else it's good as it is.

[Ivo-Maffei]

comment:46

Replying to @dimpase:

If you like to add the meataxe speed up option, please do, else it's good as it is.

The current code is faster than any previous version that used meataxe
I'm not sure how to speed things up more with meataxe

[vbraun]

Changed branch from public/graphs/30312 to 339b4f5

[vbraun]

Changed commit from 339b4f5 to none

[vbraun]

comment:49

**********************************************************************
File "src/sage/graphs/generators/distance_regular.pyx", line 629, in sage.graphs.generators.distance_regular.BilinearFormsGraph
Failed example:
    G = graphs.BilinearFormsGraph(3,3,3)  # long time (20 s)
Exception raised:
    Traceback (most recent call last):
      File "/var/lib/buildbot/slave/sage_git/build/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 715, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/var/lib/buildbot/slave/sage_git/build/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 1139, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.generators.distance_regular.BilinearFormsGraph[2]>", line 1, in <module>
        G = graphs.BilinearFormsGraph(Integer(3),Integer(3),Integer(3))  # long time (20 s)
      File "sage/graphs/generators/distance_regular.pyx", line 679, in sage.graphs.generators.distance_regular.BilinearFormsGraph (build/cythonized/sage/graphs/generators/distance_regular.c:11661)
        m3 = tuple([m1[i] + m2[i] for i in range(d*e)])
    MemoryError
**********************************************************************
File "src/sage/graphs/generators/distance_regular.pyx", line 630, in sage.graphs.generators.distance_regular.BilinearFormsGraph
Failed example:
    G.order()  # long time (due to above)
Expected:
    19683
Got:
    512
**********************************************************************

[Ivo-Maffei]

comment:50

I made the same changes of #30337 commit 5977681

[Ivo-Maffei]

Changed branch from 339b4f5 to public/graphs/30312

[Ivo-Maffei]

Commit: 4675366

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

97f0450

Merge branch 'develop' into t/30312

[sagetrac-git]

Changed commit from 4675366 to 97f0450

[dimpase]

comment:52

some tests should still be tagged long:

Trying (line 388):    G = graphs.distance_3_doubly_truncated_Golay_code_graph()
Expecting nothing
ok [10.27 s]
...

Trying (line 582):    G = graphs.UstimenkoGraph(5, 2)
Expecting nothing
ok [22.18 s]
Trying (line 583):    G.order()
Expecting:
    2295
ok [0.00 s]
Trying (line 585):    G.is_distance_regular(True)
Expecting:
    ([310, 224, None], [None, 1, 35])
ok [11.42 s]

Trying (line 633):    G.is_distance_regular(True)
Expecting:
    ([105, 84, 48, None], [None, 1, 6, 28])
ok [17.22 s]

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

5344f35

added long time flags and fixed van Lint name

[sagetrac-git]

Changed commit from 97f0450 to 5344f35

[dimpase]

comment:54

#long tag missing on line 588, leading to a failing doctest:

File "src/sage/graphs/generators/distance_regular.pyx", line 588, in sage.graphs.generators.distance_regular.UstimenkoGraph
Failed example:
    G.is_distance_regular(True)
Expected:
    ([390, 243, None], [None, 1, 130])
Got:
    ([70, 32, None], [None, 1, 35])

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

9e69f0d

missing # long time

[sagetrac-git]

Changed commit from 5344f35 to 9e69f0d

[dimpase]

comment:56

long tests are still a bit too long to my taste, but OK.

[vbraun]

Changed branch from public/graphs/30312 to 9e69f0d