#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, GitHub, GitLab) Commit: 574960d6141180687fcc749b9b2cef5554ffa59f
Dependencies: #30277 Stopgaps:

Status badges

Description

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

Change History (47)

comment:1 Changed 15 months ago by gh-Ivo-Maffei

  • Cc dimpase added
  • Status changed from new to needs_review

comment:2 follow-up: Changed 15 months ago by 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().

comment:3 Changed 15 months ago by git

  • Commit changed from cd1be589d7735b2ce6dbc6c81ff3a7d2df875042 to da2c8f7392b276acd7e275f6c03e5172e555516b

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

a5ad68cadded a few sporadic distance regular graphs
da2c8f7moved file to generators; fixed tests

comment:4 in reply to: ↑ 2 Changed 15 months ago by 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)

comment:5 follow-up: Changed 15 months ago by dcoudert

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

comment:6 Changed 15 months ago by git

  • Commit changed from da2c8f7392b276acd7e275f6c03e5172e555516b to 27c2868bc0b71e8ee4648de6cef2fb34cf42937a

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

27c2868fixed typos and formatting

comment:7 in reply to: ↑ 5 Changed 15 months ago by gh-Ivo-Maffei

  • 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 15 months ago by 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.

comment:9 Changed 15 months ago by git

  • Commit changed from 27c2868bc0b71e8ee4648de6cef2fb34cf42937a to faf04e91399df2cd384544315ab47dcad4bc379f

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

faf04e9itertools to simplify code

comment:10 Changed 15 months ago by dimpase

  • 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 15 months ago by git

  • Commit changed from faf04e91399df2cd384544315ab47dcad4bc379f to bc196736037f659ce6e9bb2b095e806c3e96e9a0

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

bc19673change optional flag for atlasrep

comment:12 Changed 15 months ago by gh-Ivo-Maffei

  • Status changed from needs_work to needs_review

comment:13 follow-up: Changed 15 months ago by 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.

Last edited 15 months ago by dimpase (previous) (diff)

comment:14 Changed 15 months ago by git

  • Commit changed from bc196736037f659ce6e9bb2b095e806c3e96e9a0 to 12d3e1e898e86adbfb16f3c5e8e9922190fb5d85

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

12d3e1erenamed locally GQ function and added references

comment:15 in reply to: ↑ 13 ; follow-up: Changed 15 months ago by 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.

comment:16 Changed 15 months ago by git

  • Commit changed from 12d3e1e898e86adbfb16f3c5e8e9922190fb5d85 to e91e0585312c21f62324fc1d535cb7f6f9fc9ba0

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

e91e058forgot to rename graph

comment:17 in reply to: ↑ 15 Changed 15 months ago by 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 ?

comment:18 Changed 15 months ago by 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.

comment:19 Changed 15 months ago by dimpase

  • Reviewers changed from David Coudert to David Coudert, Dima Pasechnik
  • Status changed from needs_review to positive_review

OK, fine.

comment:20 Changed 15 months ago by dcoudert

  • 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 15 months ago by git

  • Commit changed from e91e0585312c21f62324fc1d535cb7f6f9fc9ba0 to 63177084eb5cc97fb68c3a0b728aa2385eab657e

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

6317708fixed indentation issue

comment:22 Changed 15 months ago by gh-Ivo-Maffei

  • Status changed from needs_work to positive_review

comment:23 Changed 15 months ago by dcoudert

  • 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 15 months ago by dimpase

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

comment:25 Changed 15 months ago by dimpase

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

comment:26 Changed 15 months ago by dimpase

  • Dependencies set to #30277

comment:27 Changed 15 months ago by 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

comment:28 Changed 15 months ago by 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...).

comment:29 Changed 15 months ago by gh-Ivo-Maffei

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

comment:30 Changed 15 months ago by git

  • Commit changed from 63177084eb5cc97fb68c3a0b728aa2385eab657e to 7754591fe4e8b4f56db6857c3598f2863e76d822

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

01b96b0Merge branch 't/29701/replace_use_of_module_list_optionalextension' into t/29950/build_sagelib_using_installed_sage_setup
2818739Merge branch 't/29950/build_sagelib_using_installed_sage_setup' into t/30277/remove_src_module_list_py
89aaa5badded a few sporadic distance regular graphs
2f8ca0fmoved file to generators; fixed tests
7a906b1fixed typos and formatting
8164445itertools to simplify code
6a15420change optional flag for atlasrep
92537c0renamed locally GQ function and added references
6f3754bforgot to rename graph
7754591fixed indentation issue

comment:31 Changed 15 months ago by dimpase

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

comment:32 follow-up: Changed 15 months ago by git

  • Commit changed from 7754591fe4e8b4f56db6857c3598f2863e76d822 to 4e17fd7fd738e0d1a376a8212fbbf44ea9262646

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

4e17fd7fixed bug introduced by removing module_list

comment:33 Changed 15 months ago by 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?

comment:34 follow-up: Changed 15 months ago by dimpase

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 15 months ago by dimpase

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 15 months ago by dimpase

Replying to git:

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

4e17fd7fixed bug introduced by removing module_list

it is less clutter to write there simply

from .generators import smallgraphs, distance_regular

comment:37 in reply to: ↑ 34 ; follow-up: Changed 15 months ago by 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

comment:38 Changed 15 months ago by git

  • Commit changed from 4e17fd7fd738e0d1a376a8212fbbf44ea9262646 to e063b5e46a9076c0a5cea1046f22121bb14f7642

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

e063b5esimplified import

comment:39 in reply to: ↑ 37 ; follow-up: Changed 15 months ago by 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.

comment:40 Changed 15 months ago by dimpase

test, please ignore.

comment:41 in reply to: ↑ 39 Changed 15 months ago by 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?

comment:42 Changed 15 months ago by dimpase

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 15 months ago by dimpase

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

Last edited 15 months ago by dimpase (previous) (diff)

comment:44 Changed 15 months ago by git

  • Commit changed from e063b5e46a9076c0a5cea1046f22121bb14f7642 to 574960d6141180687fcc749b9b2cef5554ffa59f

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

574960dadded gap_packages flag to atlasrep

comment:45 Changed 15 months ago by gh-Ivo-Maffei

  • Status changed from needs_work to needs_review

comment:46 Changed 14 months ago by dimpase

  • Status changed from needs_review to positive_review

LGTM

comment:47 Changed 14 months ago by vbraun

  • Branch changed from u/gh-Ivo-Maffei/drg_sporadic1 to 574960d6141180687fcc749b9b2cef5554ffa59f
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.