Graphs: obtain distance-regular graphs from generalised quadrangles

[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.

Depends on #30223
Depends on #30509

CC: @dimpase

Component: graph theory

Author: Ivo Maffei

Branch/Commit: 3449361

Reviewer: Dima Pasechnik

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

[Ivo-Maffei]

comment:1

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

[Ivo-Maffei]

Branch: public/graphs/30337

[Ivo-Maffei]

Commit: b98b5e0

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

[sagetrac-git]

Changed commit from b98b5e0 to 7753054

[dimpase]

comment:3

it seems that the latest changes should be merged in.

[sagetrac-git]

Changed commit from 7753054 to 0d92ec4

[sagetrac-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]

comment:5

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.

diff --git a/src/sage/graphs/generators/distance_regular.pyx b/src/sage/graphs/generators/distance_regular.pyx
index 094f9bdc6a..7f8df1250d 100644
--- a/src/sage/graphs/generators/distance_regular.pyx
+++ b/src/sage/graphs/generators/distance_regular.pyx
@@ -648,23 +648,25 @@ def BilinearFormsGraph(const int d, const int e, const int q):
         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,11 +675,15 @@ def BilinearFormsGraph(const int d, const int e, const int q):
 
     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))

[Ivo-Maffei]

comment:6

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

[sagetrac-git]

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

376d459

convert matrices in bilinearFormsGraph to integers to lower memory requirements

[sagetrac-git]

Changed commit from 0d92ec4 to 376d459

[dimpase]

comment:8

Replying to @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.

[dimpase]

Reviewer: Dima Pasechnik

[sagetrac-git]

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

ec44560

a python style fix

[sagetrac-git]

Changed commit from 376d459 to ec44560

[vbraun]

comment:12

**********************************************************************
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
**********************************************************************

[sagetrac-git]

Changed commit from 5977681 to 3c3b4b5

[Ivo-Maffei]

comment:19

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]

comment:20

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

[sagetrac-git]

Changed commit from 3c3b4b5 to f880352

[sagetrac-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]

comment:22

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

[Ivo-Maffei]

comment:23

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]

comment:24

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

[Ivo-Maffei]

comment:25

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

[dimpase]

comment:26

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

[sagetrac-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

[sagetrac-git]

Changed commit from f880352 to 8c12a8f

[sagetrac-git]

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

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

[sagetrac-git]

Changed commit from 8c12a8f to c97bda5

[sagetrac-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

[sagetrac-git]

Changed commit from c97bda5 to d9c9149

[Ivo-Maffei]

Changed dependencies from #30223, #30329 to #30223, #30509

[dimpase]

comment:32

please also merge in the latest develop beta, beta12.

[sagetrac-git]

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

3449361

Merge branch 9.2.beta12 into t/30337

[sagetrac-git]

Changed commit from d9c9149 to 3449361

[dimpase]

comment:34

OK, good!

[vbraun]

Changed branch from public/graphs/30337 to 3449361