Opened 5 years ago
Closed 5 years ago
#19098 closed enhancement (fixed)
implement Taylor 2graphs for U_3(q) and related srg's
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:  6253d7a (Commits)  Commit:  6253d7ad6618213d1f32bd818592b5e7b83ef467 
Dependencies:  #18972, #18997, #19099, #19133  Stopgaps: 
Description
implement Taylor 2graphs for U_3(q) and related srg's; the latter have to be constructed directly, as the twograph gets very big and slow.
see §7E of Brouwer and van Lint and note the correction saying
§7E, A construction by D. Taylor, it should say: ...
"the triples {x,y,z} for which H(x,y)H(y,z)H(z,x) is a square in GF(q^2
) if q ≡ 3 mod 4, a nonsquare if q ≡ 1 mod 4"
Change History (49)
comment:1 Changed 5 years ago by
comment:2 Changed 5 years ago by
 Cc ncohen added
comment:3 Changed 5 years ago by
 Branch set to u/dimpase/taylor2graphs
 Commit set to ef096b5f3c3c4eeb745cf3e27f5e66094b08550d
Last 10 new commits:
ab18d25  merge Merge branch 'unitary' into the latest #18972

5450f1e  doctest fixes from John Palmieri: Thanks John! They help!

50a6efc  Merge branch 'seidelsw' into unitary

35a9b17  doctest fixes

fd9a689  Merge branch 'seidelsw' into unitary

acc985a  addressed reviewer's points

ee9c5d6  address #18997:24

88ed777  Merge branch 'develop' into unitary

ce952f9  Merge branch 'unitary' into taylor2graphs

ef096b5  implement the constructions of SRGs on q^3 and q^3+1 points

comment:4 Changed 5 years ago by
 Dependencies set to #18972, #18997
comment:5 Changed 5 years ago by
 Commit changed from ef096b5f3c3c4eeb745cf3e27f5e66094b08550d to 52b555929e8511cf761972559ded1e6064863bd1
comment:6 Changed 5 years ago by
 Dependencies changed from #18972, #18997 to #18972, #18997, #19099
New commits:
56d98a3  trac #19099: Always check output in strongly_regular_graph

52b5559  Merge branch 'u/ncohen/19099' of git://trac.sagemath.org/sage into taylor2graphs

New commits:
56d98a3  trac #19099: Always check output in strongly_regular_graph

52b5559  Merge branch 'u/ncohen/19099' of git://trac.sagemath.org/sage into taylor2graphs

comment:7 Changed 5 years ago by
 Commit changed from 52b555929e8511cf761972559ded1e6064863bd1 to 9758eb6bb55c36ea708a2eb1d75f85fd8bb844a6
comment:8 Changed 5 years ago by
 Commit changed from 9758eb6bb55c36ea708a2eb1d75f85fd8bb844a6 to 773d10d2b417f72829fcf0556f2426bd02cd0efb
Branch pushed to git repo; I updated commit sha1. New commits:
773d10d  more doctests and docs and typos fixed

comment:9 followup: ↓ 10 Changed 5 years ago by
 Status changed from new to needs_review
I don't grok that **kwds
business; the following does not work:
diff git a/src/sage/combinat/designs/twographs.py b/src/sage/combinat/designs/twographs.py index c86506b..d3b51c8 100644  a/src/sage/combinat/designs/twographs.py +++ b/src/sage/combinat/designs/twographs.py @@ 68,8 +68,7 @@ class TwoGraph(IncidenceStructure): :mod:`~sage.combinat.designs.twographs` module. """  def __init__(self, points=None, blocks=None, incidence_matrix=None,  name=None, check=False, copy=True): + def __init__(self, check=False, **kwds): r""" Constructor of the class @@ 86,9 +85,7 @@ class TwoGraph(IncidenceStructure): sage: TwoGraph(p, check=True) Incidence structure with 10 points and 60 blocks """  IncidenceStructure.__init__(self, points=points, blocks=blocks,  incidence_matrix=incidence_matrix,  name=name, check=False, copy=copy) + IncidenceStructure.__init__(self, check=False, **kwds) if check: # it is a very slow, O(points^4), test... from sage.combinat.designs.twographs import is_twograph assert is_twograph(self), "the structure is not a 2graph!"
Any idea? Otherwise, the ticket is ready...
comment:10 in reply to: ↑ 9 ; followup: ↓ 12 Changed 5 years ago by
Any idea? Otherwise, the ticket is ready...
What do you think of bug reports which say "that does not work" and do not say what's wrong?
comment:11 Changed 5 years ago by
 Status changed from needs_review to needs_work
doc does not build, see patchbot report
comment:12 in reply to: ↑ 10 Changed 5 years ago by
Replying to ncohen:
Any idea? Otherwise, the ticket is ready...
What do you think of bug reports which say "that does not work" and do not say what's wrong?
well, I was wondering whether what I tried was totally silly... Anyhow, here is what I get after this change:
sage t twographs.py ********************************************************************** File "twographs.py", line 78, in sage.combinat.designs.twographs.TwoGraph.__init__ Failed example: TwoGraph([[1,2]]) Exception raised: Traceback (most recent call last): File "/home/dima/software/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 496, in _run self.compile_and_execute(example, compiler, test.globs) File "/home/dima/software/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 858, in compile_and_execute exec(compiled, globs) File "<doctest sage.combinat.designs.twographs.TwoGraph.__init__[1]>", line 1, in <module> TwoGraph([[Integer(1),Integer(2)]]) File "/home/dima/software/sage/local/lib/python2.7/sitepackages/sage/combinat/designs/twographs.py", line 88, in __init__ IncidenceStructure.__init__(self, check=False, **kwds) File "/home/dima/software/sage/local/lib/python2.7/sitepackages/sage/combinat/designs/incidence_structures.py", line 241, in __init__ self._points = sorted(points) TypeError: 'NoneType' object is not iterable ********************************************************************** File "twographs.py", line 80, in sage.combinat.designs.twographs.TwoGraph.__init__ Failed example: TwoGraph([[1,2]], check=True) Expected: Traceback (most recent call last): ... AssertionError: the structure is not a 2graph! Got: <BLANKLINE> Traceback (most recent call last): File "/home/dima/software/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 496, in _run self.compile_and_execute(example, compiler, test.globs) File "/home/dima/software/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 858, in compile_and_execute exec(compiled, globs) File "<doctest sage.combinat.designs.twographs.TwoGraph.__init__[2]>", line 1, in <module> TwoGraph([[Integer(1),Integer(2)]], check=True) TypeError: __init__() got multiple values for keyword argument 'check' ********************************************************************** File "twographs.py", line 84, in sage.combinat.designs.twographs.TwoGraph.__init__ Failed example: p=graphs.PetersenGraph().twograph() ...
comment:13 Changed 5 years ago by
 Commit changed from 773d10d2b417f72829fcf0556f2426bd02cd0efb to bc401cef4985f4dff03d932786f33aeb574528df
Branch pushed to git repo; I updated commit sha1. New commits:
bc401ce  satisfied sphinx (bug shows only after make docclean)

comment:14 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:15 followup: ↓ 16 Changed 5 years ago by
What is this ? O_o
+ cf. ``git blame`` for the others involved
Nathann
comment:16 in reply to: ↑ 15 ; followup: ↓ 18 Changed 5 years ago by
Replying to ncohen:
What is this ?
O_o
+ cf. ``git blame`` for the others involved
What, your legal department does not approve this copyright notice?
comment:17 Changed 5 years ago by
of course I can remove it if you like...
comment:18 in reply to: ↑ 16 ; followup: ↓ 20 Changed 5 years ago by
What, your legal department does not approve this copyright notice?
It committed suicide last month, but through an exorcist I was able to get in touch with one of its members: what about just removing the only entry that exists in this file, given that it is not representative of anything, instead of leaving it alone and adding your note?
Nathann
comment:19 Changed 5 years ago by
 Commit changed from bc401cef4985f4dff03d932786f33aeb574528df to 86495a4cfc599a2d25c5efd9fb2c7e6d199454fa
Branch pushed to git repo; I updated commit sha1. New commits:
86495a4  authors cleared

comment:20 in reply to: ↑ 18 Changed 5 years ago by
Replying to ncohen:
What, your legal department does not approve this copyright notice?
It committed suicide last month, but through an exorcist I was able to get in touch with one of its members: what about just removing the only entry that exists in this file, given that it is not representative of anything, instead of leaving it alone and adding your note?
be my guest.
comment:21 followup: ↓ 26 Changed 5 years ago by
 Commit changed from 86495a4cfc599a2d25c5efd9fb2c7e6d199454fa to edb886e9f9d0f505f272fe769e69e8a51ab265df
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
edb886e  authors cleared

comment:22 Changed 5 years ago by
Sorry but I can't review this branch before its dependencies get merged. I'm trying to get the 'diff' file while excluding dependencies, but I can't obtain *only* what this branch changes...
Nathann
comment:23 followup: ↓ 25 Changed 5 years ago by
+ Test whether some Taylor twograph SRG is `(v,k,\lambda,\mu)`strongly regular. + + For more information, see http://www.win.tue.nl/~aeb/graphs/srghub.html.
I don't find "Taylor" in that page.
Nathann
comment:24 Changed 5 years ago by
 Commit changed from edb886e9f9d0f505f272fe769e69e8a51ab265df to 6262d658ffd644af0146835a081d1abc9241a711
Branch pushed to git repo; I updated commit sha1. New commits:
6262d65  give the right references, and also the typo missed earlier

comment:25 in reply to: ↑ 23 Changed 5 years ago by
Replying to ncohen:
+ Test whether some Taylor twograph SRG is `(v,k,\lambda,\mu)`strongly regular. + + For more information, see http://www.win.tue.nl/~aeb/graphs/srghub.html.I don't find "Taylor" in that page.e
fixed by the last commit.
comment:26 in reply to: ↑ 21 Changed 5 years ago by
comment:27 Changed 5 years ago by
comment:28 Changed 5 years ago by
 Commit changed from 6262d658ffd644af0146835a081d1abc9241a711 to 685d86df4c9257a64f4c23501a1c97bd9af59d40
Branch pushed to git repo; I updated commit sha1. New commits:
685d86d  utf8...

comment:29 Changed 5 years ago by
 Commit changed from 685d86df4c9257a64f4c23501a1c97bd9af59d40 to dbca37ec255b521ee12662d915a492f55261b842
Branch pushed to git repo; I updated commit sha1. New commits:
dbca37e  a sporadic example related to 2graphs

comment:30 Changed 5 years ago by
 Commit changed from dbca37ec255b521ee12662d915a492f55261b842 to 6a6f7b3abad0ee5ea82166f79c52e25793775bfd
comment:31 Changed 5 years ago by
 Dependencies changed from #18972, #18997, #19099 to #18972, #18997, #19099, #19133
comment:32 Changed 5 years ago by
Good news: a new beta has been released, so I will be able to review this soon
Bad news: it is in conflcit with the latest beta :/
Nathann
comment:33 followup: ↓ 34 Changed 5 years ago by
 Commit changed from 6a6f7b3abad0ee5ea82166f79c52e25793775bfd to d7878be6695b3386b8e5e10ed71634b08519db7d
Branch pushed to git repo; I updated commit sha1. New commits:
d7878be  Merge branch 'taylor2graphs' into tay2

comment:34 in reply to: ↑ 33 Changed 5 years ago by
comment:35 Changed 5 years ago by
I pushed a speedup at public/19098
.
Nathann
comment:36 followup: ↓ 39 Changed 5 years ago by
Helloooooooooo Dima,
Two questions about this branch:
 It seems that you do not use the
taylor_twograph
function anywhere. If you think that it is useful in its own right I do not mind, but I couldn't help but notice the apparently large overlap between the code oftaylor_twograph
and the code ofTaylorTwographDescendantSRG
. Couldn't you let one of the two functions call the other? Especially since with the speedup commit, it takes less time to build the graph.
 I do not understand the point of this line. Could you explain? To me all it
does is add a vertex
v0
G = H.union(Graph([[v0], lambda x, y: x != y])) # to make sure vertices are not relabeled
Nathann
comment:37 Changed 5 years ago by
 Branch changed from u/dimpase/taylor2graphs to public/19098
 Commit changed from d7878be6695b3386b8e5e10ed71634b08519db7d to 9510c7015c4252b82d60b55d80c47ccd1b6d15f4
New commits:
9510c70  trac #19098: Speedup

comment:38 Changed 5 years ago by
 Commit changed from 9510c7015c4252b82d60b55d80c47ccd1b6d15f4 to 4fd56a1f10901663ea001460dd2dfe0da666f4c8
Branch pushed to git repo; I updated commit sha1. New commits:
4fd56a1  use TaylorTwographSRG in taylor_twograph

comment:39 in reply to: ↑ 36 ; followup: ↓ 40 Changed 5 years ago by
Replying to ncohen:
Helloooooooooo Dima,
Two questions about this branch:
 It seems that you do not use the
taylor_twograph
function anywhere. If you think that it is useful in its own right I do not mind, but I couldn't help but notice the apparently large overlap between the code oftaylor_twograph
and the code ofTaylorTwographDescendantSRG
. Couldn't you let one of the two functions call the other? Especially since with the speedup commit, it takes less time to build the graph.
OK, see my last commit.
 I do not understand the point of this line. Could you explain? To me all it does is add a vertex
v0
G = H.union(Graph([[v0], lambda x, y: x != y])) # to make sure vertices are not relabeled
it makes Graph([v0])
have vertex named by what's in v0
rather than just by number 0.
And so G
's vertex names stay uniform. Perhaps there is a less ugly way, I don't know.
New commits:
4fd56a1  use TaylorTwographSRG in taylor_twograph

comment:40 in reply to: ↑ 39 ; followup: ↓ 42 Changed 5 years ago by
it makes
Graph([v0])
have vertex named by what's inv0
rather than just by number 0.
What about your_graph.add_vertex(v0)
?
comment:41 Changed 5 years ago by
 Commit changed from 4fd56a1f10901663ea001460dd2dfe0da666f4c8 to 83f94e41f1fc8647e105fbf956bea44426e30d5f
Branch pushed to git repo; I updated commit sha1. New commits:
83f94e4  just add vertex v0

comment:42 in reply to: ↑ 40 Changed 5 years ago by
Replying to ncohen:
it makes
Graph([v0])
have vertex named by what's inv0
rather than just by number 0.What about
your_graph.add_vertex(v0)
?
done by the last commit, thanks!
comment:43 followup: ↓ 45 Changed 5 years ago by
Hellooooooooo,
 Could you add an INPUT: section for every function that takes arguments as input?
 It is not necessary to check in
taylor_twograph
thatq
is an odd prime power, as this is done by the call to the subfunction
 Why?
 sage: G = SRG_253_140_87_65() # optional  gap_packages  sage: G.is_strongly_regular(parameters=True) # optional  gap_packages + sage: G = SRG_253_140_87_65() + sage: G.is_strongly_regular(parameters=True)
 (Unrelated) turns out that we have another problem with names
sage: graphs.strongly_regular_graph(126,50,13,24) Subgraph of (Distance graph for distance 2 in ): Graph on 126 vertices
Nathann
comment:44 Changed 5 years ago by
 Commit changed from 83f94e41f1fc8647e105fbf956bea44426e30d5f to 21597637cb5c8a4aa781a1be3dae88375a58979b
comment:45 in reply to: ↑ 43 Changed 5 years ago by
Replying to ncohen:
 Why?
 sage: G = SRG_253_140_87_65() # optional  gap_packages  sage: G.is_strongly_regular(parameters=True) # optional  gap_packages + sage: G = SRG_253_140_87_65() + sage: G.is_strongly_regular(parameters=True)
oops, I forgot to merge later updates to #19133. Fixed in the last push, as well as fixed a further trivial typo in #19133.
 (Unrelated) turns out that we have another problem with names
sage: graphs.strongly_regular_graph(126,50,13,24) Subgraph of (Distance graph for distance 2 in ): Graph on 126 vertices
IMHO all these SRG_...
functions ought to return proper graph names.
not on this ticket...
comment:46 followup: ↓ 47 Changed 5 years ago by
 Commit changed from 21597637cb5c8a4aa781a1be3dae88375a58979b to 6253d7ad6618213d1f32bd818592b5e7b83ef467
Branch pushed to git repo; I updated commit sha1. New commits:
6253d7a  added INPUT, removed unnecessary check

comment:47 in reply to: ↑ 46 Changed 5 years ago by
comment:48 Changed 5 years ago by
 Reviewers set to Nathann Cohen
 Status changed from needs_review to positive_review
Okayyyyyyyyyyyyyyyyyyyyyyyyyyy !!
Thanks,
Nathann
comment:49 Changed 5 years ago by
 Branch changed from public/19098 to 6253d7ad6618213d1f32bd818592b5e7b83ef467
 Resolution set to fixed
 Status changed from positive_review to closed
also improve
__init__
ofTwoGraph
, using**kwds
.