Graphs: a few distance-regular graphs

[gh-Ivo-Maffei]

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

[dcoudert]

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().

[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

[gh-Ivo-Maffei]

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]

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.

[git]

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

​27c2868

fixed typos and formatting

[gh-Ivo-Maffei]

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]

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.

[git]

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

​faf04e9

itertools to simplify code

[dimpase]

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

[git]

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

​bc19673

change optional flag for atlasrep

[dimpase]

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.

[git]

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

​12d3e1e

renamed locally GQ function and added references

[gh-Ivo-Maffei]

Replying to dimpase:

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)

I looked closer at what is written in BCN and they say the graph is the unique amply regular graph with \mu = 6. I'm not sure that's true, tough.

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

I've added them and I think the construction of locally_GQ42_distance_transitive_graph is actually due to you as is not the one given in BCN.

[git]

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

​e91e058

forgot to rename graph

[dimpase]

Replying to gh-Ivo-Maffei:

Replying to dimpase:

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)

I looked closer at what is written in BCN and they say the graph is the unique amply regular graph with \mu = 6.

yes, that's correct - you do need mu=6, though. There is a locally GQ(4,2) graph with mu=18 (an s.r.g) graphs.strongly_regular_graph(126,45,12,18)

I'm not sure that's true, tough.

so, add that mu=6 there then.

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

I've added them and I think the construction of locally_GQ42_distance_transitive_graph is actually due to you as is not the one given in BCN.

huh? see [BCN], 13.2.C and p.397 for references. It seems that [688] is the earliest - but why don't you just refer to [BCN], 13.2.C ?

[gh-Ivo-Maffei]

I cited BCN 13.2.C for a description of the graph, however the construction that takes a normal subgroup of 3^2.U4(3).D8 is hard to deduce from that section and I think it is something you came up during one of our meetings. I can remove the sentence citing you if you wish.

[dimpase]

OK, fine.

[dcoudert]

small indentation issue

-    for c1, c2 in itertools.combinations(cocliques, 2):
-        if len(c1.intersection(c2)) == 8:
-                edges.append((c1, c2))
+    for c1, c2 in itertools.combinations(cocliques, 2):
+        if len(c1.intersection(c2)) == 8:
+            edges.append((c1, c2))

once corrected, you can set back the ticket to positive review.

[git]

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

​6317708

fixed indentation issue

[dcoudert]

#30277 removes file src/module_list.py from sagemath, so this ticket should not write in it.

When this part is removed from this ticket, you can set it back to positive review.

Thanks.

[dimpase]

Oh, right, this ticket should be based on #30277, indeed. Sorry for missing this.

[dimpase]

my understanding is that you just have to remove any changed to src/module_list.py - the rest is the same.

[dimpase]

Two-stage rebase worked for me -

1) rebase the current branch over the latest beta (beta7)

2) rebase the result over the branch of #30277

[dcoudert]

May be you should push the result to a new branch ? I don't know if Ivo knows how to do that (not sure I can do it myself, I'm a basic git user...).

[gh-Ivo-Maffei]

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

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

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

[git]

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

​4e17fd7

fixed bug introduced by removing module_list

[gh-Ivo-Maffei]

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]

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

[dimpase]

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

[dimpase]

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

[gh-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:

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

[git]

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

​e063b5e

simplified import

[dimpase]

Replying to gh-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]

test, please ignore.

[gh-Ivo-Maffei]

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]

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

[dimpase]

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

[git]

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

​574960d

added gap_packages flag to atlasrep

[dimpase]

LGTM