Graphs: a few distance-regular graphs

[Ivo-Maffei]

Implemented a few distance-regular graphs for a database of such graphs.

Depends on #30277

CC: @dimpase

Component: graph theory

Keywords: distance_regular_graph drg

Author: Ivo Maffei

Branch/Commit: 574960d

Reviewer: David Coudert, Dima Pasechnik

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

[dcoudert]

comment:2

Hello,

can you move the file distance_regular.pyx to the subdirectory generators/. This is certainly a better place for generators.

Also, what's the added value of using python instead of python here ? Do you have any plan for further improvements ? I'm not against python here, I just want to understand the motivation.

The patchbot reports an issue with gap during the construction G = graphs.graph_3O73().

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

a5ad68c	added a few sporadic distance regular graphs
da2c8f7	moved file to generators; fixed tests

[sagetrac-git]

Changed commit from cd1be58 to da2c8f7

[Ivo-Maffei]

comment:4

Replying to @dcoudert:

can you move the file distance_regular.pyx to the subdirectory generators/.

Sure!

Also, what's the added value of using python instead of python here ? Do you have any plan for further improvements ?

I'm using Cython mainly to speed things up a bit. I have quite a lot of graphs that will end up here, but I thought that many small tickets are better than a huge one.

The patchbot reports an issue with gap during the construction G = graphs.graph_3O73().

Should be fixed now.

(Also rebased branch on 9.2.beta6)

[dcoudert]

comment:5

I fully agree that small tickets are better ;)
In the future, i suggest to name branch like public/graphs/30240 so that I can directly push a review commit for minor corrections.

A few comments:

• ensure that comments are formatted in 80 columns mode. Not sure it is the case now

• typos

-Dabase of distance regular graphs
+Database of distance regular graphs

• several times

-    This is a distance-regular graph with intersecion array
+    This is a distance-regular graph with intersection array

• wha's the reason for choosing 100 ?
• PEP8

-        for j in range(i+1,100):
+        for j in range(i + 1, 100):

-                sC2 = frozenset(cocliques[j])
-                edges.append( (sC,sC2) )
+                edges.append((sC, rozenset(cocliques[j])))

-    G = Graph(edges,format="list_of_edges")
+    G = Graph(edges, format="list_of_edges")

-    H = libgap.AtlasGroup("3^2.U4(3).D8",libgap.NrMovedPoints,756)
+    H = libgap.AtlasGroup("3^2.U4(3).D8", libgap.NrMovedPoints, 756)

-    G = Graph(libgap.Orbit(N,[1,9],libgap.OnSets), format='list_of_edges')
+    G = Graph(libgap.Orbit(N, [1, 9], libgap.OnSets), format='list_of_edges')

• if x == 0 -> if not x

• x == z2+1 -> x == z2 + 1 this is to improve readability (PEP8)

• #create e_i -> # create e_i this is to avoid confusion with compilers macros

• ei = [0]*6 -> ei = [0] * 6 or directly ei = [0, 0, 0, 0, 0, 0] ?

• possibly simpler code

-    def has_edge(u,v):
-        com = 0
-        for i in range(6):
-            com += u[i].conjugate() * v[i]
-
-        if com == 2:
-            return True
-        return False
+    def has_edge(u, v):
+        return sum(u[i].conjugate() * v[i] for i in range(6)) == 2

• you could add a loop so set all K[i] to immutable first. I think you do that many times.

[dcoudert]

Reviewer: David Coudert

[sagetrac-git]

Changed commit from da2c8f7 to 27c2868

[sagetrac-git]

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

27c2868

fixed typos and formatting

[Ivo-Maffei]

comment:7

Replying to @dcoudert:
Thanks for the feedback

• ensure that comments are formatted in 80 columns mode. Not sure it is the case now

Unless my editor is wrong, there are only 2 lines that reach (and don't exceed) column 80 (line 40 and 243).

• wha's the reason for choosing 100 ?

There are only 100 cocliques, so to iterate over the list I use range(100).

• if x == 0 -> if not x

Personally I find the rhs more confusing as I read it as if x is not None (especially since x is not an int).
I changed it to if x.is_zero(). If PEP8 or Sage insist with if not x, I'll change it right away.

[dcoudert]

comment:8

I'm not insisting for the not x ;)

may be you can do:

cocliques = [frozenset(c) for c in DC.cliques_maximum()]

edges = []
import itertools
for sC, sC2 in itertools.combinations(cocliques, 2):
    if len(sC.intersection(sC2)) == 8:
        edges.append((sC, sC2))

similarly

-    for i in range(length):
-        for j in range(i + 1, length):
+    for Ki, Kj in itertools.combinations(K, 2):

I agree it's minor changes.

[sagetrac-git]

Changed commit from 27c2868 to faf04e9

[sagetrac-git]

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

faf04e9

itertools to simplify code

[dimpase]

comment:10

AtlasRep is always installed together with GAP, it's not a part of gap_packages.
These tests, however, need to be tagged with internet rather tnan gap_packages, as AtlasRep pulls data from the net (and caches it if it can).

[sagetrac-git]

Changed commit from faf04e9 to bc19673

[sagetrac-git]

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

bc19673

change optional flag for atlasrep

[dimpase]

comment:13

The name of the graph function locally_GQ42_graph() is not good. There are more locally GQ42 graphs (I even found one myself many years ago, see https://mathscinet.ams.org/mathscinet-getitem?mr=1357771 :-))

Probably locally_GQ42_distance_transitive_graph() is better.
(There is also the 3-fold quotient of this graph - but it is strongly regular, so no confusion should arise).

Also the docstring for this graph should be improved; it says

 Return the unique amply regular graph which is locally a generalised
 quadrangle.

but this is not unique such a graph, as it's 3-fold quotient is also amply regular
(all strongly regular graphs are)

Please also add REFERENCES: sectuion to all the graphs in this branch.

[sagetrac-git]

Changed commit from bc19673 to 12d3e1e

[Ivo-Maffei]

comment:29

I can do it. You would need to wait until my update to sage 9.2.beta7 is complete, though

[sagetrac-git]

Changed commit from 6317708 to 7754591

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

01b96b0	Merge branch 't/29701/replace_use_of_module_list_optionalextension' into t/29950/build_sagelib_using_installed_sage_setup
2818739	Merge branch 't/29950/build_sagelib_using_installed_sage_setup' into t/30277/remove_src_module_list_py
89aaa5b	added a few sporadic distance regular graphs
2f8ca0f	moved file to generators; fixed tests
7a906b1	fixed typos and formatting
8164445	itertools to simplify code
6a15420	change optional flag for atlasrep
92537c0	renamed locally GQ function and added references
6f3754b	forgot to rename graph
7754591	fixed indentation issue

[dimpase]

comment:31

unfortunately my (perhaps wrong) tests indicate that #30277 is broken. Some pyx modules are not discovered and built in, somehow

[sagetrac-git]

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

4e17fd7

fixed bug introduced by removing module_list

[sagetrac-git]

Changed commit from 7754591 to 4e17fd7

[Ivo-Maffei]

comment:33

I found a bug because the module sage.graphs.distance_regular had path sage/graphs/generators/distance_regular.pyx
Everything else seems to work. Do you have a specific example where things go bad?

[dimpase]

comment:34

graph_3073() does not work for me as libgap.AtlasGroup("3.O7(3)", libgap.NrMovedPoints, 1134) returns fail. Did it ever work?

[dimpase]

comment:35

It seems that AtlasGroup only knows 3.O7(3) as a 27-dimensional matrix group over GF(4).

[dimpase]

comment:36

Replying to @sagetrac-git:

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

4e17fd7

fixed bug introduced by removing module_list

it is less clutter to write there simply

from .generators import smallgraphs, distance_regular

[Ivo-Maffei]

comment:37

Replying to @dimpase:

graph_3073() does not work for me as libgap.AtlasGroup("3.O7(3)", libgap.NrMovedPoints, 1134) returns fail. Did it ever work?

I get the following:

sage: graphs.graph_3O73()
Distance transitive graph with automorphism group 3.O_7(3): Graph on 1134 vertices
sage: G=_
sage: G.is_distance_regular(True)
([117, 80, 24, 1, None], [None, 1, 12, 80, 117])
sage: libgap.DisplayAtlasInfo("3.O7(3)")
Representations for G = 3.O7(3):    (all refer to std. generators 1)
--------------------------------
1: G <= Sym(1134)* rank 7, on cosets of L4(3).2_2<3xL4(3).2_2
2: G <= GL(27a,4)  

Programs for G = 3.O7(3):    (all refer to std. generators 1)
-------------------------
- kernels*:
  3.O7(3) -> O7(3)*             
- maxes (11 out of 15):
   1*:  6_1.U4(3).2_2           
   2*:  3.3^5:U4(2):2           
   3*:  3xL4(3).2_2             
   4*:  3.G2(3)                 
   6*:  3.(3^(3+3):L3(3))       
   7*:  3xS6(2)                 
   9*:  3.3^(1+6)_+.(2A4xA4).2  
  12*:  3x(2^2xU4(2)):2         
  13*:  2^6:3A7                 
  14*:  3xS6xS4                 
  15*:  3.(A4x2(A4xA4).2).2

Maybe we have different versions of GAP installed?

% sage -gap
 ┌───────┐   GAP 4.10.2 of 19-Jun-2019
 │  GAP  │   https://www.gap-system.org
 └───────┘   Architecture: x86_64-apple-darwin19.4.0-default64-kv3
 Configuration:  gmp 6.0.0, readline

[sagetrac-git]

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

e063b5e

simplified import

[sagetrac-git]

Changed commit from 4e17fd7 to e063b5e

[dimpase]

comment:39

Replying to @Ivo-Maffei:

Replying to @dimpase:

graph_3073() does not work for me as libgap.AtlasGroup("3.O7(3)", libgap.NrMovedPoints, 1134) returns fail. Did it ever work?

I get the following:

right, sorry, I got the error because I didn't have gap_packages installed, and they provide extra data needed in this case. That is, these tests should be tagged with gap_packages, too, not only internet.

[dimpase]

comment:40

test, please ignore.

[Ivo-Maffei]

comment:41

Replying to @dimpase:

right, sorry, I got the error because I didn't have gap_packages installed, and they provide extra data needed in this case. That is, these tests should be tagged with gap_packages, too, not only internet.

Just to be sure, only the tests for graph_7073 or does locally_GQ42_distance_transitive_graph need it too?

Is there a way to check what optional packages are really needed without having another sage installation?

[dimpase]

comment:42

make gap_packages-clean should uninstall this one. Iirc, only that one graph needed
gap_packages installed, not sure, away from kbd now.

[dimpase]

comment:43

Just tag all the tests using AtlasGroup with gap_packages, in addtion to internet.

[sagetrac-git]

Changed commit from e063b5e to 574960d

[sagetrac-git]

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

574960d

added gap_packages flag to atlasrep

[dimpase]

comment:46

LGTM

[vbraun]

Changed branch from u/gh-Ivo-Maffei/drg_sporadic1 to 574960d