Opened 18 months ago
Closed 18 months ago
#30240 closed enhancement (fixed)
Graphs: a few distanceregular graphs
Reported by:  ghIvoMaffei  Owned by:  

Priority:  major  Milestone:  sage9.2 
Component:  graph theory  Keywords:  distance_regular_graph drg 
Cc:  dimpase  Merged in:  
Authors:  Ivo Maffei  Reviewers:  David Coudert, Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  574960d (Commits, GitHub, GitLab)  Commit:  574960d6141180687fcc749b9b2cef5554ffa59f 
Dependencies:  #30277  Stopgaps: 
Description
Implemented a few distanceregular graphs for a database of such graphs.
Change History (47)
comment:1 Changed 18 months ago by
 Cc dimpase added
 Status changed from new to needs_review
comment:2 followup: ↓ 4 Changed 18 months ago by
comment:3 Changed 18 months ago by
 Commit changed from cd1be589d7735b2ce6dbc6c81ff3a7d2df875042 to da2c8f7392b276acd7e275f6c03e5172e555516b
comment:4 in reply to: ↑ 2 Changed 18 months ago by
Replying to dcoudert:
can you move the file
distance_regular.pyx
to the subdirectorygenerators/
.
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)
comment:5 followup: ↓ 7 Changed 18 months ago by
 Reviewers set to David Coudert
 Status changed from needs_review to needs_work
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 distanceregular graph with intersecion array + This is a distanceregular 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 macrosei = [0]*6
>ei = [0] * 6
or directlyei = [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.
comment:6 Changed 18 months ago by
 Commit changed from da2c8f7392b276acd7e275f6c03e5172e555516b to 27c2868bc0b71e8ee4648de6cef2fb34cf42937a
Branch pushed to git repo; I updated commit sha1. New commits:
27c2868  fixed typos and formatting

comment:7 in reply to: ↑ 5 Changed 18 months ago by
 Status changed from needs_work to needs_review
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.
comment:8 Changed 18 months ago by
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.
comment:9 Changed 18 months ago by
 Commit changed from 27c2868bc0b71e8ee4648de6cef2fb34cf42937a to faf04e91399df2cd384544315ab47dcad4bc379f
Branch pushed to git repo; I updated commit sha1. New commits:
faf04e9  itertools to simplify code

comment:10 Changed 18 months ago by
 Status changed from needs_review to needs_work
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).
comment:11 Changed 18 months ago by
 Commit changed from faf04e91399df2cd384544315ab47dcad4bc379f to bc196736037f659ce6e9bb2b095e806c3e96e9a0
Branch pushed to git repo; I updated commit sha1. New commits:
bc19673  change optional flag for atlasrep

comment:12 Changed 18 months ago by
 Status changed from needs_work to needs_review
comment:13 followup: ↓ 15 Changed 18 months ago by
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/mathscinetgetitem?mr=1357771 :))
Probably locally_GQ42_distance_transitive_graph()
is better.
(There is also the 3fold 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 3fold quotient is also amply regular (all strongly regular graphs are)
Please also add REFERENCES:
sectuion to all the graphs in this branch.
comment:14 Changed 18 months ago by
 Commit changed from bc196736037f659ce6e9bb2b095e806c3e96e9a0 to 12d3e1e898e86adbfb16f3c5e8e9922190fb5d85
Branch pushed to git repo; I updated commit sha1. New commits:
12d3e1e  renamed locally GQ function and added references

comment:15 in reply to: ↑ 13 ; followup: ↓ 17 Changed 18 months ago by
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 3fold 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.
comment:16 Changed 18 months ago by
 Commit changed from 12d3e1e898e86adbfb16f3c5e8e9922190fb5d85 to e91e0585312c21f62324fc1d535cb7f6f9fc9ba0
Branch pushed to git repo; I updated commit sha1. New commits:
e91e058  forgot to rename graph

comment:17 in reply to: ↑ 15 Changed 18 months ago by
Replying to ghIvoMaffei:
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 3fold 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 ?
comment:18 Changed 18 months ago by
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.
comment:19 Changed 18 months ago by
 Reviewers changed from David Coudert to David Coudert, Dima Pasechnik
 Status changed from needs_review to positive_review
OK, fine.
comment:20 Changed 18 months ago by
 Status changed from positive_review to needs_work
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.
comment:21 Changed 18 months ago by
 Commit changed from e91e0585312c21f62324fc1d535cb7f6f9fc9ba0 to 63177084eb5cc97fb68c3a0b728aa2385eab657e
Branch pushed to git repo; I updated commit sha1. New commits:
6317708  fixed indentation issue

comment:22 Changed 18 months ago by
 Status changed from needs_work to positive_review
comment:23 Changed 18 months ago by
 Status changed from positive_review to needs_work
#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.
comment:24 Changed 18 months ago by
Oh, right, this ticket should be based on #30277, indeed. Sorry for missing this.
comment:25 Changed 18 months ago by
my understanding is that you just have to remove any changed to src/module_list.py
 the rest is the same.
comment:26 Changed 18 months ago by
 Dependencies set to #30277
comment:27 Changed 18 months ago by
Twostage rebase worked for me 
1) rebase the current branch over the latest beta (beta7)
2) rebase the result over the branch of #30277
comment:28 Changed 18 months ago by
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...).
comment:29 Changed 18 months ago by
I can do it. You would need to wait until my update to sage 9.2.beta7 is complete, though
comment:30 Changed 18 months ago by
 Commit changed from 63177084eb5cc97fb68c3a0b728aa2385eab657e to 7754591fe4e8b4f56db6857c3598f2863e76d822
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

comment:31 Changed 18 months ago by
unfortunately my (perhaps wrong) tests indicate that #30277 is broken. Some pyx modules are not discovered and built in, somehow
comment:32 followup: ↓ 36 Changed 18 months ago by
 Commit changed from 7754591fe4e8b4f56db6857c3598f2863e76d822 to 4e17fd7fd738e0d1a376a8212fbbf44ea9262646
Branch pushed to git repo; I updated commit sha1. New commits:
4e17fd7  fixed bug introduced by removing module_list

comment:33 Changed 18 months ago by
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?
comment:34 followup: ↓ 37 Changed 18 months ago by
graph_3073()
does not work for me as libgap.AtlasGroup("3.O7(3)", libgap.NrMovedPoints, 1134)
returns fail
. Did it ever work?
comment:35 Changed 18 months ago by
It seems that AtlasGroup
only knows 3.O7(3)
as a 27dimensional matrix group over GF(4).
comment:36 in reply to: ↑ 32 Changed 18 months ago by
comment:37 in reply to: ↑ 34 ; followup: ↓ 39 Changed 18 months ago by
Replying to dimpase:
graph_3073()
does not work for me aslibgap.AtlasGroup("3.O7(3)", libgap.NrMovedPoints, 1134)
returnsfail
. 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 19Jun2019 │ GAP │ https://www.gapsystem.org └───────┘ Architecture: x86_64appledarwin19.4.0default64kv3 Configuration: gmp 6.0.0, readline
comment:38 Changed 18 months ago by
 Commit changed from 4e17fd7fd738e0d1a376a8212fbbf44ea9262646 to e063b5e46a9076c0a5cea1046f22121bb14f7642
Branch pushed to git repo; I updated commit sha1. New commits:
e063b5e  simplified import

comment:39 in reply to: ↑ 37 ; followup: ↓ 41 Changed 18 months ago by
Replying to ghIvoMaffei:
Replying to dimpase:
graph_3073()
does not work for me aslibgap.AtlasGroup("3.O7(3)", libgap.NrMovedPoints, 1134)
returnsfail
. 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
.
comment:40 Changed 18 months ago by
test, please ignore.
comment:41 in reply to: ↑ 39 Changed 18 months ago by
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 withgap_packages
, too, not onlyinternet
.
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?
comment:42 Changed 18 months ago by
make gap_packagesclean
should uninstall this one. Iirc, only that one graph needed
gap_packages installed, not sure, away from kbd now.
comment:43 Changed 18 months ago by
Just tag all the tests using AtlasGroup with gap_packages
, in addtion to internet
.
comment:44 Changed 18 months ago by
 Commit changed from e063b5e46a9076c0a5cea1046f22121bb14f7642 to 574960d6141180687fcc749b9b2cef5554ffa59f
Branch pushed to git repo; I updated commit sha1. New commits:
574960d  added gap_packages flag to atlasrep

comment:45 Changed 18 months ago by
 Status changed from needs_work to needs_review
comment:47 Changed 18 months ago by
 Branch changed from u/ghIvoMaffei/drg_sporadic1 to 574960d6141180687fcc749b9b2cef5554ffa59f
 Resolution set to fixed
 Status changed from positive_review to closed
Hello,
can you move the file
distance_regular.pyx
to the subdirectorygenerators/
. 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()
.