Graphs: obtain distance-regular graphs from generalised quadrangles

[gh-Ivo-Maffei]

Added code that constructs distance-regular graphs from generalised quadrangles with spread. Also added a function that checks whether an distance-regular graph can be built using the method above.

[gh-Ivo-Maffei]

This is where #30223 gets used.

---

Last 10 new commits:

​51d73b4	Merge 30312 into 30329
​06b8d25	code for symmetric matrices
​9991f4f	added file
​931859b	added code
​7555255	cleaned up code; added docstring; added tests
​0e82896	removed gap int; fixed some docstrings
​ee0e18f	added references
​51517fe	Merge 30223 into drg_fam2
​190dd4b	added code to generate drg from GQs
​b98b5e0	fix doctests; added references

[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
​d2ff33f	Merge branch 30312 into 30329 (removed 29886)
​7753054	Merge branch 30329 into 30337

[dimpase]

it seems that the latest changes should be merged in.

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​48395a1	use integer vectors in bilinear form to represents matrices
​339b4f5	fix docstrings
​c081dde	Merge branch '30312' into 30329
​ac45a62	some code formatting and docstrings
​e96c7c7	Merge branch '30329' into 30337
​a0463d5	fix docsrtings; renamed module
​5d16394	renamed in design_catalog
​e6ff3fa	Merge branch 't/30223' into t/30337
​3e1df8c	added const to half cube
​0d92ec4	Merge branch 't/30329' into t/30337

[dimpase]

I still got Memory Error in the longest bilinear forms graphs test, so here is an optimisation that reduces memory consumption by packing matrices into int, with it all tests pass.

src/sage/graphs/generators/distance_regular.pyx

@@ -648 +648 @@
         sage: K.is_isomorphic(G)
         True
     """
-    from sage.combinat.integer_vector import IntegerVectors
+    from itertools import product as cartprod
 
     Fq = GF(q)
     Fqelems = list(Fq)
-    matricesOverq = IntegerVectors(k=d*e, max_part=q-1)
-
+    dim = d*e
+    matricesOverq = cartprod(*([range(q)]*dim))
+    qv = [int(q**jj) for jj in range(dim)]
     rank1Matrices = []
+    vsp = VectorSpace(Fq, e)
     for u in VectorSpace(Fq, d):
         if u.is_zero() or not u[u.support()[0]].is_one():
             continue
 
-        for v in VectorSpace(Fq, e):
+        for v in vsp:
             if v.is_zero():
                 continue
 
             sig_check()
-            M = [0] * (d*e)
+            M = [0] * dim
             for row in range(d):
                 for col in range(e):
                     M[e*row + col] = u[row] * v[col]
@@ -673 +675 @@
 
     edges = []
     for m1 in matricesOverq:
-        m1 = tuple(map(lambda x: Fqelems[x], m1))
+        im1 = 0
+        for jj in range(dim):
+            im1 += m1[jj] * qv[jj]
         for m2 in rank1Matrices:
             sig_check()
-            m3 = tuple([m1[i] + m2[i] for i in range(d*e)])
-            edges.append((m1, m3))
+            im3 = 0
+            for jj in range(dim):
+                im3 += Fqelems.index(Fqelems[m1[jj]] + m2[jj]) * qv[jj]
+            edges.append((im1, im3))
 
     G = Graph(edges, format='list_of_edges')
     G.name("Bilinear forms graphs over F_%d with parameters (%d, %d)"%(q, d, e))

[gh-Ivo-Maffei]

Is this conversion to integers needed for the other forms graphs?

[git]

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

​376d459

convert matrices in bilinearFormsGraph to integers to lower memory requirements

[dimpase]

Replying to gh-Ivo-Maffei:

Is this conversion to integers needed for the other forms graphs?

it certainly lowers memory consumption, but I would not worry too much about it. There are much better ways to handle this, as implemented in GAP package GRAPE.

[git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

​ec44560

a python style fix

[vbraun]

**********************************************************************
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 "/home/buildbot/slave/sage_git/build/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 715, in _run
      File "/home/buildbot/slave/sage_git/build/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 1139, in compile_and_execute
      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 691, in sage.graphs.generators.distance_regular.BilinearFormsGraph (build/cythonized/sage/graphs/generators/distance_regular.c:11929)
      File "/home/buildbot/slave/sage_git/build/local/lib/python3.7/site-packages/sage/graphs/graph.py", line 1261, in __init__
      File "/home/buildbot/slave/sage_git/build/local/lib/python3.7/site-packages/sage/graphs/generic_graph.py", line 10935, in add_edges
      File "sage/graphs/base/sparse_graph.pyx", line 1645, in sage.graphs.base.sparse_graph.SparseGraphBackend.add_edge (build/cythonized/sage/graphs/base/sparse_graph.c:17623)
      File "sage/graphs/base/sparse_graph.pyx", line 1096, in sage.graphs.base.sparse_graph.SparseGraph.add_arc_label (build/cythonized/sage/graphs/base/sparse_graph.c:13067)
    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
**********************************************************************

[vbraun]

Does that really test a code path that cannot be tested in <1s?

[gh-Ivo-Maffei]

I cannot reproduce the error.

All my code do is calling Graph(edges, format='list_of_edges'). The edges list is long (6652854) but I believe the code path (i.e. the full stack of function calls) should not differ from Graph([(0,1)], format='list_of_edges').

I can change the doctest to importing BilinearFormsGraph directly from sage.graphs.generators.distance_regular if this solves the issue, but I don't know how to test it myself.

[dimpase]

I agree with Volker (vbraun) that this doctest takes way too long. Mark it not tested and add graphs.BilinearFormsGraph(3,4,2) instead - this takes <3 sec.

[git]

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

​5977681

removed long doctests

[dimpase]

Please run

./sage -tp --long --verbose src/sage/graphs/generators/distance_regular.pyx

to see what tests are the longest. This file is still by far the slowest to test in sage/graphs/, 3 times as long as anything else there. GrassmannGraph(2, 6, 3) and DoubleGrassmannGraph(3, 2) are the two slowest ones (>30 sec each on my oldish X1 Carbon Lenovo, and they aren't even tagged long time!), but there are more.

[git]

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

​3c3b4b5

added long time flags

[gh-Ivo-Maffei]

I marked everything that took more than 1s as long.

I think one should change the default value for --warn-long (it is usually 2 min) if 30s are long.

[vbraun]

The buildbot limits the available memory to encourage writing efficient unit tests, hence the MemoryError?

[git]

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

​4675366	replaced long doctest
​d5555b4	Merge branch 't/30312' into t/30329
​f880352	Merge branch 't/30329' into t/30337

[dimpase]

let's wait for the next beta/rc, to lessen the rebase work.

[gh-Ivo-Maffei]

Replying to dimpase:

let's wait for the next beta/rc, to lessen the rebase work.

I'm having issues with beta11 not starting for an import error on libgsl.23.dylib Has this issue been brought up yet or am I the only one?

[dimpase]

How do you get gsl in your installation? Does it come from the system/Homebrew/conda, or do you build it?

[gh-Ivo-Maffei]

It is in sage/local/lib/. I can send you the crash report, if you wish

[dimpase]

gsl has been updated in just merged #29483. Perhaps you need to run ./sage -f gsl && make build

[git]

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

​05c9593	Merge branch 'develop' of git://trac.sagemath.org/sage into t/30337
​97f0450	Merge branch 'develop' into t/30312
​2a1861d	Merge branch 't/30312' into t/30329
​5344f35	added long time flags and fixed van Lint name
​9e69f0d	missing # long time
​49cdcc1	Merge branch 't/30312' into t/30329
​ea30040	added long time flags
​4bcdb3c	typos and TeX fixes
​feabf4f	better index section, uniform naming
​8c12a8f	Merge branch 't/30329' into t/30337

[git]

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

​1fdcad9	fixed typo
​c97bda5	Merge branch 't/30329' into t/30337

[git]

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

​3024980	faster implementation of HalfCube
​898fbee	added positions to HalfCube
​d9c9149	Merge branch 't/30509' into t/30337

[dimpase]

please also merge in the latest develop beta, beta12.

[git]

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

​3449361

Merge branch 9.2.beta12 into t/30337

[dimpase]

OK, good!