Unitary and symplectic (dual) polar graphs

[dimpase]

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.

Depends on #18972

CC: @nathanncohen

Component: graph theory

Author: Dima Pasechnik

Branch/Commit: ee9c5d6

Reviewer: Nathann Cohen

Issue created by migration from https://trac.sagemath.org/ticket/18997

[dimpase]

Dependencies: #18972

[nathanncohen]

comment:2

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

[dimpase]

comment:3

Replying to @nathanncohen:

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...

[nathanncohen]

comment:4

Okayokay. I am looking at generalized quadrangles at the moment. Seems that we will have to build some of them.

Nathann

http://cage.ugent.be/~bamberg/FGQ.pdf

[dimpase]

comment:5

Replying to @nathanncohen:

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<sup>2,q</sup>3). So we will need GQ(q<sup>3,q</sup>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<sup>2,q</sup>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<sup>3,q</sup>2).

What remains is GQ(q-1,q+1) and its dual, GQ(q+1,q-1).

[nathanncohen]

comment:6

we are already building GQ(q,q) and GQ(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.

[dimpase]

comment:7

Replying to @nathanncohen:

we are already building GQ(q,q) and GQ(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...

[sagetrac-git]

Changed commit from 971476d to cd86455

[sagetrac-git]

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

cd86455

addded dial polar graphs, libGAP way to construct them

[dimpase]

comment:9

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.

[sagetrac-git]

Changed commit from cd86455 to 4af0f07

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

19b40d9	trac #19019: Sort the list of SRGs
778556f	Merge remote-tracking 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 two-graphs class
afbf2cb	docs changes; hyperlinks etc
86bf5b8	remove twographs.* from global namespace, added to design_catalog
4af0f07	Merge branch 'seidelsw' into unitary

[sagetrac-git]

Changed commit from 4af0f07 to d1f653e

[sagetrac-git]

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

d1f653e

added recongision of (dual) unitary graphs to the DB

[sagetrac-git]

Changed commit from d1f653e to 1765846

[sagetrac-git]

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

[sagetrac-git]

Changed commit from 1765846 to ab18d25

[sagetrac-git]

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

[dimpase]

comment:15

for the life of me, I get

OSError: [graphs   ] /home/dima/software/sage/local/lib/python2.7/site-packages/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.

[jhpalmieri]

comment:16

Does this help (maybe the changes for _polar_Graph are unnecessary):

diff --git a/src/sage/graphs/generators/families.py b/src/sage/graphs/generators/families.py
index 0fadbbd..89777b0 100644
--- a/src/sage/graphs/generators/families.py
+++ b/src/sage/graphs/generators/families.py
@@ -2535,11 +2535,11 @@ def _polar_Graph(m, q, g, intersection_size=None):
 
     TESTS::
 
-    sage: from sage.graphs.generators.families import _polar_Graph
-    sage: _polar_Graph(4, 4, libgap.GeneralUnitaryGroup(4, 2))
-    Graph on 45 vertices
-    sage: _polar_Graph(4, 4, libgap.GeneralUnitaryGroup(4, 2), intersection_size=1)
-    Graph on 27 vertices
+        sage: from sage.graphs.generators.families import _polar_Graph
+        sage: _polar_Graph(4, 4, libgap.GeneralUnitaryGroup(4, 2))
+        Graph on 45 vertices
+        sage: _polar_Graph(4, 4, libgap.GeneralUnitaryGroup(4, 2), intersection_size=1)
+        Graph on 27 vertices
     """
     from sage.libs.gap.libgap import libgap
     from itertools import combinations
@@ -2675,17 +2675,17 @@ def SymplecticDualPolarGraph(m, q):
 
     EXAMPLES::
 
-    sage: G = graphs.SymplecticDualPolarGraph(6,2); G
-    Symplectic Polar Graph O(6, 2): Graph on 135 vertices
-    sage: G.is_distance_regular(parameters=True)
-    ([14, 12, 8, None], [None, 1, 3, 7])
+        sage: G = graphs.SymplecticDualPolarGraph(6,2); G
+        Symplectic Polar Graph O(6, 2): Graph on 135 vertices
+        sage: G.is_distance_regular(parameters=True)
+        ([14, 12, 8, None], [None, 1, 3, 7])
 
     TESTS::
 
-    sage: G = graphs.SymplecticDualPolarGraph(6,3); G       # long time
-    Symplectic Polar Graph O(6, 3): Graph on 1120 vertices
-    sage: G.is_distance_regular(parameters=True)            # long time
-    ([39, 36, 27, None], [None, 1, 4, 13])
+        sage: G = graphs.SymplecticDualPolarGraph(6,3); G       # long time
+        Symplectic Polar Graph O(6, 3): Graph on 1120 vertices
+        sage: G.is_distance_regular(parameters=True)            # long time
+        ([39, 36, 27, None], [None, 1, 4, 13])
     """
     from sage.libs.gap.libgap import libgap
     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:

diff --git a/src/sage/graphs/generators/families.py b/src/sage/graphs/generators/families.py
index 0fadbbd..953b576 100644
--- a/src/sage/graphs/generators/families.py
+++ b/src/sage/graphs/generators/families.py
@@ -192,9 +192,9 @@ def BalancedTree(r, h):
 
     TESTS:
 
-     Normally we would only consider balanced trees whose root node
-     has degree `r \geq 2`, but the construction degenerates
-     gracefully::
+    Normally we would only consider balanced trees whose root node
+    has degree `r \geq 2`, but the construction degenerates
+    gracefully::
 
         sage: graphs.BalancedTree(1, 10)
         Balanced tree: Graph on 2 vertices

diff --git a/src/sage/graphs/generators/random.py b/src/sage/graphs/generators/random.py
index 01f9c13..246250d 100644
--- a/src/sage/graphs/generators/random.py
+++ b/src/sage/graphs/generators/random.py
@@ -749,7 +749,7 @@ def RandomToleranceGraph(n):
         sage: g.clique_number() == g.chromatic_number()
         True
 
-    TEST:
+    TEST::
 
         sage: g = graphs.RandomToleranceGraph(-2)
         Traceback (most recent call last):
diff --git a/src/sage/graphs/generators/smallgraphs.py b/src/sage/graphs/generators/smallgraphs.py
index 39ca04e..27e1124 100644
--- a/src/sage/graphs/generators/smallgraphs.py
+++ b/src/sage/graphs/generators/smallgraphs.py
@@ -1810,7 +1810,7 @@ def ChvatalGraph():
         2
         4
 
-    TEST:
+    TEST::
 
         sage: import networkx
         sage: G = graphs.ChvatalGraph()
@@ -2647,7 +2647,7 @@ def FruchtGraph():
         'KhCKM?_EGK?L'
         sage: (graphs.FruchtGraph()).show() # long time
 
-    TEST:
+    TEST::
 
         sage: import networkx
         sage: G = graphs.FruchtGraph()
@@ -2896,7 +2896,7 @@ def HeawoodGraph():
         'MhEGHC@AI?_PC@_G_'
         sage: (graphs.HeawoodGraph()).show() # long time
 
-    TEST:
+    TEST::
 
         sage: import networkx
         sage: G = graphs.HeawoodGraph()
@@ -3363,7 +3363,7 @@ def KrackhardtKiteGraph():
         sage: g = graphs.KrackhardtKiteGraph()
         sage: g.show() # long time
 
-    TEST:
+    TEST::
 
         sage: import networkx
         sage: G = graphs.KrackhardtKiteGraph()
diff --git a/src/sage/graphs/strongly_regular_db.pyx b/src/sage/graphs/strongly_regular_db.pyx
index 44a6640..f28248c 100644
--- a/src/sage/graphs/strongly_regular_db.pyx
+++ b/src/sage/graphs/strongly_regular_db.pyx
@@ -1518,7 +1518,7 @@ def strongly_regular_graph(int v,int k,int l,int mu=-1,bint existence=False):
         ...
         RuntimeError: Sage cannot figure out if a (1394,175,0,25)-strongly regular graph exists.
 
-    Test the Claw bound (see 3.D of [vLintBrouwer84]_):
+    Test the Claw bound (see 3.D of [vLintBrouwer84]_)::
 
         sage: graphs.strongly_regular_graph(2058,242,91,20,existence=True)
         False

You could also change "TEST:" to "TESTS:" throughout, but I don't really care much about that.

[sagetrac-git]

Changed commit from ab18d25 to 5450f1e

[sagetrac-git]

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

5450f1e

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

[sagetrac-git]

Changed commit from 5450f1e to 35a9b17

[sagetrac-git]

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 remote-tracking branch 'trac/public/18972' into seidelsw
25eec1b	uniformity, but no regularity
50a6efc	Merge branch 'seidelsw' into unitary
35a9b17	doctest fixes

[nathanncohen]

comment:19

Helloooooooo Dima,

Here is a 'first-pass' 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 this 6,4 by 4,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 case G?

• 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

[dimpase]

Author: Dima Pasechnik

[dimpase]

Reviewer: Nathann Cohen

[dimpase]

comment:21

Replying to @nathanncohen:

• 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 case G?

• 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 non-complicated objects,
like integers, this is as quick as native Python... (certainly, replacing libgap with gap there would lead to a huge performance hit).

[sagetrac-git]

Changed commit from 35a9b17 to acc985a

[sagetrac-git]

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

a729b27	the reviwer has cooked and has eaten my brain (removed stuff from designs.*)
1e8e0b4	shortening lines
fd9a689	Merge branch 'seidelsw' into unitary
acc985a	addressed reviewer's points

[nathanncohen]

comment:24

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 tested algorithm =='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 and SimplecticDualPolarGraph -- should we
  uniformize the Polar 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 beta

  sage -t --long families.py
       [250 tests, 19.95 s]
  

• Some graphs are not defined on a html page, and for those you link toward
  "Distance-regular 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

[dimpase]

comment:25

Replying to @nathanncohen:

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 tested algorithm =='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 and SimplecticDualPolarGraph -- should we
  uniformize the Polar 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
  "Distance-regular 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/Distance-regular_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.

[sagetrac-git]

Changed commit from acc985a to ee9c5d6

[sagetrac-git]

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

ee9c5d6

address #18997:24

[dimpase]

comment:27

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.

[nathanncohen]

comment:28

Hello,

yep, how about renaming SimplecticGraph to SimplecticPolarGraph and make SimplecticGraph a deprecated alias to SimplecticPolarGraph?

+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/Distance-regular_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

[vbraun]

Changed branch from u/dimpase/unitary to ee9c5d6