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.

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

Nathann

[dimpase]

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

[ncohen]

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]

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(q-1,q+1) and its dual, GQ(q+1,q-1).

[ncohen]

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]

Replying to ncohen:

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

[git]

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

​cd86455

addded dial polar graphs, libGAP way to construct them

[dimpase]

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.

[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

[git]

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

​d1f653e

added recongision of (dual) unitary graphs to the DB

[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

[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]

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]

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

src/sage/graphs/generators/families.py

@@ -2535 +2535 @@
 
     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 +2675 @@
 
     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:

src/sage/graphs/generators/families.py

@@ -192 +192 @@
 
     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

src/sage/graphs/generators/random.py

@@ -749 +749 @@
         sage: g.clique_number() == g.chromatic_number()
         True
 
-    TEST:
+    TEST::
 
         sage: g = graphs.RandomToleranceGraph(-2)
         Traceback (most recent call last):

src/sage/graphs/generators/smallgraphs.py

@@ -1810 +1810 @@
         2
         4
 
-    TEST:
+    TEST::
 
         sage: import networkx
         sage: G = graphs.ChvatalGraph()
@@ -2647 +2647 @@
         'KhCKM?_EGK?L'
         sage: (graphs.FruchtGraph()).show() # long time
 
-    TEST:
+    TEST::
 
         sage: import networkx
         sage: G = graphs.FruchtGraph()
@@ -2896 +2896 @@
         'MhEGHC@AI?_PC@_G_'
         sage: (graphs.HeawoodGraph()).show() # long time
 
-    TEST:
+    TEST::
 
         sage: import networkx
         sage: G = graphs.HeawoodGraph()
@@ -3363 +3363 @@
         sage: g = graphs.KrackhardtKiteGraph()
         sage: g.show() # long time
 
-    TEST:
+    TEST::
 
         sage: import networkx
         sage: G = graphs.KrackhardtKiteGraph()

src/sage/graphs/strongly_regular_db.pyx

@@ -1518 +1518 @@
         ...
         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.

[git]

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

​5450f1e

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

[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

[ncohen]

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]

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

[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

[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 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]

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

[git]

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

​ee9c5d6

address #18997:24

[dimpase]

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.

[ncohen]

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