Opened 7 years ago
Closed 7 years ago
#18997 closed enhancement (fixed)
Unitary and symplectic (dual) polar graphs
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:  ee9c5d6 (Commits, GitHub, GitLab)  Commit:  ee9c5d61e1c3976fe87cf01ddc8315b33238cdd6 
Dependencies:  #18972  Stopgaps: 
Description (last modified by )
implement the classical unitary (reps. symplectic) ordinary and dual polar graphs U(n,q)
(resp. Sp(2d,q)
), see
http://www.win.tue.nl/~aeb/graphs/srghub.html for the ordinary ones, and [BCN89] for the dual ones (for these of diameter bigger than 2).
As well, recognise the corresponding SRGs in the DB.
Change History (30)
comment:1 Changed 7 years ago by
 Dependencies set to #18972
comment:2 followup: ↓ 3 Changed 7 years ago by
comment:3 in reply to: ↑ 2 Changed 7 years ago by
 Description modified (diff)
 Summary changed from Unitary polar graphs to Unitary and symplectic polar graphs
Replying to ncohen:
Is there any reason why you made this ticket depend on #18972? It seems easier to finalize, and apparently does not rely on anything from that other ticket.
this is merely to avoid merging troubles, as they are both changing strongly_regular_db
.
(I'm still writing the latter part of this ticket, and speeding the construction up).
And I will add a contruction of symplectic polar graphs here, as it's almost identical...
comment:4 followup: ↓ 5 Changed 7 years ago by
Okayokay. I am looking at generalized quadrangles at the moment. Seems that we will have to build some of them.
Nathann
comment:5 in reply to: ↑ 4 ; followup: ↓ 6 Changed 7 years ago by
Replying to ncohen:
Okayokay. I am looking at generalized quadrangles at the moment. Seems that we will have to build some of them.
we are already building GQ(q,q)
and GQ(q,q^2)
; this ticket will give GQ(q^2,q)
and GQ(q^2,q^3)
. So we will need GQ(q^3,q^2)
 I can do this on this ticket too, as
this is essentially a small modification:
 I build points and lines of the
GQ(q^2,q^3)
, and use them to create the graph;  I can also use them to create the intersection graph of the lines, which will give the graph of
GQ(q^3,q^2)
.
What remains is GQ(q1,q+1)
and its dual, GQ(q+1,q1)
.
comment:6 in reply to: ↑ 5 ; followup: ↓ 7 Changed 7 years ago by
we are already building
GQ(q,q)
andGQ(q,q^2)
;
Oh, really? Shouldn't they be incidence structures in their most natural form instead? I thought that it would make more sense to have a hypergraphs.generalized_quadrangle
that would then be called by graph constructors.
comment:7 in reply to: ↑ 6 Changed 7 years ago by
Replying to ncohen:
we are already building
GQ(q,q)
andGQ(q,q^2)
;Oh, really?
yes, sure, it's OrthogonalPolarGraph(5,q)
and OrthogonalPolarGraph(6,q,'')
.
Shouldn't they be incidence structures in their most natural form instead? I thought that it would make more sense to have a
hypergraphs.generalized_quadrangle
that would then be called by graph constructors.
well, they are a part of a more general construction, polar spaces. We can have hypergraphs.polar_space
of which hypergraphs.generalized_quadrangle
is a subclass...
comment:8 Changed 7 years ago by
 Commit changed from 971476d1d7bb4a32cacf70c1d8de478295423aa9 to cd864554e81ada74a00759e40ec6edd7bac609ca
Branch pushed to git repo; I updated commit sha1. New commits:
cd86455  addded dial polar graphs, libGAP way to construct them

comment:9 Changed 7 years ago by
 Description modified (diff)
 Summary changed from Unitary and symplectic polar graphs to Unitary and symplectic (dual) polar graphs
actually, there already was graphs.SymplecticGraph
, so to it I just added another algorithm to build it, which is faster for fields of size bigger than 3.
comment:10 Changed 7 years ago by
 Commit changed from cd864554e81ada74a00759e40ec6edd7bac609ca to 4af0f07d4928e2d7dba8d8734abc3229ce245201
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
19b40d9  trac #19019: Sort the list of SRGs

778556f  Merge remotetracking branch 'trac/u/ncohen/19019' into t19019

6ed716d  added a doctest

cb0b3fb  Merge branch 'reg_symm_hadamard' into t19019

2c4a38a  Merge branch '#19019' into seidelsw

8601814  removed duplicate [BH12]

6ba4533  docs for twographs class

afbf2cb  docs changes; hyperlinks etc

86bf5b8  remove twographs.* from global namespace, added to design_catalog

4af0f07  Merge branch 'seidelsw' into unitary

comment:11 Changed 7 years ago by
 Commit changed from 4af0f07d4928e2d7dba8d8734abc3229ce245201 to d1f653efccf25283d1102bf5372ace78d3598db1
Branch pushed to git repo; I updated commit sha1. New commits:
d1f653e  added recongision of (dual) unitary graphs to the DB

comment:12 Changed 7 years ago by
 Description modified (diff)
 Status changed from new to needs_review
comment:13 Changed 7 years ago by
 Commit changed from d1f653efccf25283d1102bf5372ace78d3598db1 to 1765846d94a8f0fdac54fa922be881c2f50d0c59
Branch pushed to git repo; I updated commit sha1. New commits:
2fae2fc  fixed docs for twograph_descendant, adjusted the Graph methods indices

799a2bf  speeding up twograph_descendant

b9fd7af  removed spaces and added r's

68c0edd  moved twograph_descendant to twographs.py, and docs improved

3fc3bb2  Merge branch 'seidelsw' into unitary

1765846  fixing sphynx docbuild

comment:14 Changed 7 years ago by
 Commit changed from 1765846d94a8f0fdac54fa922be881c2f50d0c59 to ab18d25ae8046bb3091b7741ca930f60100b807e
Branch pushed to git repo; I updated commit sha1. New commits:
6bc5cbd  next round of fixes, cf #18972:75

d9b098a  trac #18972: Reviewer's commit

e7022f3  trac #18972: inplace seidel_switching

f4add31  Merge branch 'develop' into seidelsw

4f7e3c9  1st portion of fixes for #18972:81

a336241  The rest of fixes for #18972:81:

ab18d25  merge Merge branch 'unitary' into the latest #18972

comment:15 Changed 7 years ago by
for the life of me, I get
OSError: [graphs ] /home/dima/software/sage/local/lib/python2.7/sitepackages/sage/graphs/graph_generators.py:docstring of sage.graphs.graph_generators.GraphGenerators.SymplecticGraph:16: WARNING: Literal block expected; none found.
no matter how I try building the docs... No f*cking idea why I get this error.
comment:16 Changed 7 years ago by
Does this help (maybe the changes for _polar_Graph
are unnecessary):

src/sage/graphs/generators/families.py
diff git a/src/sage/graphs/generators/families.py b/src/sage/graphs/generators/families.py index 0fadbbd..89777b0 100644
a b def _polar_Graph(m, q, g, intersection_size=None): 2535 2535 2536 2536 TESTS:: 2537 2537 2538 sage: from sage.graphs.generators.families import _polar_Graph2539 sage: _polar_Graph(4, 4, libgap.GeneralUnitaryGroup(4, 2))2540 Graph on 45 vertices2541 sage: _polar_Graph(4, 4, libgap.GeneralUnitaryGroup(4, 2), intersection_size=1)2542 Graph on 27 vertices2538 sage: from sage.graphs.generators.families import _polar_Graph 2539 sage: _polar_Graph(4, 4, libgap.GeneralUnitaryGroup(4, 2)) 2540 Graph on 45 vertices 2541 sage: _polar_Graph(4, 4, libgap.GeneralUnitaryGroup(4, 2), intersection_size=1) 2542 Graph on 27 vertices 2543 2543 """ 2544 2544 from sage.libs.gap.libgap import libgap 2545 2545 from itertools import combinations … … def SymplecticDualPolarGraph(m, q): 2675 2675 2676 2676 EXAMPLES:: 2677 2677 2678 sage: G = graphs.SymplecticDualPolarGraph(6,2); G2679 Symplectic Polar Graph O(6, 2): Graph on 135 vertices2680 sage: G.is_distance_regular(parameters=True)2681 ([14, 12, 8, None], [None, 1, 3, 7])2678 sage: G = graphs.SymplecticDualPolarGraph(6,2); G 2679 Symplectic Polar Graph O(6, 2): Graph on 135 vertices 2680 sage: G.is_distance_regular(parameters=True) 2681 ([14, 12, 8, None], [None, 1, 3, 7]) 2682 2682 2683 2683 TESTS:: 2684 2684 2685 sage: G = graphs.SymplecticDualPolarGraph(6,3); G # long time2686 Symplectic Polar Graph O(6, 3): Graph on 1120 vertices2687 sage: G.is_distance_regular(parameters=True) # long time2688 ([39, 36, 27, None], [None, 1, 4, 13])2685 sage: G = graphs.SymplecticDualPolarGraph(6,3); G # long time 2686 Symplectic Polar Graph O(6, 3): Graph on 1120 vertices 2687 sage: G.is_distance_regular(parameters=True) # long time 2688 ([39, 36, 27, None], [None, 1, 4, 13]) 2689 2689 """ 2690 2690 from sage.libs.gap.libgap import libgap 2691 2691 G = _polar_Graph(m, q, libgap.SymplecticGroup(m, q),
If you feel like fixing some other minor docstring issues, you could make these changes, too:

src/sage/graphs/generators/families.py
diff git a/src/sage/graphs/generators/families.py b/src/sage/graphs/generators/families.py index 0fadbbd..953b576 100644
a b def BalancedTree(r, h): 192 192 193 193 TESTS: 194 194 195 196 197 195 Normally we would only consider balanced trees whose root node 196 has degree `r \geq 2`, but the construction degenerates 197 gracefully:: 198 198 199 199 sage: graphs.BalancedTree(1, 10) 200 200 Balanced tree: Graph on 2 vertices 
src/sage/graphs/generators/random.py
diff git a/src/sage/graphs/generators/random.py b/src/sage/graphs/generators/random.py index 01f9c13..246250d 100644
a b def RandomToleranceGraph(n): 749 749 sage: g.clique_number() == g.chromatic_number() 750 750 True 751 751 752 TEST: 752 TEST:: 753 753 754 754 sage: g = graphs.RandomToleranceGraph(2) 755 755 Traceback (most recent call last): 
src/sage/graphs/generators/smallgraphs.py
diff git a/src/sage/graphs/generators/smallgraphs.py b/src/sage/graphs/generators/smallgraphs.py index 39ca04e..27e1124 100644
a b def ChvatalGraph(): 1810 1810 2 1811 1811 4 1812 1812 1813 TEST: 1813 TEST:: 1814 1814 1815 1815 sage: import networkx 1816 1816 sage: G = graphs.ChvatalGraph() … … def FruchtGraph(): 2647 2647 'KhCKM?_EGK?L' 2648 2648 sage: (graphs.FruchtGraph()).show() # long time 2649 2649 2650 TEST: 2650 TEST:: 2651 2651 2652 2652 sage: import networkx 2653 2653 sage: G = graphs.FruchtGraph() … … def HeawoodGraph(): 2896 2896 'MhEGHC@AI?_PC@_G_' 2897 2897 sage: (graphs.HeawoodGraph()).show() # long time 2898 2898 2899 TEST: 2899 TEST:: 2900 2900 2901 2901 sage: import networkx 2902 2902 sage: G = graphs.HeawoodGraph() … … def KrackhardtKiteGraph(): 3363 3363 sage: g = graphs.KrackhardtKiteGraph() 3364 3364 sage: g.show() # long time 3365 3365 3366 TEST: 3366 TEST:: 3367 3367 3368 3368 sage: import networkx 3369 3369 sage: G = graphs.KrackhardtKiteGraph() 
src/sage/graphs/strongly_regular_db.pyx
diff git a/src/sage/graphs/strongly_regular_db.pyx b/src/sage/graphs/strongly_regular_db.pyx index 44a6640..f28248c 100644
a b def strongly_regular_graph(int v,int k,int l,int mu=1,bint existence=False): 1518 1518 ... 1519 1519 RuntimeError: Sage cannot figure out if a (1394,175,0,25)strongly regular graph exists. 1520 1520 1521 Test the Claw bound (see 3.D of [vLintBrouwer84]_): 1521 Test the Claw bound (see 3.D of [vLintBrouwer84]_):: 1522 1522 1523 1523 sage: graphs.strongly_regular_graph(2058,242,91,20,existence=True) 1524 1524 False
You could also change "TEST:" to "TESTS:" throughout, but I don't really care much about that.
comment:17 Changed 7 years ago by
 Commit changed from ab18d25ae8046bb3091b7741ca930f60100b807e to 5450f1e1e8c20fe86d25e001c495bbcd3f5719c0
Branch pushed to git repo; I updated commit sha1. New commits:
5450f1e  doctest fixes from John Palmieri: Thanks John! They help!

comment:18 Changed 7 years ago by
 Commit changed from 5450f1e1e8c20fe86d25e001c495bbcd3f5719c0 to 35a9b1752da8eadddc03b68e584ceffa9e14bc93
Branch pushed to git repo; I updated commit sha1. New commits:
3350efc  inplace has arrived here too

4e077db  making internet and gap_packages tests optional

0d20a94  inplace has arrived here too

7d15add  trac #18972: Speedup is_twograph

7a690de  trac #18972: speedup Graph.twograph

4e3a0ea  Merge branch 'public/18972' of git://trac.sagemath.org/sage into HEAD

95fe0f2  Merge remotetracking branch 'trac/public/18972' into seidelsw

25eec1b  uniformity, but no regularity

50a6efc  Merge branch 'seidelsw' into unitary

35a9b17  doctest fixes

comment:19 followup: ↓ 21 Changed 7 years ago by
 Status changed from needs_review to needs_work
Helloooooooo Dima,
Here is a 'firstpass' review:
 This doctest is way too long:
sage: %time graphs.SymplecticGraph(6,4,algorithm="gap").is_strongly_regular(parameters=True) CPU times: user 22 s, sys: 132 ms, total: 22.2 s Wall time: 21.1 s (1365, 340, 83, 85)
You will see several places in this file doctests disabled because they take ~5seconds. This, because the doctests are run very often by a lot of people, and we can't have them compute for 20 seconds whenever we add a function (and we do add many). Could you replace this6,4
by4,4
or something?
 Why is this only checked when
algorithm="gap"
?if d < 1 or d%2 != 0: raise ValueError("d must be even and greater than 2")
_polar_graph
 misses an 'INPUT' section
 Could you merge this branch with the latest version of its dependency?
 in
_polar_Graph
 why upper caseG
?
 same function: would it make sense to compute the list of edges of the graph in GAP instead of doing it in Sage, which triggers GAP calls? Just wondering, as it seems that interacting with GAP is often costly.
Nathann
comment:20 Changed 7 years ago by
 Reviewers set to Nathann Cohen
comment:21 in reply to: ↑ 19 Changed 7 years ago by
Replying to ncohen:
 Why is this only checked when
algorithm="gap"
?if d < 1 or d%2 != 0: raise ValueError("d must be even and greater than 2")
oops, it's a bug...
 in
_polar_Graph
 why upper caseG
?
 same function: would it make sense to compute the list of edges of the graph in GAP instead of doing it in Sage, which triggers GAP calls? Just wondering, as it seems that interacting with GAP is often costly.
this is libGAP
, we can be reasonably sure that at least with noncomplicated objects,
like integers, this is as quick as native Python... (certainly, replacing libgap
with gap
there would lead to a huge performance hit).
comment:22 Changed 7 years ago by
 Commit changed from 35a9b1752da8eadddc03b68e584ceffa9e14bc93 to acc985a045f02a1c796accd9a029ae809a0a92fd
comment:23 Changed 7 years ago by
 Status changed from needs_work to needs_review
comment:24 followup: ↓ 25 Changed 7 years ago by
 Status changed from needs_review to needs_work
Helloooooooo Dima,
 About the methods with a "algorithm" keyword: some of them do not have an
INPUT
block where the parameter is described. Also, it would be better if instead of checking!= 'gap'
you testedalgorithm =='Gap'
then `algorithm is None` and finally raised an exception if the argument does not beelong to the allowed list. This being said, I would have nothing against it if you chose to remove the pure Sage code. It's up to you.
 Backticks are missing around
Sp(x,y)
and others.
 We have
SimplecticGraph
andSimplecticDualPolarGraph
 should we uniformize thePolar
somehow?
 singilar
 Can you please remove/change all tests that take more than 2 seconds? Don't
build instances larger than is necessary to *test* your code. With your
branch:
sage t long families.py [280 tests, 44.02 s]
With the latest betasage t long families.py [250 tests, 19.95 s]
 Some graphs are not defined on a html page, and for those you link toward "Distanceregular graphs". As this is much harder to find than a web page, could you provide some quick definition of the class, just to give the user "an idea"?
 You may want (it's up to you) to add "SEEALSO" blocks between your methods.
 As we now have many of these polar graphs, you may want (it's up to you) to split them from the "Graph families" block of the index (http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_generators.html) and give them a block of their own.
Thank you *very* much for this code.
Nathann
comment:25 in reply to: ↑ 24 ; followup: ↓ 28 Changed 7 years ago by
Replying to ncohen:
Helloooooooo Dima,
 About the methods with a "algorithm" keyword: some of them do not have an
INPUT
block where the parameter is described. Also, it would be better if instead of checking!= 'gap'
you testedalgorithm =='Gap'
then `algorithm is None` and finally raised an exception if the argument does not beelong to the allowed list. This being said, I would have nothing against it if you chose to remove the pure Sage code. It's up to you.
it's always better to have 2 implementations... I'll rearrange as you ask.
 Backticks are missing around
Sp(x,y)
and others.
 We have
SimplecticGraph
andSimplecticDualPolarGraph
 should we uniformize thePolar
somehow?
yep, how about renaming SimplecticGraph
to SimplecticPolarGraph
and make SimplecticGraph
a deprecated alias to SimplecticPolarGraph
?
 Can you please remove/change all tests that take more than 2 seconds?
How about I'll move them into examples and mark them # not tested (long time)? They test "generic" situations, whereas all the small examples there are kinds of corner cases.
 Some graphs are not defined on a html page, and for those you link toward "Distanceregular graphs". As this is much harder to find than a web page, could you provide some quick definition of the class, just to give the user "an idea"?
all these SymplecticPolar
, OrthogonalPolar
, etc are very similar, as
well as all SymplecticDualPolar
etc.
There is a freely available preprint that describes them in detail:
https://repository.cwi.nl/noauth/search/fullrecord.php?publnr=6775
I'd rather include this as a reference.
Perhaps it's more meaningful to create a separate module, say polar_families.py,
where we move all them, as well as AffinePolar
guys. Then a doc can be written
in the top of this new module.
We could also extend the wikipedia page https://en.wikipedia.org/wiki/Distanceregular_graph and have docs there...
 You may want (it's up to you) to add "SEEALSO" blocks between your methods.
 As we now have many of these polar graphs, you may want (it's up to you) to split them from the "Graph families" block of the index (http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_generators.html) and give them a block of their own.
this would be even more meaningful with a new module.
comment:26 Changed 7 years ago by
 Commit changed from acc985a045f02a1c796accd9a029ae809a0a92fd to ee9c5d61e1c3976fe87cf01ddc8315b33238cdd6
Branch pushed to git repo; I updated commit sha1. New commits:
ee9c5d6  address #18997:24

comment:27 Changed 7 years ago by
 Status changed from needs_work to needs_review
I'd rather do the reorganisation elsewhere. E.g. to make the list of dual polar graphs complete, one should add orthogonal dual polar graphs.
comment:28 in reply to: ↑ 25 Changed 7 years ago by
Hello,
yep, how about renaming
SimplecticGraph
toSimplecticPolarGraph
and makeSimplecticGraph
a deprecated alias toSimplecticPolarGraph
?
+1
There is a freely available preprint that describes them in detail: https://repository.cwi.nl/noauth/search/fullrecord.php?publnr=6775
I'd rather include this as a reference.
Works for me.
it's more meaningful to create a separate module, say polar_families.py, where we move all them, as well as
AffinePolar
guys. Then a doc can be written in the top of this new module.
+1
We could also extend the wikipedia page https://en.wikipedia.org/wiki/Distanceregular_graph and have docs there...
+1. Though I beware of wikipedia now. I have experienced how hard it is to fight the whims of those who are "in charge" of some pages...
this would be even more meaningful with a new module.
+1
I'd rather do the reorganisation elsewhere. E.g. to make the list of dual polar graphs complete, one should add orthogonal dual polar graphs.
Reorganization can indeed wait, but must not forget to address the "SymplecticDualPolarGraph?" vs "SymplecticGraph?" issue.
Nathann
comment:29 Changed 7 years ago by
 Status changed from needs_review to positive_review
comment:30 Changed 7 years ago by
 Branch changed from u/dimpase/unitary to ee9c5d61e1c3976fe87cf01ddc8315b33238cdd6
 Resolution set to fixed
 Status changed from positive_review to closed
Is there any reason why you made this ticket depend on #18972? It seems easier to finalize, and apparently does not rely on anything from that other ticket.
Nathann