Opened 9 years ago
Closed 8 years ago
#14631 closed enhancement (fixed)
Affine Polar Graphs
Reported by:  Nathann Cohen  Owned by:  jason, ncohen, rlm 

Priority:  major  Milestone:  sage6.3 
Component:  graph theory  Keywords:  
Cc:  Dima Pasechnik, Jernej Azarija, Slani  Merged in:  
Authors:  Nathann Cohen, Dima Pasechnik  Reviewers:  Nathann Cohen, Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  3ef564e (Commits, GitHub, GitLab)  Commit:  3ef564e3849c43440b8e27adb0164f3f3d964c02 
Dependencies:  #16362  Stopgaps: 
Description (last modified by )
Thank youuuuuuUUUUUUUUUuuuuuu Brouwer !!! :P
Nathann
P.S. : This patch "does not really" depend on #14589, but here is what happens when calling "is_strongly_regular" on a big graph. With the patch :
sage: g Affine Polar Graph VO^+(10,2): Graph on 1024 vertices sage: %time g.is_strongly_regular(parameters = True) CPU times: user 3.30 s, sys: 0.00 s, total: 3.30 s Wall time: 3.31 s (1024, 527, 270, 272)
Without the patch
sage: %time g.is_strongly_regular(parameters = True) CPU times: user 316.33 s, sys: 0.08 s, total: 316.41 s Wall time: 317.20 s (1024, 527, 270, 272)
Annnnnd the doctests that this patch adds are a bit faster as a result :P
Attachments (1)
Change History (27)
comment:1 Changed 9 years ago by
Description:  modified (diff) 

Status:  new → needs_review 
comment:2 Changed 9 years ago by
Cc:  Jernej Azarija Slani added 

Changed 9 years ago by
Attachment:  trac_14631.patch added 

comment:3 Changed 9 years ago by
Description:  modified (diff) 

comment:4 followup: 5 Changed 9 years ago by
comment:5 followup: 6 Changed 9 years ago by
How about "normal" polar space graphs? Any affine polar graph is (perhaps a quotients of) the subgraph induced on the nonneighbours of a vertex in a polar space graph.
Ahahah. Dima, I have NOooooooooo idea what "normal polar space graphs" are. I barely understand what this patch does in the first place. Why don't you give it a try, by the way ?
Nathann
comment:6 Changed 9 years ago by
Replying to ncohen:
How about "normal" polar space graphs? Any affine polar graph is (perhaps a quotients of) the subgraph induced on the nonneighbours of a vertex in a polar space graph.
Ahahah. Dima, I have NOooooooooo idea what "normal polar space graphs" are.
I sent you a link to a text about them, didn't I? Here is another link: http://www.win.tue.nl/~aeb/graphs/srghub.html Most of the graphs described there are of this type (expect the Grassmann graphs, E_6, and the rest of lowdimensional examples).
I barely understand what this patch does in the first place. Why don't you give it a try, by the way ?
I have about 10 other things I must work on now (if not last month or year :)), and organization of this: http://web.spms.ntu.edu.sg/~dima/IMS2013/ And I don't even have a fixed job, as you know, so you don't feel the pressure I do feel from this side...
comment:7 Changed 9 years ago by
Milestone:  sage5.11 → sage5.12 

comment:8 Changed 9 years ago by
Branch:  → u/ncohen/14631 

Made it a Git branch, as I need to use it.
Nathann
comment:9 Changed 9 years ago by
Commit:  → a9faba0865604b6f7445adfa80728d7adccb4e08 

Branch pushed to git repo; I updated commit sha1. New commits:
a9faba0  trac #14631: Affine Polar Graphs

comment:10 Changed 9 years ago by
Milestone:  sage6.1 → sage6.2 

comment:11 Changed 8 years ago by
Milestone:  sage6.2 → sage6.3 

comment:12 followup: 13 Changed 8 years ago by
With #16362 one can construct VO(n,q,<sign>) by merely taking the subgraph induced on nonneighbours of a vertex in
OrthogonalPolarGraph(n+2,q,<sign>)
. I don't insist on rewriting the code, but this should at least be mentioned in the docs somewhere.
comment:13 Changed 8 years ago by
With #16362 one can construct VO(n,q,<sign>) by merely taking the subgraph induced on nonneighbours of a vertex in
OrthogonalPolarGraph(n+2,q,<sign>)
. I don't insist on rewriting the code, but this should at least be mentioned in the docs somewhere.
That's what happens when a patch stays in "needs_review" for one year.
I will add a commit in a second :P
Nathann
comment:14 Changed 8 years ago by
Commit:  a9faba0865604b6f7445adfa80728d7adccb4e08 → e725be93e85e2212be7346b7d14edd2f91d43dfc 

Branch pushed to git repo; I updated commit sha1. New commits:
a1ec9b5  trac #14631: Merged with 6.3.beta1

6adc14b  trac #16362: Polar Graph

f1e4fb3  just a small pep8 cleanup

e3c4aaa  trac #16362: Reviewer's comments

0089d6c  trac #16362: Broken documentation

c5cc1d9  trac #14631: Merged with #16362

e725be9  trac #14631: Note added

comment:15 followup: 16 Changed 8 years ago by
well, my comment on this fact is about a year old :–)
New commits:
a1ec9b5  trac #14631: Merged with 6.3.beta1

6adc14b  trac #16362: Polar Graph

f1e4fb3  just a small pep8 cleanup

e3c4aaa  trac #16362: Reviewer's comments

0089d6c  trac #16362: Broken documentation

c5cc1d9  trac #14631: Merged with #16362

e725be9  trac #14631: Note added

comment:16 followup: 17 Changed 8 years ago by
I don't get a word of what you said in this comment.
Nathann
comment:17 Changed 8 years ago by
Replying to ncohen:
I don't get a word of what you said in this comment.
It must be then pure coincidence that I mention http://www.win.tue.nl/~aeb/graphs/srghub.html there (the link mentioned by you in #16362) :P
comment:19 Changed 8 years ago by
Status:  needs_review → needs_work 

This code has the same potential bug as mentioned in here. Please fix.
comment:20 Changed 8 years ago by
Also, for consistency with #16362, the function AffinePolarGraph
should be renamed AffineOrthogonalPolarGraph
.
comment:21 Changed 8 years ago by
Dependencies:  #14589 → #16362 

Status:  needs_work → needs_review 
Done.
comment:22 Changed 8 years ago by
Commit:  e725be93e85e2212be7346b7d14edd2f91d43dfc → 4f82fa59211318a79c6ba03a1484c5aea25bb5cb 

comment:23 Changed 8 years ago by
Branch:  u/ncohen/14631 → u/dimpase/14631 

comment:24 Changed 8 years ago by
Commit:  4f82fa59211318a79c6ba03a1484c5aea25bb5cb → 3ef564e3849c43440b8e27adb0164f3f3d964c02 

if you're happy with my changes please set this to positive review!
New commits:
3ef564e  libGAPification

comment:25 Changed 8 years ago by
Reviewers:  → Nathann Cohen, Dima Pasechnik 

Status:  needs_review → positive_review 
Well, given that it still passes tests... :)
Nathann
comment:26 Changed 8 years ago by
Branch:  u/dimpase/14631 → 3ef564e3849c43440b8e27adb0164f3f3d964c02 

Resolution:  → fixed 
Status:  positive_review → closed 
How about "normal" polar space graphs? Any affine polar graph is (perhaps a quotients of) the subgraph induced on the nonneighbours of a vertex in a polar space graph.