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: sage-6.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 ncohen)

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)

trac_14631.patch (4.4 KB) - added by ncohen 6 years ago.

Download all attachments as: .zip

Change History (27)

comment:1 Changed 6 years ago by ncohen

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 6 years ago by ncohen

  • Cc azi Slani added

Changed 6 years ago by ncohen

comment:3 Changed 6 years ago by ncohen

  • Description modified (diff)

comment:4 follow-up: Changed 6 years ago by dimpase

How about "normal" polar space graphs? Any affine polar graph is (perhaps a quotients of) the subgraph induced on the non-neighbours of a vertex in a polar space graph.

comment:5 in reply to: ↑ 4 ; follow-up: Changed 6 years ago by ncohen

How about "normal" polar space graphs? Any affine polar graph is (perhaps a quotients of) the subgraph induced on the non-neighbours 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 dimpase

Replying to ncohen:

How about "normal" polar space graphs? Any affine polar graph is (perhaps a quotients of) the subgraph induced on the non-neighbours 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 low-dimensional 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 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:8 Changed 6 years ago by ncohen

  • Branch set to u/ncohen/14631

Made it a Git branch, as I need to use it.

Nathann

comment:9 Changed 6 years ago by git

  • Commit set to a9faba0865604b6f7445adfa80728d7adccb4e08

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

a9faba0trac #14631: Affine Polar Graphs

comment:10 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:11 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:12 follow-up: Changed 5 years ago by dimpase

With #16362 one can construct VO(n,q,<sign>) by merely taking the subgraph induced on non-neighbours 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 ncohen

With #16362 one can construct VO(n,q,<sign>) by merely taking the subgraph induced on non-neighbours 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 git

  • Commit changed from a9faba0865604b6f7445adfa80728d7adccb4e08 to e725be93e85e2212be7346b7d14edd2f91d43dfc

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

a1ec9b5trac #14631: Merged with 6.3.beta1
6adc14btrac #16362: Polar Graph
f1e4fb3just a small pep8 cleanup
e3c4aaatrac #16362: Reviewer's comments
0089d6ctrac #16362: Broken documentation
c5cc1d9trac #14631: Merged with #16362
e725be9trac #14631: Note added

comment:15 follow-up: Changed 5 years ago by dimpase

well, my comment on this fact is about a year old :–)


New commits:

a1ec9b5trac #14631: Merged with 6.3.beta1
6adc14btrac #16362: Polar Graph
f1e4fb3just a small pep8 cleanup
e3c4aaatrac #16362: Reviewer's comments
0089d6ctrac #16362: Broken documentation
c5cc1d9trac #14631: Merged with #16362
e725be9trac #14631: Note added

comment:16 in reply to: ↑ 15 ; follow-up: Changed 5 years ago by ncohen

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 dimpase

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 dimpase

Affine Polar Graph page should be Affine Polar Graphs page

comment:19 Changed 5 years ago by dimpase

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

Also, for consistency with #16362, the function AffinePolarGraph should be renamed AffineOrthogonalPolarGraph.

comment:21 Changed 5 years ago by ncohen

  • Dependencies changed from #14589 to #16362
  • Status changed from needs_work to needs_review

Done.

comment:22 Changed 5 years ago by git

  • Commit changed from e725be93e85e2212be7346b7d14edd2f91d43dfc to 4f82fa59211318a79c6ba03a1484c5aea25bb5cb

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

257082dtrac #14631: Reviewer's comments
272e18ftrac #16362: Broken doc 2
4f82fa5trac #14631: Merged with #16362

comment:23 Changed 5 years ago by dimpase

  • Branch changed from u/ncohen/14631 to u/dimpase/14631

comment:24 Changed 5 years ago by dimpase

  • Commit changed from 4f82fa59211318a79c6ba03a1484c5aea25bb5cb to 3ef564e3849c43440b8e27adb0164f3f3d964c02

if you're happy with my changes please set this to positive review!


New commits:

3ef564elibGAPification

comment:25 Changed 5 years ago by ncohen

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

  • Branch changed from u/dimpase/14631 to 3ef564e3849c43440b8e27adb0164f3f3d964c02
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.