Opened 6 years ago
Closed 5 years ago
#14631 closed enhancement (fixed)
Affine Polar Graphs
Reported by:  ncohen  Owned by:  jason, ncohen, rlm 

Priority:  major  Milestone:  sage6.3 
Component:  graph theory  Keywords:  
Cc:  dimpase, azi, Slani  Merged in:  
Authors:  Nathann Cohen, Dima Pasechnik  Reviewers:  Nathann Cohen, Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  3ef564e (Commits)  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 6 years ago by
 Description modified (diff)
 Status changed from new to needs_review
comment:2 Changed 6 years ago by
 Cc azi Slani added
Changed 6 years ago by
comment:3 Changed 6 years ago by
 Description modified (diff)
comment:4 followup: ↓ 5 Changed 6 years ago by
comment:5 in reply to: ↑ 4 ; followup: ↓ 6 Changed 6 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 in reply to: ↑ 5 Changed 6 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 5 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:8 Changed 5 years ago by
 Branch set to u/ncohen/14631
Made it a Git branch, as I need to use it.
Nathann
comment:9 Changed 5 years ago by
 Commit set to a9faba0865604b6f7445adfa80728d7adccb4e08
Branch pushed to git repo; I updated commit sha1. New commits:
a9faba0  trac #14631: Affine Polar Graphs

comment:10 Changed 5 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:11 Changed 5 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:12 followup: ↓ 13 Changed 5 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 in reply to: ↑ 12 Changed 5 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 5 years ago by
 Commit changed from a9faba0865604b6f7445adfa80728d7adccb4e08 to 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 5 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 in reply to: ↑ 15 ; followup: ↓ 17 Changed 5 years ago by
I don't get a word of what you said in this comment.
Nathann
comment:17 in reply to: ↑ 16 Changed 5 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:18 Changed 5 years ago by
Affine Polar Graph page
should be
Affine Polar Graphs page
comment:19 Changed 5 years ago by
 Status changed from needs_review to needs_work
This code has the same potential bug as mentioned in here. Please fix.
comment:20 Changed 5 years ago by
Also, for consistency with #16362, the function AffinePolarGraph
should be renamed AffineOrthogonalPolarGraph
.
comment:21 Changed 5 years ago by
 Dependencies changed from #14589 to #16362
 Status changed from needs_work to needs_review
Done.
comment:22 Changed 5 years ago by
 Commit changed from e725be93e85e2212be7346b7d14edd2f91d43dfc to 4f82fa59211318a79c6ba03a1484c5aea25bb5cb
comment:23 Changed 5 years ago by
 Branch changed from u/ncohen/14631 to u/dimpase/14631
comment:24 Changed 5 years ago by
 Commit changed from 4f82fa59211318a79c6ba03a1484c5aea25bb5cb to 3ef564e3849c43440b8e27adb0164f3f3d964c02
if you're happy with my changes please set this to positive review!
New commits:
3ef564e  libGAPification

comment:25 Changed 5 years ago by
 Reviewers set to Nathann Cohen, Dima Pasechnik
 Status changed from needs_review to positive_review
Well, given that it still passes tests... :)
Nathann
comment:26 Changed 5 years ago by
 Branch changed from u/dimpase/14631 to 3ef564e3849c43440b8e27adb0164f3f3d964c02
 Resolution set to fixed
 Status changed from positive_review to 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.