Opened 5 years ago

Closed 5 years ago

Last modified 5 years ago

#19136 closed enhancement (fixed)

NO and NU graphs

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

Change History (37)

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

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 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
  • Commit set to abf0a5e6f9a2aa52550555d77e9bfc654ad59399

Last 10 new commits:

9510c70trac #19098: Speedup
4fd56a1use TaylorTwographSRG in taylor_twograph
83f94e4just add vertex v0
6c0c890trac #19133: Merged with 6.9.beta5
3bc31a1trac #19133: Broken doctests
ffcf6acMerge remote-tracking branch 'trac/public/19133' into tay2
2159763fix a docstring typo in #19133
6253d7aadded INPUT, removed unnecessary check
ecd04ffMerge branch 'tay2' into NONU
abf0a5eimplemented 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)`.

sound about right?

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

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 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:

a0b6349implemented 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:

826e475NU(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:

50c5c92a largely failed attempt to do NO^e(2m-1,q)
1bb2572done 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:

7caba1adone 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:

d28689edone with NO^e(m,q, (perp)), and its recognition for DB
7cbfa8btrac #19180: A (220,84,38,28)-strongly regular graph
6ce1899trac #19180: Speedup
ee2d06dMerge 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:

26db5ecMerge branch 'develop' of git://trac.sagemath.org/sage into NONU
d70bf50implemented 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:

2bd5f54fix for a silly bug in is_NOodd, moar doctests

comment:19 Changed 5 years ago by dimpase

  • Status changed from new to needs_review

the patchbomb is ready!

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

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

  • 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? 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:

a0a3320added SymplecticGraph to graphs.* and fixed a typo there, and a doctest
3bd8437else if -> elif, other things in NonisotropicOrthogonalPolarGraph
79ce567speedups by calling vector() once

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

Replying to ncohen:

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

dbc50b1remove forgotten prints

comment:32 in reply to: ↑ 30 ; follow-up: 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: 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: Changed 5 years ago by dimpase

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 (q-1,q+1) and (q+1,q-1), the others are there already).
  • skew-Hadamard and relatives (I promised to work on this 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).
  • skew-Hadamard and relatives (I promised to work on this 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...

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

Note: See TracTickets for help on using tickets.