Opened 5 years ago

Closed 5 years ago

Last modified 5 years ago

#21155 closed enhancement (fixed)

implement Muzychuk's "prolific" constructions of strongly regular graphs

Reported by: dimpase Owned by:
Priority: major Milestone: sage-7.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:

Status badges

Description (last modified by dimpase)

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 Wallis-Fon-Der-Flaass 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 dimpase

  • Milestone changed from sage-7.3 to sage-7.4

comment:2 Changed 5 years ago by dimpase

  • Branch set to u/dimpase/muzS6
  • Commit set to b27adcf9b7335eecfd95ce867aba3a70ea54264e

still needs some minor cleanup and more tests --- but works already


New commits:

b27adcfimplementation by Rowan Schrecker, with few fixes/improvements

comment:3 Changed 5 years ago by dimpase

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

  • Commit changed from b27adcf9b7335eecfd95ce867aba3a70ea54264e to f19c4363516ad1d06c89ff6757728bde0ae52385

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

f19c436more tests, examples, doctests pass now, made phi and sigma non-modifiable

comment:5 Changed 5 years ago by dimpase

  • Cc vdelecroix added
  • Description modified (diff)
  • Status changed from new to needs_review

comment:6 follow-up: Changed 5 years ago by 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)

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 ; follow-up: Changed 5 years ago by dimpase

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/k

Why not using this instead. I assume that line is a pair.

no, line is a hyperplane in the (d-1)-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 dcoudert

no, line is a hyperplane in the (d-1)-dimensional affine space over GF(n), and C 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 git

  • Commit changed from f19c4363516ad1d06c89ff6757728bde0ae52385 to db10d0113602c90907e40de8339cb8e4e7e0fb04

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

db10d01improving docs and speeding up code

comment:10 follow-up: Changed 5 years ago by dimpase

test, pls ignore

comment:11 in reply to: ↑ 10 Changed 5 years ago by dimpase

Replying to dimpase:

test, pls ignore

test2

comment:12 Changed 5 years ago by git

  • Commit changed from db10d0113602c90907e40de8339cb8e4e7e0fb04 to d1b6588289aa9de0d9cedc0f98e18dbad5f04fc3

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

e751532Merge branch 'u/dimpase/muzS6' of trac.sagemath.org:sage into muz61
d1b6588removed broken user-supplied Sigma dict parameter,

comment:13 Changed 5 years ago by dimpase

  • Milestone changed from sage-7.4 to sage-7.5

more doc cleanup, testing 'random' options properly (and fixing bugs on the way).

comment:14 Changed 5 years ago by git

  • Commit changed from d1b6588289aa9de0d9cedc0f98e18dbad5f04fc3 to f6d862f7d234cda471eb78473f9b0adac7dff776

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

f6d862fremoved broken user-supplied Sigma dict parameter;

comment:15 Changed 5 years ago by git

  • Commit changed from f6d862f7d234cda471eb78473f9b0adac7dff776 to b6a169fd814a717fa21419b7cf09d181d5bf87ba

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

814c3afMerge branch 'muzS6' into muzS6bis
66b5648Merge branch 'muz61' into muzS6bis
b6a169ffix a typo mentioned on #21061

comment:16 follow-up: Changed 5 years ago by chapoton

+    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 dimpase

Replying to chapoton:

+    from __builtin__ import range

I 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 git

  • Commit changed from b6a169fd814a717fa21419b7cf09d181d5bf87ba to 12ed3813cbb89d12b189ce3df855834ae7cd7ceb

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

12ed381added EPSRC ackn. for Rowan

comment:19 Changed 5 years ago by git

  • Commit changed from 12ed3813cbb89d12b189ce3df855834ae7cd7ceb to df0c845dfcb77d097bacbc592910851dc26b456c

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

02e99eatrac #19990: graphs.IoninKharaghani765Graph
e2d55caMerge branch 'hadaconst' into IK765
2d93ab3more details on construction
d3162edMerge branch 'hadaconst' into IK765
3ee3a6dadded TODO for an update to [IK03]
1071e13Merge branch 'u/dimpase/19990' of trac.sagemath.org:sage into iokar
116abf9Merge branch 'develop' of trac.sagemath.org:sage into iokar
edfeed1fixed typos and refs, updated for the current beta
df0c845Merge branch 'u/dimpase/muzS6' of trac.sagemath.org:sage into iokar

comment:20 Changed 5 years ago by dimpase

  • Dependencies set to #19990

this one is ready for review too...

comment:21 follow-up: Changed 5 years ago by chapoton

.. [Mu07] M. Muzychuk.

should be

.. [Mu07] \M. Muzychuk.

for obscure sphinx reasons

comment:22 Changed 5 years ago by git

  • Commit changed from df0c845dfcb77d097bacbc592910851dc26b456c to 2c74c1ee7ef0502959ceac9a7a94aad0d02390ce

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

2c74c1ebackslash!

comment:23 in reply to: ↑ 21 Changed 5 years ago by dimpase

Replying to chapoton:

.. [Mu07] M. Muzychuk.

should be

.. [Mu07] \M. Muzychuk.

for obscure sphinx reasons

fixed by the latest commit.

comment:24 Changed 5 years ago by dimpase

  • Authors set to Dima Pasechnik

this should tell bots to run tests

comment:25 Changed 5 years ago by dcoudert

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 = [((v-k)/v)*ones - k*F_i[x] for x in range(m)] or may be A_i = [(v-k)*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 git

  • Commit changed from 2c74c1ee7ef0502959ceac9a7a94aad0d02390ce to 25bef7735c83a97c5ac7033c4abcab85319e80fe

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

b9a96c0Merge branch 'develop' into muz
25bef77implemented reviewer's suggestions

comment:27 Changed 5 years ago by dimpase

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 follow-up: Changed 5 years ago by dcoudert

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 ; follow-up: Changed 5 years ago by dimpase

Replying to dcoudert:

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

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 dcoudert

these is_...() are internal functions, optimised for speed. If is_...() 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 git

  • Commit changed from 25bef7735c83a97c5ac7033c4abcab85319e80fe to 3fdec90122f84ec148cc5e3d68befc8c886f6caa

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

3fdec90fixed the doc

comment:32 Changed 5 years ago by dimpase

Docs corrected. I meant to do this all along, but forgot, sorry about this.

comment:33 follow-up: Changed 5 years ago by dcoudert

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

  • Commit changed from 3fdec90122f84ec148cc5e3d68befc8c886f6caa to 4e4eba21393932601b30563397161719de83cb02

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

4e4eba2reformatted to fit in 80 columns and fixed the typo

comment:35 in reply to: ↑ 33 Changed 5 years ago by dimpase

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 dcoudert

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

Thanks. The next in line is #21890, if you have time...

Last edited 5 years ago by dimpase (previous) (diff)

comment:38 Changed 5 years ago by vbraun

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

  • Authors changed from Dima Pasechnik to Dima Pasechnik, Rowan Schrecker
  • Commit 4e4eba21393932601b30563397161719de83cb02 deleted
Note: See TracTickets for help on using tickets.