#30343 closed enhancement (fixed)

Graphs: point-graph of generalised polygons

Reported by: gh-Ivo-Maffei Owned by:
Priority: major Milestone: sage-9.3
Component: graph theory Keywords:
Cc: dimpase Merged in:
Authors: Ivo Maffei Reviewers: Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: a176e0b (Commits, GitHub, GitLab) Commit: a176e0b0263fc580e1cdcb438c1fca32c849cc75
Dependencies: #30337 Stopgaps:

Status badges

Description

Added constructions to obtain distance-regular graphs from generalised polygons.

Change History (42)

comment:1 Changed 16 months ago by gh-Ivo-Maffei

  • Branch set to public/graphs/30343
  • Cc dimpase added
  • Commit set to 66d7fa350de80a77ce78922f669bfa68d3bb255e
  • Status changed from new to needs_review

Last 10 new commits:

9991f4fadded file
931859badded code
7555255cleaned up code; added docstring; added tests
0e82896removed gap int; fixed some docstrings
ee0e18fadded references
51517feMerge 30223 into drg_fam2
190dd4badded code to generate drg from GQs
b98b5e0fix doctests; added references
fb83a38added generalised polygons and related private functions
66d7fa3fix doctests

comment:2 follow-up: Changed 16 months ago by dimpase

should I review this before #29886 is fixed (or removed from the deps chain here)?

comment:3 in reply to: ↑ 2 Changed 16 months ago by gh-Ivo-Maffei

  • Status changed from needs_review to needs_work

Replying to dimpase:

should I review this before #29886 is fixed (or removed from the deps chain here)?

Oops, I rushed this out... I think I'll remove #29886 from the dependency chain and update all tickets. Once we decide on something for #29886, I'll make a quick patch.

comment:4 Changed 16 months ago by git

  • Commit changed from 66d7fa350de80a77ce78922f669bfa68d3bb255e to 35a457ea490183488b454a72157b8d2b2e75c8c2

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

9a3e609reverted changes to matrix_space.py
e78c2d0removed dependecies from symmetric generator
38577a8fixed bug with matrix generation; added meataxe flag to tests
d2ff33fMerge branch 30312 into 30329 (removed 29886)
7753054Merge branch 30329 into 30337
35a457eMerge branch 30337 into 30343

comment:5 Changed 15 months ago by git

  • Commit changed from 35a457ea490183488b454a72157b8d2b2e75c8c2 to 536785851ff1731af9f7aa4539554c2a1ef8d633

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

d76ba80Merge branch '30337' into 30343
a0463d5fix docsrtings; renamed module
5d16394renamed in design_catalog
e6ff3faMerge branch 't/30223' into t/30337
3e1df8cadded const to half cube
0d92ec4Merge branch 't/30329' into t/30337
ac3ed1aMerge branch 't/30337' into t/30343
376d459convert matrices in bilinearFormsGraph to integers to lower memory requirements
11d9953Merge branch 't/30337' into t/30343
5367858some code formatting

comment:6 Changed 15 months ago by gh-Ivo-Maffei

  • Status changed from needs_work to needs_review

comment:7 follow-up: Changed 15 months ago by dimpase

this is incorrect:

+        ValueError: generalised octagons of order (q, q^2) exist only for q odd powers of 2

what's correct that only for these values of q a construction is known.

Please also check for similar incorrect things elsewhere in this code.

comment:8 in reply to: ↑ 7 Changed 15 months ago by gh-Ivo-Maffei

Replying to dimpase:

I'm apologise for the late reply.

this is incorrect:

+        ValueError: generalised octagons of order (q, q^2) exist only for q odd powers of 2

what's correct that only for these values of q a construction is known.

With the latest commit (5367858) I changed all such error messages. Now the above should read:

ValueError(("generalised octagons of order (q, q^2) "
            "are known only for q odd powers of 2"))

comment:9 Changed 15 months ago by git

  • Commit changed from 536785851ff1731af9f7aa4539554c2a1ef8d633 to d127e7a81c27aaca23b24334277130b2eae7530b

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

d127e7afix typos, English, cut/paste errors

comment:10 Changed 15 months ago by dimpase

  • Reviewers set to Dima Pasechnik
  • Status changed from needs_review to positive_review

OK, looks good.

comment:11 Changed 15 months ago by git

  • Commit changed from d127e7a81c27aaca23b24334277130b2eae7530b to b99474be2280fb282eca5f47f42a2ede62192dbb
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. Last 10 new commits:

4bcdb3ctypos and TeX fixes
feabf4fbetter index section, uniform naming
8c12a8fMerge branch 't/30329' into t/30337
1fdcad9fixed typo
c97bda5Merge branch 't/30329' into t/30337
3024980faster implementation of HalfCube
898fbeeadded positions to HalfCube
d9c9149Merge branch 't/30509' into t/30337
3449361Merge branch 9.2.beta12 into t/30337
b99474bMerge branch 't/30337' into t/30343

comment:12 Changed 15 months ago by gh-Ivo-Maffei

I merged the last beta and the last changes to #30337. The patch box had a weird error with the documentation of UstimenkoGraph. I couldn't understand what was wrong so I'll check if the issue is still there after this merging.

comment:13 Changed 15 months ago by git

  • Commit changed from b99474be2280fb282eca5f47f42a2ede62192dbb to 7d17b7d3832609d0d34a7f3e00818cba7225f964

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

7d17b7dremoved blank lines

comment:14 Changed 15 months ago by gh-Ivo-Maffei

The patchbot still complains about the docstrings, but I can't see any issue in the built html.

comment:15 follow-up: Changed 15 months ago by chapoton

There should be no space before colons

++    while edges :
++            try :

This is a typography rule.

And importing something from sagenb does not look right, as sagenb is plain dead.

EDIT: you can safely forget about the patchbot complaints in graph_database.py, even if they point to real problems.

Last edited 15 months ago by chapoton (previous) (diff)

comment:16 Changed 15 months ago by git

  • Commit changed from 7d17b7d3832609d0d34a7f3e00818cba7225f964 to b4a3c1852bb0eda6ca682ec784a9fdad555b414e

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

b4a3c18sagenb is gone

comment:17 Changed 15 months ago by dimpase

this fixes the 2nd of the pyflakes complaints:

src/sage/graphs/graph_database.py:421:47 undefined name 'subgraphs_to_data'
src/sage/graphs/graph_database.py:945:9 'sagenb.notebook.interact.input_grid' imported but unused

the 1st looks like a bug, just never tested that code.

comment:18 Changed 15 months ago by chapoton

yes, both are bugs. Probably many things are broken, even if only because they depend on sagenb

comment:19 Changed 15 months ago by git

  • Commit changed from b4a3c1852bb0eda6ca682ec784a9fdad555b414e to d152871f354a7b8b4d0d5c77a4c068d8c1fe847a

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

d152871remote extra spaces

comment:20 in reply to: ↑ 15 Changed 15 months ago by dimpase

Replying to chapoton:

There should be no space before colons

++    while edges :
++            try :

This is a typography rule.

OK, thanks, that's fixed. The bot is mis-reporting the locations where these are, though.

EDIT: you can safely forget about the patchbot complaints in graph_database.py, even if they point to real problems.

yeah, that is a legacy code...

comment:21 Changed 15 months ago by dimpase

  • Status changed from needs_review to positive_review

ok

comment:22 Changed 14 months ago by vbraun

  • Status changed from positive_review to needs_work

On some but not all machines I'm getting

**********************************************************************
File "src/sage/graphs/generators/distance_regular.pyx", line 1714, in sage.graphs.generators.distance_regular._line_graph_generalised_polygon
Failed example:
    G = graphs.GeneralisedHexagonGraph(3, 3)
Exception raised:
    Traceback (most recent call last):
      File "/Users/buildbot-sage/slave/sage_git/build/local/lib/python3.8/site-packages/sage/doctest/forker.py", line 720, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/buildbot-sage/slave/sage_git/build/local/lib/python3.8/site-packages/sage/doctest/forker.py", line 1145, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.generators.distance_regular._line_graph_generalised_polygon[4]>", line 1, in <module>
        G = graphs.GeneralisedHexagonGraph(Integer(3), Integer(3))
      File "sage/graphs/generators/distance_regular.pyx", line 1587, in sage.graphs.generators.distance_regular.GeneralisedHexagonGraph (build/cythonized/sage/graphs/generators/distance_regular.c:25912)
        orb = libgap.Orbit(matrixRep, e1, libgap.OnLines)
      File "sage/libs/gap/element.pyx", line 2525, in sage.libs.gap.element.GapElement_Function.__call__ (build/cythonized/sage/libs/gap/element.c:19781)
        sig_on()
    sage.libs.gap.util.GAPError: Error, no method found! Error, no 1st choice method found for `GeneratorsOfMagmaWithInverses' on 1 arguments
    The 1st argument is 'fail' which might point to an earlier problem
**********************************************************************

Same when running manually:

sage: graphs.GeneralisedHexagonGraph(3, 3) 
....:                                                                                                                                                            
---------------------------------------------------------------------------
GAPError                                  Traceback (most recent call last)
<ipython-input-1-6dbe64b36795> in <module>
----> 1 graphs.GeneralisedHexagonGraph(Integer(3), Integer(3))

~/slave/sage_git/build/local/lib/python3.8/site-packages/sage/graphs/generators/distance_regular.pyx in sage.graphs.generators.distance_regular.GeneralisedHexagonGraph (build/cythonized/sage/graphs/generators/distance_regular.c:25912)()
   1585             matrixRep = libgap.AtlasGroup("G2(3)", libgap.Position, 7)
   1586             e1 = vector(GF(3), [1, 0, 0, 0, 0, 0, 0])
-> 1587             orb = libgap.Orbit(matrixRep, e1, libgap.OnLines)
   1588             group = libgap.Action(matrixRep, orb, libgap.OnLines)
   1589 

~/slave/sage_git/build/local/lib/python3.8/site-packages/sage/libs/gap/element.pyx in sage.libs.gap.element.GapElement_Function.__call__ (build/cythonized/sage/libs/gap/element.c:19781)()
   2523         try:
   2524             sig_GAP_Enter()
-> 2525             sig_on()
   2526             if n == 0:
   2527                 result = CALL_0ARGS(self.value)

GAPError: Error, no method found! Error, no 1st choice method found for `GeneratorsOfMagmaWithInverses' on 1 arguments
The 1st argument is 'fail' which might point to an earlier problem
sage:                                                                                                                                                            
Exiting Sage (CPU time 0m1.43s, Wall time 0m15.41s).

comment:23 Changed 14 months ago by dimpase

I cannot reproduce this (neither with python 3.7 or 3.8, neither with the currenly Sage's GAP, nor with GAP 4.11 update, with or without gap_packages installed) - do you actually have working libgap on these machines?

Last edited 14 months ago by dimpase (previous) (diff)

comment:24 Changed 14 months ago by git

  • Commit changed from d152871f354a7b8b4d0d5c77a4c068d8c1fe847a to 8c81bdc38c27128a923f708810f18283b975e36d

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

8c81bdctypo in the graph name string

comment:25 follow-up: Changed 14 months ago by vbraun

It might be one of the dependent tickets...

comment:26 in reply to: ↑ 25 Changed 14 months ago by dimpase

  • Status changed from needs_work to positive_review

Replying to vbraun:

It might be one of the dependent tickets...

Do you mean to say you mass-test some more tickets along with this one and attribute the error you see to this one?

I'm setting this to positive review, as I don't see what work can be done here.

comment:27 Changed 14 months ago by vbraun

  • Status changed from positive_review to needs_work

Its definitely this ticket thats failing. Possibly running out of memory, prematurely garbage collecting, or generator choice...

comment:28 Changed 14 months ago by vbraun

sage: libgap.AtlasGroup("G2(3)")                                                                                                                   
fail
Last edited 14 months ago by vbraun (previous) (diff)

comment:29 Changed 14 months ago by vbraun

After installing gap_packages:

sage: libgap.AtlasGroup("G2(3)")                                                                                                                   
<matrix group of size 4245696 with 2 generators>
sage: graphs.GeneralisedHexagonGraph(3, 3)                                                                                                         
Generalised hexagon of order (3, 3): Graph on 364 vertices

comment:30 Changed 14 months ago by gh-Ivo-Maffei

The test is marked with gap_packages. Is the syntax wrong or is an issue with the testing?

comment:31 Changed 13 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:32 Changed 12 months ago by mkoeppe

This ticket seems to be blocking a number of positively reviewed tickets that have it as a dependency

comment:33 Changed 12 months ago by dcoudert

I tried this ticket before and after installing gap_packages and I measured the memory used while testing the ticket. For me the ticket looks ok, so I don't know why the some bots are failing.

sapristi:sage dcoudert$ /usr/bin/time -l ./sage -t --long src/sage/graphs/generators/distance_regular.pyx
Running doctests with ID 2020-12-12-10-37-04-0c0dc92b.
Git branch: HEAD
Using --optional=bliss,build,dochtml,homebrew,pip,python_igraph,sage,sage_numerical_backends_cplex,sage_spkg,tdlib,texttable
Doctesting 1 file.
sage -t --long --warn-long 203.5 --random-seed=0 src/sage/graphs/generators/distance_regular.pyx
    [129 tests, 178.33 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 178.5 seconds
    cpu time: 177.3 seconds
    cumulative wall time: 178.3 seconds
      193.93 real       179.36 user         5.70 sys
 433836032  maximum resident set size
         0  average shared memory size
         0  average unshared data size
         0  average unshared stack size
    472070  page reclaims
      6723  page faults
         0  swaps
         0  block input operations
         0  block output operations
         0  messages sent
         0  messages received
       156  signals received
      5180  voluntary context switches
     93942  involuntary context switches
sapristi:sage dcoudert$ /usr/bin/time -l ./sage -t --long src/sage/graphs/generators/distance_regular.pyx
Forcing sage-location, probably because a new package was installed.
Cleaning up, do not interrupt this.
Done cleaning.
Running doctests with ID 2020-12-12-11-40-44-e3fae3fc.
Git branch: develop
Using --optional=bliss,build,dochtml,gap_packages,homebrew,libsemigroups,pip,python_igraph,sage,sage_numerical_backends_cplex,sage_spkg,tdlib,texttable
Doctesting 1 file.
sage -t --long --warn-long 203.5 --random-seed=0 src/sage/graphs/generators/distance_regular.pyx
    [105 tests, 195.51 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 195.6 seconds
    cpu time: 186.3 seconds
    cumulative wall time: 195.5 seconds
      207.59 real       187.34 user         5.13 sys
 450232320  maximum resident set size
         0  average shared memory size
         0  average unshared data size
         0  average unshared stack size
    467254  page reclaims
     13861  page faults
         0  swaps
         0  block input operations
         0  block output operations
         0  messages sent
         0  messages received
       170  signals received
      7876  voluntary context switches
    189530  involuntary context switches

comment:34 Changed 12 months ago by chapoton

maybe there is a line missing the tag ?

+         sage: G = graphs.GeneralisedHexagonGraph(3, 3)

comment:35 Changed 12 months ago by dcoudert

Right, may be we should tag all the tests of these methods with gap_packages, even the trivial ones

comment:36 Changed 12 months ago by dimpase

GAP is used here. As GAP has been finally updated to 4.11 in the latest beta, let's retest this ticket and see if it works.

comment:37 Changed 12 months ago by git

  • Commit changed from 8c81bdc38c27128a923f708810f18283b975e36d to 1ade78be95f0ffe4885917bc9ce36196d2b6d5e6

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

eeef08badded generalised polygons and related private functions
a90bc7cfix doctests
1aa0bbfsome code formatting
19ada2cfix typos, English, cut/paste errors
74e52ddremoved blank lines
126b2cbsagenb is gone
47b0abaremote extra spaces
ad0c3bbtypo in the graph name string
1ade78bmissing #optional tag added

comment:38 Changed 12 months ago by dimpase

  • Status changed from needs_work to needs_review

comment:39 Changed 12 months ago by dcoudert

you must also tag the 2 lines after in the test. Depends on the result.

comment:40 Changed 12 months ago by git

  • Commit changed from 1ade78be95f0ffe4885917bc9ce36196d2b6d5e6 to a176e0b0263fc580e1cdcb438c1fca32c849cc75

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

a176e0bmissing #optional tag added

comment:41 Changed 12 months ago by dimpase

  • Status changed from needs_review to positive_review

OK, it all works now.

comment:42 Changed 11 months ago by vbraun

  • Branch changed from public/graphs/30343 to a176e0b0263fc580e1cdcb438c1fca32c849cc75
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.