Opened 6 years ago

Closed 6 years ago

#18997 closed enhancement (fixed)

Unitary and symplectic (dual) polar graphs

Reported by: dimpase Owned by:
Priority: major Milestone: sage-6.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:

Status badges

Description (last modified by 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.

Change History (30)

comment:1 Changed 6 years ago by dimpase

  • Dependencies set to #18972

comment:2 follow-up: Changed 6 years ago by 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

comment:3 in reply to: ↑ 2 Changed 6 years ago by dimpase

  • 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 follow-up: Changed 6 years ago by 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

comment:5 in reply to: ↑ 4 ; follow-up: Changed 6 years ago by 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).

comment:6 in reply to: ↑ 5 ; follow-up: Changed 6 years ago by 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.

comment:7 in reply to: ↑ 6 Changed 6 years ago by 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...

comment:8 Changed 6 years ago by git

  • Commit changed from 971476d1d7bb4a32cacf70c1d8de478295423aa9 to cd864554e81ada74a00759e40ec6edd7bac609ca

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

cd86455addded dial polar graphs, libGAP way to construct them

comment:9 Changed 6 years ago by dimpase

  • 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 6 years ago by git

  • Commit changed from cd864554e81ada74a00759e40ec6edd7bac609ca to 4af0f07d4928e2d7dba8d8734abc3229ce245201

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

19b40d9trac #19019: Sort the list of SRGs
778556fMerge remote-tracking branch 'trac/u/ncohen/19019' into t19019
6ed716dadded a doctest
cb0b3fbMerge branch 'reg_symm_hadamard' into t19019
2c4a38aMerge branch '#19019' into seidelsw
8601814removed duplicate [BH12]
6ba4533docs for two-graphs class
afbf2cbdocs changes; hyperlinks etc
86bf5b8remove twographs.* from global namespace, added to design_catalog
4af0f07Merge branch 'seidelsw' into unitary

comment:11 Changed 6 years ago by git

  • Commit changed from 4af0f07d4928e2d7dba8d8734abc3229ce245201 to d1f653efccf25283d1102bf5372ace78d3598db1

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

d1f653eadded recongision of (dual) unitary graphs to the DB

comment:12 Changed 6 years ago by dimpase

  • Description modified (diff)
  • Status changed from new to needs_review

comment:13 Changed 6 years ago by git

  • Commit changed from d1f653efccf25283d1102bf5372ace78d3598db1 to 1765846d94a8f0fdac54fa922be881c2f50d0c59

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

2fae2fcfixed docs for twograph_descendant, adjusted the Graph methods indices
799a2bfspeeding up twograph_descendant
b9fd7afremoved spaces and added r's
68c0eddmoved twograph_descendant to twographs.py, and docs improved
3fc3bb2Merge branch 'seidelsw' into unitary
1765846fixing sphynx docbuild

comment:14 Changed 6 years ago by git

  • Commit changed from 1765846d94a8f0fdac54fa922be881c2f50d0c59 to ab18d25ae8046bb3091b7741ca930f60100b807e

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

6bc5cbdnext round of fixes, cf #18972:75
d9b098atrac #18972: Reviewer's commit
e7022f3trac #18972: inplace seidel_switching
f4add31Merge branch 'develop' into seidelsw
4f7e3c91st portion of fixes for #18972:81
a336241The rest of fixes for #18972:81:
ab18d25merge Merge branch 'unitary' into the latest #18972

comment:15 Changed 6 years ago by 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.

comment:16 Changed 6 years ago by jhpalmieri

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): 
    25352535
    25362536    TESTS::
    25372537
    2538     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
     2538        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
    25432543    """
    25442544    from sage.libs.gap.libgap import libgap
    25452545    from itertools import combinations
    def SymplecticDualPolarGraph(m, q): 
    26752675
    26762676    EXAMPLES::
    26772677
    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])
     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])
    26822682
    26832683    TESTS::
    26842684
    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])
     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])
    26892689    """
    26902690    from sage.libs.gap.libgap import libgap
    26912691    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): 
    192192
    193193    TESTS:
    194194
    195      Normally we would only consider balanced trees whose root node
    196      has degree `r \geq 2`, but the construction degenerates
    197      gracefully::
     195    Normally we would only consider balanced trees whose root node
     196    has degree `r \geq 2`, but the construction degenerates
     197    gracefully::
    198198
    199199        sage: graphs.BalancedTree(1, 10)
    200200        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): 
    749749        sage: g.clique_number() == g.chromatic_number()
    750750        True
    751751
    752     TEST:
     752    TEST::
    753753
    754754        sage: g = graphs.RandomToleranceGraph(-2)
    755755        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(): 
    18101810        2
    18111811        4
    18121812
    1813     TEST:
     1813    TEST::
    18141814
    18151815        sage: import networkx
    18161816        sage: G = graphs.ChvatalGraph()
    def FruchtGraph(): 
    26472647        'KhCKM?_EGK?L'
    26482648        sage: (graphs.FruchtGraph()).show() # long time
    26492649
    2650     TEST:
     2650    TEST::
    26512651
    26522652        sage: import networkx
    26532653        sage: G = graphs.FruchtGraph()
    def HeawoodGraph(): 
    28962896        'MhEGHC@AI?_PC@_G_'
    28972897        sage: (graphs.HeawoodGraph()).show() # long time
    28982898
    2899     TEST:
     2899    TEST::
    29002900
    29012901        sage: import networkx
    29022902        sage: G = graphs.HeawoodGraph()
    def KrackhardtKiteGraph(): 
    33633363        sage: g = graphs.KrackhardtKiteGraph()
    33643364        sage: g.show() # long time
    33653365
    3366     TEST:
     3366    TEST::
    33673367
    33683368        sage: import networkx
    33693369        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): 
    15181518        ...
    15191519        RuntimeError: Sage cannot figure out if a (1394,175,0,25)-strongly regular graph exists.
    15201520
    1521     Test the Claw bound (see 3.D of [vLintBrouwer84]_):
     1521    Test the Claw bound (see 3.D of [vLintBrouwer84]_)::
    15221522
    15231523        sage: graphs.strongly_regular_graph(2058,242,91,20,existence=True)
    15241524        False

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

comment:17 Changed 6 years ago by git

  • Commit changed from ab18d25ae8046bb3091b7741ca930f60100b807e to 5450f1e1e8c20fe86d25e001c495bbcd3f5719c0

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

5450f1edoctest fixes from John Palmieri: Thanks John! They help!

comment:18 Changed 6 years ago by git

  • Commit changed from 5450f1e1e8c20fe86d25e001c495bbcd3f5719c0 to 35a9b1752da8eadddc03b68e584ceffa9e14bc93

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

3350efcinplace has arrived here too
4e077dbmaking internet and gap_packages tests optional
0d20a94inplace has arrived here too
7d15addtrac #18972: Speedup is_twograph
7a690detrac #18972: speedup Graph.twograph
4e3a0eaMerge branch 'public/18972' of git://trac.sagemath.org/sage into HEAD
95fe0f2Merge remote-tracking branch 'trac/public/18972' into seidelsw
25eec1buniformity, but no regularity
50a6efcMerge branch 'seidelsw' into unitary
35a9b17doctest fixes

comment:19 follow-up: Changed 6 years ago by ncohen

  • Status changed from needs_review to needs_work

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

comment:20 Changed 6 years ago by dimpase

  • Authors set to Dima Pasechnik
  • Reviewers set to Nathann Cohen

comment:21 in reply to: ↑ 19 Changed 6 years ago by 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).

comment:22 Changed 6 years ago by git

  • Commit changed from 35a9b1752da8eadddc03b68e584ceffa9e14bc93 to acc985a045f02a1c796accd9a029ae809a0a92fd

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

a729b27the reviwer has cooked and has eaten my brain (removed stuff from designs.*)
1e8e0b4shortening lines
fd9a689Merge branch 'seidelsw' into unitary
acc985aaddressed reviewer's points

comment:23 Changed 6 years ago by dimpase

  • Status changed from needs_work to needs_review

comment:24 follow-up: Changed 6 years ago by ncohen

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

Thank you *very* much for this code.

Nathann

comment:25 in reply to: ↑ 24 ; follow-up: Changed 6 years ago by 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.

this would be even more meaningful with a new module.

comment:26 Changed 6 years ago by git

  • Commit changed from acc985a045f02a1c796accd9a029ae809a0a92fd to ee9c5d61e1c3976fe87cf01ddc8315b33238cdd6

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

ee9c5d6address #18997:24

comment:27 Changed 6 years ago by dimpase

  • 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 6 years ago by 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

comment:29 Changed 6 years ago by ncohen

  • Status changed from needs_review to positive_review

comment:30 Changed 6 years ago by vbraun

  • Branch changed from u/dimpase/unitary to ee9c5d61e1c3976fe87cf01ddc8315b33238cdd6
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.