#21155 closed enhancement (fixed)
implement Muzychuk's "prolific" constructions of strongly regular graphs
Reported by:  dimpase  Owned by:  

Priority:  major  Milestone:  sage7.5 
Component:  graph theory  Keywords:  
Cc:  rschrecker, vdelecroix  Merged in:  
Authors:  Dima Pasechnik, Rowan Schrecker  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  4e4eba2 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  #19990  Stopgaps: 
Description (last modified by )
Currently one of few missing SRGs from A.E.Brouwer's database of SRGs is one with parameters (378,116,34,36), due to M.Muzychuk, construction S6 from "A generalization of WallisFonDerFlaass construction of strongly regular graphs." J. Algebr. Comb. 25(2), 169–187 (2007).
Most of the work is already done by Rowan Schrecker, and mostly just needed to be merged, see https://github.com/rschrecker/MuzychukProject (few easy bugs were fixed along the way, more examples/tests added, etc)
Change History (39)
comment:1 Changed 5 years ago by
 Milestone changed from sage7.3 to sage7.4
comment:2 Changed 5 years ago by
 Branch set to u/dimpase/muzS6
 Commit set to b27adcf9b7335eecfd95ce867aba3a70ea54264e
comment:3 Changed 5 years ago by
 Cc rschrecker added
I had to chase and fix a bug in MuzychukS6Graph
, which constructed wrong graph if the input, i.e. (n,d) were Python int
rather than Sage ZZ
type. (Division is differently behaving if you divide two ints in Python2...)
comment:4 Changed 5 years ago by
 Commit changed from b27adcf9b7335eecfd95ce867aba3a70ea54264e to f19c4363516ad1d06c89ff6757728bde0ae52385
Branch pushed to git repo; I updated commit sha1. New commits:
f19c436  more tests, examples, doctests pass now, made phi and sigma nonmodifiable

comment:5 Changed 5 years ago by
 Cc vdelecroix added
 Description modified (diff)
 Status changed from new to needs_review
comment:6 followup: ↓ 7 Changed 5 years ago by
Hello,
clearly I don't understand your code, but I have simple remarks.
for x in range(m): L_i[x] = [edge for edge in L.edges(labels=False) if x in edge]
should be
for x in range(m): L_i[x] = L.edges_incident(x, labels=False)
Then for this block
+ for C in ParClasses: + EC = matrix(QQ, v) + for i in range(v): + for j in range(v): + for line in C: + if i in line and j in line: + EC[i, j] = 1/k
Why not using this instead. I assume that line
is a pair.
+ for C in ParClasses: + EC = matrix(QQ, v) + for line in C: + EC[i, j] = E[j, i] = 1/k
[i, j] = line
>i,j = line
comment:7 in reply to: ↑ 6 ; followup: ↓ 8 Changed 5 years ago by
Replying to dcoudert:
Hello,
clearly I don't understand your code, but I have simple remarks.
for x in range(m): L_i[x] = [edge for edge in L.edges(labels=False) if x in edge]should be
for x in range(m): L_i[x] = L.edges_incident(x, labels=False)
right, thanks for pointing this out.
Then for this block
+ for C in ParClasses: + EC = matrix(QQ, v) + for i in range(v): + for j in range(v): + for line in C: + if i in line and j in line: + EC[i, j] = 1/kWhy not using this instead. I assume that
line
is a pair.
no, line
is a hyperplane in the (d1)dimensional affine space over GF(n), and C
is a class of
parallel hyperplanes.
+ for C in ParClasses: + EC = matrix(QQ, v) + for line in C: + EC[i, j] = E[j, i] = 1/k
[i, j] = line
>i,j = line
comment:8 in reply to: ↑ 7 Changed 5 years ago by
no,
line
is a hyperplane in the (d1)dimensional affine space over GF(n), andC
is a class of parallel hyperplanes.
OK, so you can at least do:
for C in ParClasses: EC = matrix(QQ, v) for i in range(v): for line in C: if not i in line: continue for j in range(i+1,v): if j in line: EC[i, j] = EC[j, i] = 1/k
comment:9 Changed 5 years ago by
 Commit changed from f19c4363516ad1d06c89ff6757728bde0ae52385 to db10d0113602c90907e40de8339cb8e4e7e0fb04
Branch pushed to git repo; I updated commit sha1. New commits:
db10d01  improving docs and speeding up code

comment:10 followup: ↓ 11 Changed 5 years ago by
test, pls ignore
comment:11 in reply to: ↑ 10 Changed 5 years ago by
comment:12 Changed 5 years ago by
 Commit changed from db10d0113602c90907e40de8339cb8e4e7e0fb04 to d1b6588289aa9de0d9cedc0f98e18dbad5f04fc3
comment:13 Changed 5 years ago by
 Milestone changed from sage7.4 to sage7.5
more doc cleanup, testing 'random' options properly (and fixing bugs on the way).
comment:14 Changed 5 years ago by
 Commit changed from d1b6588289aa9de0d9cedc0f98e18dbad5f04fc3 to f6d862f7d234cda471eb78473f9b0adac7dff776
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
f6d862f  removed broken usersupplied Sigma dict parameter;

comment:15 Changed 5 years ago by
 Commit changed from f6d862f7d234cda471eb78473f9b0adac7dff776 to b6a169fd814a717fa21419b7cf09d181d5bf87ba
comment:16 followup: ↓ 17 Changed 5 years ago by
+ from __builtin__ import range
I suggest to use instead
from six.moves import range
(as fast as xrange)
comment:17 in reply to: ↑ 16 Changed 5 years ago by
Replying to chapoton:
+ from __builtin__ import rangeI suggest to use instead
from six.moves import range(as fast as xrange)
this range
does not have .pop()
, while it is used in the code.
(and this is exactly why I added this import in the 1st place).
comment:18 Changed 5 years ago by
 Commit changed from b6a169fd814a717fa21419b7cf09d181d5bf87ba to 12ed3813cbb89d12b189ce3df855834ae7cd7ceb
Branch pushed to git repo; I updated commit sha1. New commits:
12ed381  added EPSRC ackn. for Rowan

comment:19 Changed 5 years ago by
 Commit changed from 12ed3813cbb89d12b189ce3df855834ae7cd7ceb to df0c845dfcb77d097bacbc592910851dc26b456c
Branch pushed to git repo; I updated commit sha1. New commits:
02e99ea  trac #19990: graphs.IoninKharaghani765Graph

e2d55ca  Merge branch 'hadaconst' into IK765

2d93ab3  more details on construction

d3162ed  Merge branch 'hadaconst' into IK765

3ee3a6d  added TODO for an update to [IK03]

1071e13  Merge branch 'u/dimpase/19990' of trac.sagemath.org:sage into iokar

116abf9  Merge branch 'develop' of trac.sagemath.org:sage into iokar

edfeed1  fixed typos and refs, updated for the current beta

df0c845  Merge branch 'u/dimpase/muzS6' of trac.sagemath.org:sage into iokar

comment:21 followup: ↓ 23 Changed 5 years ago by
.. [Mu07] M. Muzychuk.
should be
.. [Mu07] \M. Muzychuk.
for obscure sphinx reasons
comment:22 Changed 5 years ago by
 Commit changed from df0c845dfcb77d097bacbc592910851dc26b456c to 2c74c1ee7ef0502959ceac9a7a94aad0d02390ce
Branch pushed to git repo; I updated commit sha1. New commits:
2c74c1e  backslash!

comment:23 in reply to: ↑ 21 Changed 5 years ago by
Replying to chapoton:
.. [Mu07] M. Muzychuk.should be
.. [Mu07] \M. Muzychuk.for obscure sphinx reasons
fixed by the latest commit.
comment:25 Changed 5 years ago by
Some possible minor improvements:
1) test assert d > 1, 'd must be at least 2'
first.
2) replace
L_i = [0]*m for x in range(m): L_i[x] = L.edges_incident(x, labels=False)
with L_i = [L.edges_incident(x, labels=False) for x in range(m)]
3) precompute ones_v = ones/v
} and use EC = ones_v
to avoid computing ones/v
for each parallel class. It is also reused later in the code
4) use
for i,j in itertools.combinations(line, 2): EC[i,j] = EC[j,i] = 1/k
5) the block elif Phi == 'fixed':
could be
Phi = {(x,line):val for x in range(m) for val,line in enumerate(L_i[x])}
6) phi = {(x, line):ParClasses[Phi[(x, line)]] for x in range(m) for line in L_i[x]}
7) A_i = [((vk)/v)*ones  k*F_i[x] for x in range(m)]
or may be A_i = [(vk)*ones_v  k*F_i[x] for x in range(m)]
8) add seealso sections in methods MuzychukS6Graph
and is_muzychuk_S6
.
Also, you should add a space after each #
to ease the readability.
comment:26 Changed 5 years ago by
 Commit changed from 2c74c1ee7ef0502959ceac9a7a94aad0d02390ce to 25bef7735c83a97c5ac7033c4abcab85319e80fe
comment:27 Changed 5 years ago by
OK, implemented, I also added few more SEEALSO
for other strongly regular graphs, but I'd rather do this completely systematically on another ticket.
comment:28 followup: ↓ 29 Changed 5 years ago by
Method MuzychukS6Graph
is working correctly. You still have to improve its description. Something is missing with the last sentence Let L be the complete graph...
.
I don't understand the proposed behavior of method is_muzychuk_S6
.
sage: is_muzychuk_S6(378, 116, 34, 36) (<function MuzychukS6Graph at 0x19dce9cf8>, 3, 3) sage: is_muzychuk_S6(378, 116, 34, 37)
With such a name, the method should return True
or False
, but it returns either the generator + parameters or nothing.
This is apparently the standard in strongly_regular_db.pyx
but I don't understand this choice. Why not using an extra boolean parameter certificate
to return either a boolean or a boolean plus the generator+parameters.
comment:29 in reply to: ↑ 28 ; followup: ↓ 30 Changed 5 years ago by
Replying to dcoudert:
Method
MuzychukS6Graph
is working correctly. You still have to improve its description. Something is missing with the last sentenceLet L be the complete graph...
.
I'll have a look, sure.
I don't understand the proposed behavior of method
is_muzychuk_S6
.sage: is_muzychuk_S6(378, 116, 34, 36) (<function MuzychukS6Graph at 0x19dce9cf8>, 3, 3) sage: is_muzychuk_S6(378, 116, 34, 37)With such a name, the method should return
True
orFalse
, but it returns either the generator + parameters or nothing. This is apparently the standard instrongly_regular_db.pyx
but I don't understand this choice.
these is_...()
are internal functions, optimised for speed. If is_...()
returns nothing it indicates failure.
Why not using an extra boolean parameter
certificate
to return either a boolean or a boolean plus the generator+parameters.
They were not meant for outside use. Also note that returning a generator is almost as cheap as returning a boolean, so there is really little incentive in having an extra parameter.
comment:30 in reply to: ↑ 29 Changed 5 years ago by
these
is_...()
are internal functions, optimised for speed. Ifis_...()
returns nothing it indicates failure.
if it's for internal use only, then it's ok.
They were not meant for outside use. Also note that returning a generator is almost as cheap as returning a boolean, so there is really little incentive in having an extra parameter.
I agree. I didn't know that the methods are for internal use only. So no need for extra parameter.
comment:31 Changed 5 years ago by
 Commit changed from 25bef7735c83a97c5ac7033c4abcab85319e80fe to 3fdec90122f84ec148cc5e3d68befc8c886f6caa
Branch pushed to git repo; I updated commit sha1. New commits:
3fdec90  fixed the doc

comment:32 Changed 5 years ago by
Docs corrected. I meant to do this all along, but forgot, sorry about this.
comment:33 followup: ↓ 35 Changed 5 years ago by
 two of then > two of them
 Use 80 columns format for documentation
 Since #21454, references should be put in master biblio file
After that it should be ok.
comment:34 Changed 5 years ago by
 Commit changed from 3fdec90122f84ec148cc5e3d68befc8c886f6caa to 4e4eba21393932601b30563397161719de83cb02
Branch pushed to git repo; I updated commit sha1. New commits:
4e4eba2  reformatted to fit in 80 columns and fixed the typo

comment:35 in reply to: ↑ 33 Changed 5 years ago by
Replying to dcoudert:
 two of then > two of them
done
 Use 80 columns format for documentation
done
 Since #21454, references should be put in master biblio file
none of the files in src/sage/graphs/
is touched by #21454.
This is obviously a task for another ticket, to move these references into the master.
comment:36 Changed 5 years ago by
 Reviewers set to David Coudert
 Status changed from needs_review to positive_review
For me this patch is now good to go (compile, run, doctests, doc display nicely, etc.).
comment:37 Changed 5 years ago by
Thanks. The next in line is #21890, if you have time...
comment:38 Changed 5 years ago by
 Branch changed from u/dimpase/muzS6 to 4e4eba21393932601b30563397161719de83cb02
 Resolution set to fixed
 Status changed from positive_review to closed
comment:39 Changed 5 years ago by
 Commit 4e4eba21393932601b30563397161719de83cb02 deleted
still needs some minor cleanup and more tests  but works already
New commits:
implementation by Rowan Schrecker, with few fixes/improvements