Unitary and symplectic (dual) polar graphs

dimpase commented 9 years ago

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 commented 9 years ago

Dependencies: #18972

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago

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 commented 9 years ago

Description changed:

--- 
+++ 
@@ -1,2 +1,2 @@
-implement the classical unitary polar graphs `U(n,q)`, see
+implement the classical unitary (reps. symplectic) polar graphs `U(n,q)` (resp. `Sp(2d,q)`), see
 http://www.win.tue.nl/~aeb/graphs/srghub.html

dimpase commented 9 years ago

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

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago

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 commented 9 years ago

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(q2,q3). So we will need GQ(q3,q2) - I can do this on this ticket too, as this is essentially a small modification:

I build points and lines of the GQ(q2,q3), 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(q3,q2).

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

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago

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 commented 9 years ago

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 971476d to cd86455

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

cd86455 addded dial polar graphs, libGAP way to construct them

dimpase commented 9 years ago

Description changed:

--- 
+++ 
@@ -1,2 +1,2 @@
-implement the classical unitary (reps. symplectic) polar graphs `U(n,q)` (resp. `Sp(2d,q)`), see
-http://www.win.tue.nl/~aeb/graphs/srghub.html
+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).

dimpase commented 9 years ago

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from cd86455 to 4af0f07

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 4af0f07 to d1f653e

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

d1f653e added recongision of (dual) unitary graphs to the DB

dimpase commented 9 years ago

Description changed:

--- 
+++ 
@@ -1,2 +1,3 @@
 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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from d1f653e to 1765846

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 1765846 to ab18d25

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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 commented 9 years ago

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 commented 9 years ago

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from ab18d25 to 5450f1e

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 5450f1e to 35a9b17

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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`

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago

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 commented 9 years ago

Author: Dima Pasechnik

dimpase commented 9 years ago

Reviewer: Nathann Cohen

dimpase commented 9 years ago

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 35a9b17 to acc985a

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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`

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago

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 commented 9 years ago

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from acc985a to ee9c5d6

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

ee9c5d6 address #18997:24

dimpase commented 9 years ago

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.

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago

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 commented 9 years ago

Changed branch from u/dimpase/unitary to ee9c5d6

sagemath / sage

Unitary and symplectic (dual) polar graphs #18997