Opened 5 years ago

Closed 5 years ago

# NO and NU graphs

Reported by: Owned by: dimpase major sage-6.9 graph theory ncohen Dima Pasechnik Nathann Cohen N/A dbc50b1 (Commits) #19098, #19180

### Description

add strongly regular graphs on non-isotropic points of various forms, orthogonal and Hermitean. see http://www.win.tue.nl/~aeb/graphs/srghub.html and p.145 of http://www.win.tue.nl/~aeb/2WF02/spectra.pdf

### comment:1 follow-up: ↓ 2 Changed 5 years ago by ncohen

You know how to build those ? COOL O_O

They are like the main race of the graphs that we still can't build.

Nathann

### comment:2 in reply to: ↑ 1 ; follow-up: ↓ 3 Changed 5 years ago by dimpase

You know how to build those ? COOL O_O

most of it should be trivial modifications of polar graph functions. I think I also should do refactoring of graphs/generators/families here...

They are like the main race of the graphs that we still can't build.

there still skewhad* and Pasechnik, which need some skew-Hadamard matrices... These still need few not too trivial constructions by Williams to be implemented.

### comment:3 in reply to: ↑ 2 Changed 5 years ago by ncohen

most of it should be trivial modifications of polar graph functions. I think I also should do refactoring of graphs/generators/families here...

Yepyep, create the new module and update the names.

there still skewhad* and Pasechnik, which need some skew-Hadamard matrices... These still need few not too trivial constructions by Williams to be implemented.

I'm eager to have a graphs.PasechnikGraph ;-)

Nathann

### comment:4 Changed 5 years ago by dimpase

• Branch set to u/dimpase/NONU

Last 10 new commits:

 ​9510c70 trac #19098: Speedup ​4fd56a1 use TaylorTwographSRG in taylor_twograph ​83f94e4 just add vertex v0 ​6c0c890 trac #19133: Merged with 6.9.beta5 ​3bc31a1 trac #19133: Broken doctests ​ffcf6ac Merge remote-tracking branch 'trac/public/19133' into tay2 ​2159763 fix a docstring typo in #19133 ​6253d7a added INPUT, removed unnecessary check ​ecd04ff Merge branch 'tay2' into NONU ​abf0a5e implemented NO^eps(m,2)

### comment:5 Changed 5 years ago by dimpase

does this function naming

def NonisotropicOrthogonalPolarGraphF2(m, sign="+"):
r"""
Returns the Graph of Nonisotropic Points of a quadric NO^{\epsilon}_{2m}(2).


### comment:6 Changed 5 years ago by dimpase

• Dependencies set to #19098

### comment:7 Changed 5 years ago by ncohen

Dima, your branch are next-to-impossible to review. Not only you always add 10 micro-commits [1], but in this case I can't even figure out which commits *move* code around, and which commits add/modify code.

And I can't review again code that has been checked in the past.

Nathann

[1] That's what "rewriting history" is for. So that the history of your branch is not the 'history of times where you saved your files' (which has no logic of its own) but an intelligent splitting of the work your ticket does.

### comment:8 Changed 5 years ago by ncohen

As you do not even include the number of the tickets in the commit, you can't even tell what belongs to this ticket and what belongs to another.

### comment:9 Changed 5 years ago by dimpase

Dude, this ticket is not ready for review by far! the branch is just a backup of work in progress...

### comment:10 Changed 5 years ago by ncohen

Oh. My mistake. Sorry.

### comment:11 Changed 5 years ago by git

• Commit changed from abf0a5e6f9a2aa52550555d77e9bfc654ad59399 to a0b63490e1d2cf13ba6fc048213650dbd7aa9e16

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

 ​a0b6349 implemented NO(m,[2,3]) and NO(m,5,perp)

### comment:12 Changed 5 years ago by git

• Commit changed from a0b63490e1d2cf13ba6fc048213650dbd7aa9e16 to 826e475f6c553b042100f98fa99fb32479bb402f

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

 ​826e475 NU(m,q), and few minor touches in doctests around

### comment:13 Changed 5 years ago by git

• Commit changed from 826e475f6c553b042100f98fa99fb32479bb402f to 1bb2572b3d59d2be738aff37d1b06fb562f1582c

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

 ​50c5c92 a largely failed attempt to do NO^e(2m-1,q) ​1bb2572 done with NO^e(2n+1,q), and its recognition for DB

### comment:14 Changed 5 years ago by git

• Commit changed from 1bb2572b3d59d2be738aff37d1b06fb562f1582c to 7caba1a7941fcc2e442ef7877e71c47e84cf4e6d

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

 ​7caba1a done with NO^e(2n+1,q, (perp)), and its recognition for DB

### comment:15 Changed 5 years ago by git

• Commit changed from 7caba1a7941fcc2e442ef7877e71c47e84cf4e6d to ee2d06d0ce47c79a35828af99dd506b6c698c4e0

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

 ​d28689e done with NO^e(m,q, (perp)), and its recognition for DB ​7cbfa8b trac #19180: A (220,84,38,28)-strongly regular graph ​6ce1899 trac #19180: Speedup ​ee2d06d Merge branch 'public/19180' of git://trac.sagemath.org/sage into NONU

### comment:16 Changed 5 years ago by dimpase

• Dependencies changed from #19098 to #19098, #19180

with the latest commit, we only miss 152 graphs...

For this ticket to be done, we need parameters of NU(n,q)-srg's.

### comment:17 Changed 5 years ago by git

• Commit changed from ee2d06d0ce47c79a35828af99dd506b6c698c4e0 to d70bf502f85697af3e6e57ad3a1af332f1bf0b7f

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

 ​26db5ec Merge branch 'develop' of git://trac.sagemath.org/sage into NONU ​d70bf50 implemented recognition of NU; a bug in recongition of NO^+(2n+1,3) to fix...

### comment:18 Changed 5 years ago by git

• Commit changed from d70bf502f85697af3e6e57ad3a1af332f1bf0b7f to 2bd5f54053f39da78f3c610ee009f6f8bf89a440

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

 ​2bd5f54 fix for a silly bug in is_NOodd, moar doctests

### comment:19 Changed 5 years ago by dimpase

• Status changed from new to needs_review

### comment:20 follow-up: ↓ 21 Changed 5 years ago by ncohen

Could you make it easier to review, by having a commit that only *moves* the code from the old file to the new one? Otherwise it is very difficult to figure out what was just moved and what has to be reviewed again.

Nathann

### comment:21 in reply to: ↑ 20 ; follow-up: ↓ 22 Changed 5 years ago by dimpase

Could you make it easier to review, by having a commit that only *moves* the code from the old file to the new one? Otherwise it is very difficult to figure out what was just moved and what has to be reviewed again.

The closest approximation of this is the 1st commit on the ticket, 22114b7a6ada54c4c66a9b5705a2c2233046a61f

The bottom part of graphs/generators/families.py was chopped off and saved into the initial graphs/generators/classical_geometries.py And stuff happened to SymplecticGraph (it got renamed and deprecated).

Unfortunately I did not record this as two separate commits, and I don't see how I could change this now without much effort...

### comment:22 in reply to: ↑ 21 ; follow-up: ↓ 24 Changed 5 years ago by ncohen

Unfortunately I did not record this as two separate commits, and I don't see how I could change this now without much effort...

How do you think I should review this ticket, then? Re-review everything?

### comment:23 follow-up: ↓ 28 Changed 5 years ago by ncohen

• Reviewers set to Nathann Cohen
• Status changed from needs_review to needs_work

Hello Dima,

Here is a first-pass review.

• graphs.SymplecticGraph does not exist. It is not enough to create a deprecation alias, it must also be available in graphs.<tab>.
• In NonisotropicOrthogonalPolarGraph. Replace
else:
if not perp is None:
<code>
else:

with
elif not perp is None:
<code>
else:

No need to indent everything twice.
• same function: q does not appear in the INPUT block
• same function: move the checks on q (prime power) and sign (+-) to the beginning of the function (not in a 'if' block). This function builds a (dense) graph, we are not at a level where we try to minimize the amount of unnecessary 'if'.
• REFERENCE block happens at the end of the docstring
• Remove the commented code that your functions contain
• Why 5 is_NO* functions instead of one is_NO ? I remember a comment of yours about copy/paste...
• If your function is slow it is because of that line
G = Graph([V,lambda x,y:P(vector(x),vector(y))==0],loops=False)

When you do this, 'vector' is called 'binomial(n,2)' times, and vector is *SLOW*. In a previous branch of yours, I added a commit to remove this in order to gain a large speedup (do you remember)? Try to find a way to avoid vectors. If you cannot, then instead of building n^2 vectors you should turn everything into a vector *once*, and work on vectors instead. Observe that vectors have a .set_immutable method.

Then, perhaps we will be able to remove those # long time everywhere in _orthogonal_polar_graph (and elsewhere).

• Same in UnitaryPolarGraph.

Next time, please think of the reviewer when you built your commits. When you save minutes by not doing it, the reviewer loses hours trying to figure out what exactly you did.

Thanks for the addition, however. I couldn't have done that.

Nathann

P.S.: Fill the 'authors' field. Think of doing it when you set your tickets to needs_review.

### comment:24 in reply to: ↑ 22 ; follow-up: ↓ 25 Changed 5 years ago by dimpase

• Reviewers Nathann Cohen deleted

Unfortunately I did not record this as two separate commits, and I don't see how I could change this now without much effort...

How do you think I should review this ticket, then? Re-review everything?

Splitting a file into two isn't really specially supported by git, no? That is, in the new file one can potentially put anything..

%%% while I was writing this I saw your review, thanks! anyhow I'll leave it here just in case.

You can do the following: check out 22114b7a6ada54c4c66a9b5705a2c2233046a61f, take graphs/generators/classical_geometries.py and remove the top part before the first def. Now join the result to the bottom of graphs/generators/families.py

Now you can look at the diff of the resulting graphs/generators/families.py and graphs/generators/families.py from the appropriate beta. You will see all what happened at 22114b7a6ada54c4c66a9b5705a2c2233046a61f this way.

After that you can review the diff of the ticket branch against 22114b7a6ada54c4c66a9b5705a2c2233046a61f.

### comment:25 in reply to: ↑ 24 Changed 5 years ago by ncohen

Splitting a file into two isn't really specially supported by git, no?

No indeed, but you can make it easier for the reviewer this way:

1) Make a first commit that just *moves* code from one file to another. It is very easy to check something like that: I only have to make the same move in the other direction, and check that the two commits add up to no modification at all.

2) After this first commit the code may not compile (because of broken import and stuff). You can then change code wherever you like to adapt to it.

3) Do whatever else you need to do in this branch.

This way, after checking the first commit, I can review the diff of all commits except the first.

You can do the following:

Thanks. I'll try it.

Nathann

### comment:26 Changed 5 years ago by dimpase

• Authors set to Dima Pasechnik
• Reviewers set to Nathann Cohen

### comment:27 Changed 5 years ago by git

• Commit changed from 2bd5f54053f39da78f3c610ee009f6f8bf89a440 to 79ce567d62ac693b0abe28b659cde2e16abdeb09

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

 ​a0a3320 added SymplecticGraph to graphs.* and fixed a typo there, and a doctest ​3bd8437 else if -> elif, other things in NonisotropicOrthogonalPolarGraph ​79ce567 speedups by calling vector() once

### comment:28 in reply to: ↑ 23 ; follow-up: ↓ 30 Changed 5 years ago by dimpase

• graphs.SymplecticGraph does not exist. It is not enough to create a deprecation alias, it must also be available in graphs.<tab>.

done

• In NonisotropicOrthogonalPolarGraph. Replace
else:
if not perp is None:
<code>
else:

with
elif not perp is None:
<code>
else:

No need to indent everything twice.

done

• same function: q does not appear in the INPUT block

done

• same function: move the checks on q (prime power) and sign (+-) to the beginning of the function (not in a 'if' block). This function builds a (dense) graph, we are not at a level where we try to minimize the amount of unnecessary 'if'.

done

• REFERENCE block happens at the end of the docstring

done (moved REFERENCE twice)

• Remove the commented code that your functions contain

hmm, where? I've better worded a comment that looked as code, but otherwise...

• Why 5 is_NO* functions instead of one is_NO ? I remember a comment of yours about copy/paste...

it's because the arithmetic properties of parameters are quite different in each of these cases. Each has a different algorithm coded.

• If your function is slow it is because of that line
G = Graph([V,lambda x,y:P(vector(x),vector(y))==0],loops=False)

When you do this, 'vector' is called 'binomial(n,2)' times, and vector is *SLOW*. In a previous branch of yours, I added a commit to remove this in order to gain a large speedup (do you remember)? Try to find a way to avoid vectors. If you cannot, then instead of building n^2 vectors you should turn everything into a vector *once*, and work on vectors instead. Observe that vectors have a .set_immutable method.

OK, I did the latter. Totally getting rid of vector() in these cases seems tricky. Anyhow, it was quite an improvement.

Then, perhaps we will be able to remove those # long time everywhere in _orthogonal_polar_graph (and elsewhere).

done

• Same in UnitaryPolarGraph.

done (as above)

Next time, please think of the reviewer when you built your commits. When you save minutes by not doing it, the reviewer loses hours trying to figure out what exactly you did.

sorry for the mess...

### comment:29 Changed 5 years ago by dimpase

• Status changed from needs_work to needs_review

### comment:30 in reply to: ↑ 28 ; follow-up: ↓ 32 Changed 5 years ago by ncohen

Hellooooooo,

• Remove the commented code that your functions contain

hmm, where? I've better worded a comment that looked as code, but otherwise...

(tmp|✔)~/sage/graphs$grep "^# " strongly_regular_db.pyx # -*- coding: utf-8 -*- # print "ev: ", r, " ", s, "\n" # print "p=", p, " t=", t, " r=", r, " s=", s,"\n" # print "2nd try: p=", p, " t=", t, " r=", r, " s=", s,"\n" # print "q=", q, "e=", e, "\n" # n = t/kk + 2 # print q**(n-1)*(q**n - e)/(q + 1), " ",\ # (q**(n-1) + e)*(q**(n-2) - e), " ",\ # q**(2*n-5)*(q+1) - e*q**(n-2)*(q-1) - 2, " ",\ # q**(n-3)*(q + 1)*(q**(n-2) - e),"\n"  • Why 5 is_NO* functions instead of one is_NO ? I remember a comment of yours about copy/paste... it's because the arithmetic properties of parameters are quite different in each of these cases. Each has a different algorithm coded. So the test is different in each case, but the tests for prime powers, the ordering or s,r, the eigenvalues.. All this is common (not to mention a big part of the doc). Why not one function, with several 'if' for each case? Nathann ### comment:31 Changed 5 years ago by git • Commit changed from 79ce567d62ac693b0abe28b659cde2e16abdeb09 to dbc50b1b074afe22f4fb32542e8b1ca76c41525e Branch pushed to git repo; I updated commit sha1. New commits:  ​dbc50b1 remove forgotten prints ### comment:32 in reply to: ↑ 30 ; follow-up: ↓ 33 Changed 5 years ago by dimpase Replying to ncohen: (tmp|✔)~/sage/graphs$ grep "^# " strongly_regular_db.pyx
# -*- coding: utf-8 -*-
#    print "ev: ", r, " ", s, "\n"
#    print "p=", p, " t=", t, " r=", r, " s=", s,"\n"
#            print "2nd try: p=", p, " t=", t, " r=", r, " s=", s,"\n"
#    print "q=", q, "e=", e, "\n"
#    n  = t/kk + 2
#    print q**(n-1)*(q**n - e)/(q + 1), " ",\
#          (q**(n-1) + e)*(q**(n-2) - e), " ",\
#          q**(2*n-5)*(q+1) - e*q**(n-2)*(q-1) - 2, " ",\
#          q**(n-3)*(q + 1)*(q**(n-2) - e),"\n"


OK, removed, sorry.

• Why 5 is_NO* functions instead of one is_NO ? I remember a comment of yours about copy/paste...

it's because the arithmetic properties of parameters are quite different in each of these cases. Each has a different algorithm coded.

So the test is different in each case, but the tests for prime powers, the ordering or s,r, the eigenvalues..

no, read the code: in some cases eigenvalues aren't even computed; if they are used then they are used differently in different functions, etc. Also note that there is a lot in common between all of the following:

is_affine_polar,is_orthogonal_polar,is_NOodd, is_NOperp_F5,
is_NO_F2, is_NO_F3, is_NU,
is_unitary_polar,is_unitary_dual_polar


And most of these test for more than one series of graphs, if you count all these '+', '-', etc.

All this is common (not to mention a big part of the doc). Why not one function, with several 'if' for each case?

because several ifs suck and make code unreadable and harder to debug, and hard to document and test. Imagine e.g. how hard it would be to figure out what doctest tests what.

### comment:33 in reply to: ↑ 32 Changed 5 years ago by ncohen

Yo,

no, read the code: in some cases eigenvalues aren't even computed;

Depends how you see it. If you compute eigenvalues in several functions that could be merged, that you compute them too many times. If it were only one function, it wouldn't be the case.

because several ifs suck and make code unreadable and harder to debug, and hard to document and test. Imagine e.g. how hard it would be to figure out what doctest tests what.

While you were developing it perhaps, but there is nothing to debug now, right?

### comment:34 follow-up: ↓ 35 Changed 5 years ago by ncohen

• Status changed from needs_review to positive_review

Okay, let's get this merged. You and I seldom agree on anything when it comes to design, and the code works well anyway. I have been building all graphs for which we detect a constructions up to 1000+, and there is no problem there: we get the SRG we ask for, each time. And there is no N<whatever> in the list of graphs we miss.

Thanks,

Nathann

### comment:35 in reply to: ↑ 34 ; follow-up: ↓ 37 Changed 5 years ago by dimpase

Okay, let's get this merged. You and I seldom agree on anything when it comes to design, and the code works well anyway. I have been building all graphs for which we detect a constructions up to 1000+, and there is no problem there: we get the SRG we ask for, each time. And there is no N<whatever> in the list of graphs we miss.

we can refactor the code so that eigenvalues are computed very early and get passed around as parameters to the is_BLAH() functions that use them. Perhaps I'll do this some time later, if you don't mind.

OK, so we still have big classes to cover:

• GQs (of order (q-1,q+1) and (q+1,q-1), the others are there already).
• Goethals-Seidel (8.C in [BvL84]; seems to be easy to do)
• Mathon: symmetric conference matrices (8.B in [BvL84])

I easily can do GQs, too, unless you already are on them...

### comment:36 Changed 5 years ago by vbraun

• Branch changed from u/dimpase/NONU to dbc50b1b074afe22f4fb32542e8b1ca76c41525e
• Resolution set to fixed
• Status changed from positive_review to closed

### comment:37 in reply to: ↑ 35 Changed 5 years ago by ncohen

• Commit dbc50b1b074afe22f4fb32542e8b1ca76c41525e deleted

we can refactor the code so that eigenvalues are computed very early and get passed around as parameters to the is_BLAH() functions that use them. Perhaps I'll do this some time later, if you don't mind.

Indeed. No need to think of that before computing the eigenvalues becomes a critical cost.

OK, so we still have big classes to cover:

• GQs (of order (q-1,q+1) and (q+1,q-1), the others are there already).