#19136 closed enhancement (fixed)
NO and NU graphs
Reported by:  dimpase  Owned by:  

Priority:  major  Milestone:  sage6.9 
Component:  graph theory  Keywords:  
Cc:  ncohen  Merged in:  
Authors:  Dima Pasechnik  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  dbc50b1 (Commits)  Commit:  
Dependencies:  #19098, #19180  Stopgaps: 
Description
add strongly regular graphs on nonisotropic 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
Change History (37)
comment:1 followup: ↓ 2 Changed 5 years ago by
comment:2 in reply to: ↑ 1 ; followup: ↓ 3 Changed 5 years ago by
Replying to ncohen:
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 skewHadamard 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
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*
andPasechnik
, which need some skewHadamard 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
 Branch set to u/dimpase/NONU
 Commit set to abf0a5e6f9a2aa52550555d77e9bfc654ad59399
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 remotetracking 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
does this function naming
def NonisotropicOrthogonalPolarGraphF2(m, sign="+"): r""" Returns the Graph of Nonisotropic Points of a quadric `NO^{\epsilon}_{2m}(2)`.
sound about right?
comment:6 Changed 5 years ago by
 Dependencies set to #19098
comment:7 Changed 5 years ago by
Dima, your branch are nexttoimpossible to review. Not only you always add 10 microcommits [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
Really, look at that: http://git.sagemath.org/sage.git/log/?q=70f7b1c5d206e8627f3d124a28b7083e3a82313a..abf0a5e6f9a2aa52550555d77e9bfc654ad59399&h=abf0a5e6f9a2aa52550555d77e9bfc654ad59399&qt=range
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
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
Oh. My mistake. Sorry.
comment:11 Changed 5 years ago by
 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
 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
 Commit changed from 826e475f6c553b042100f98fa99fb32479bb402f to 1bb2572b3d59d2be738aff37d1b06fb562f1582c
comment:14 Changed 5 years ago by
 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
 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
 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
 Commit changed from ee2d06d0ce47c79a35828af99dd506b6c698c4e0 to d70bf502f85697af3e6e57ad3a1af332f1bf0b7f
comment:18 Changed 5 years ago by
 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:20 followup: ↓ 21 Changed 5 years ago by
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 ; followup: ↓ 22 Changed 5 years ago by
Replying to 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.
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 ; followup: ↓ 24 Changed 5 years ago by
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? Rereview everything?
comment:23 followup: ↓ 28 Changed 5 years ago by
 Reviewers set to Nathann Cohen
 Status changed from needs_review to needs_work
Hello Dima,
Here is a firstpass review.
graphs.SymplecticGraph
does not exist. It is not enough to create a deprecation alias, it must also be available ingraphs.<tab>
.
 In
NonisotropicOrthogonalPolarGraph
. Replaceelse: if not perp is None: <code> else:
withelif 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 oneis_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, andvector
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 buildingn^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 ; followup: ↓ 25 Changed 5 years ago by
 Reviewers Nathann Cohen deleted
Replying to 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? Rereview 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
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
 Reviewers set to Nathann Cohen
comment:27 Changed 5 years ago by
 Commit changed from 2bd5f54053f39da78f3c610ee009f6f8bf89a440 to 79ce567d62ac693b0abe28b659cde2e16abdeb09
comment:28 in reply to: ↑ 23 ; followup: ↓ 30 Changed 5 years ago by
Replying to ncohen:
graphs.SymplecticGraph
does not exist. It is not enough to create a deprecation alias, it must also be available ingraphs.<tab>
.
done
 In
NonisotropicOrthogonalPolarGraph
. Replaceelse: if not perp is None: <code> else:withelif 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 oneis_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, andvector
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 buildingn^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
 Status changed from needs_work to needs_review
comment:30 in reply to: ↑ 28 ; followup: ↓ 32 Changed 5 years ago by
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: utf8 * # 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**(n1)*(q**n  e)/(q + 1), " ",\ # (q**(n1) + e)*(q**(n2)  e), " ",\ # q**(2*n5)*(q+1)  e*q**(n2)*(q1)  2, " ",\ # q**(n3)*(q + 1)*(q**(n2)  e),"\n"
 Why 5
is_NO*
functions instead of oneis_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
 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 ; followup: ↓ 33 Changed 5 years ago by
Replying to ncohen:
(tmp✔)~/sage/graphs$ grep "^# " strongly_regular_db.pyx # * coding: utf8 * # 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**(n1)*(q**n  e)/(q + 1), " ",\ # (q**(n1) + e)*(q**(n2)  e), " ",\ # q**(2*n5)*(q+1)  e*q**(n2)*(q1)  2, " ",\ # q**(n3)*(q + 1)*(q**(n2)  e),"\n"
OK, removed, sorry.
 Why 5
is_NO*
functions instead of oneis_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
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 followup: ↓ 35 Changed 5 years ago by
 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 ; followup: ↓ 37 Changed 5 years ago by
Replying to ncohen:
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 (q1,q+1) and (q+1,q1), the others are there already).
 skewHadamard and relatives (I promised to work on this already...)
 GoethalsSeidel (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
 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
 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 (q1,q+1) and (q+1,q1), the others are there already).
 skewHadamard and relatives (I promised to work on this already...)
 GoethalsSeidel (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...
Err.. To be honest I don't know exactly which ones I could work on. If you tell me that you know how to deal with these classes then I can print the list of those that remain and see those that I can settle, as that would give me a starting point.
Nathann
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