Opened 6 months ago
Closed 5 months ago
#30240 closed enhancement (fixed)
Graphs: a few distance-regular graphs
Reported by: | gh-Ivo-Maffei | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.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) | Commit: | 574960d6141180687fcc749b9b2cef5554ffa59f |
Dependencies: | #30277 | Stopgaps: |
Description
Implemented a few distance-regular graphs for a database of such graphs.
Change History (47)
comment:1 Changed 6 months ago by
- Cc dimpase added
- Status changed from new to needs_review
comment:2 follow-up: ↓ 4 Changed 6 months ago by
comment:3 Changed 6 months ago by
- Commit changed from cd1be589d7735b2ce6dbc6c81ff3a7d2df875042 to da2c8f7392b276acd7e275f6c03e5172e555516b
comment:4 in reply to: ↑ 2 Changed 6 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 follow-up: ↓ 7 Changed 6 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 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 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 6 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 6 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 6 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 6 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 6 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 6 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 6 months ago by
- Status changed from needs_work to needs_review
comment:13 follow-up: ↓ 15 Changed 6 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/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.
comment:14 Changed 6 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 ; follow-up: ↓ 17 Changed 6 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 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.
comment:16 Changed 6 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 6 months ago by
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 ?
comment:18 Changed 6 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 6 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 6 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 6 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 6 months ago by
- Status changed from needs_work to positive_review
comment:23 Changed 6 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 6 months ago by
Oh, right, this ticket should be based on #30277, indeed. Sorry for missing this.
comment:25 Changed 6 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 6 months ago by
- Dependencies set to #30277
comment:27 Changed 6 months ago by
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
comment:28 Changed 6 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 6 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 6 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 6 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 follow-up: ↓ 36 Changed 6 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 6 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 follow-up: ↓ 37 Changed 6 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 6 months ago by
It seems that AtlasGroup
only knows 3.O7(3)
as a 27-dimensional matrix group over GF(4).
comment:36 in reply to: ↑ 32 Changed 6 months ago by
comment:37 in reply to: ↑ 34 ; follow-up: ↓ 39 Changed 6 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 19-Jun-2019 │ GAP │ https://www.gap-system.org └───────┘ Architecture: x86_64-apple-darwin19.4.0-default64-kv3 Configuration: gmp 6.0.0, readline
comment:38 Changed 6 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 ; follow-up: ↓ 41 Changed 6 months ago by
Replying to gh-Ivo-Maffei:
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 6 months ago by
test, please ignore.
comment:41 in reply to: ↑ 39 Changed 6 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 6 months ago by
make gap_packages-clean
should uninstall this one. Iirc, only that one graph needed
gap_packages installed, not sure, away from kbd now.
comment:43 Changed 6 months ago by
Just tag all the tests using AtlasGroup with gap_packages
, in addtion to internet
.
comment:44 Changed 6 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 6 months ago by
- Status changed from needs_work to needs_review
comment:47 Changed 5 months ago by
- Branch changed from u/gh-Ivo-Maffei/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()
.