Opened 18 months ago
Closed 13 months ago
#30343 closed enhancement (fixed)
Graphs: pointgraph of generalised polygons
Reported by:  ghIvoMaffei  Owned by:  

Priority:  major  Milestone:  sage9.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: 
Description
Added constructions to obtain distanceregular graphs from generalised polygons.
Change History (42)
comment:1 Changed 18 months ago by
 Branch set to public/graphs/30343
 Cc dimpase added
 Commit set to 66d7fa350de80a77ce78922f669bfa68d3bb255e
 Status changed from new to needs_review
comment:2 followup: ↓ 3 Changed 18 months ago by
should I review this before #29886 is fixed (or removed from the deps chain here)?
comment:3 in reply to: ↑ 2 Changed 18 months ago by
 Status changed from needs_review to needs_work
comment:4 Changed 18 months ago by
 Commit changed from 66d7fa350de80a77ce78922f669bfa68d3bb255e to 35a457ea490183488b454a72157b8d2b2e75c8c2
Branch pushed to git repo; I updated commit sha1. New commits:
9a3e609  reverted changes to matrix_space.py

e78c2d0  removed dependecies from symmetric generator

38577a8  fixed bug with matrix generation; added meataxe flag to tests

d2ff33f  Merge branch 30312 into 30329 (removed 29886)

7753054  Merge branch 30329 into 30337

35a457e  Merge branch 30337 into 30343

comment:5 Changed 17 months ago by
 Commit changed from 35a457ea490183488b454a72157b8d2b2e75c8c2 to 536785851ff1731af9f7aa4539554c2a1ef8d633
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
d76ba80  Merge branch '30337' into 30343

a0463d5  fix docsrtings; renamed module

5d16394  renamed in design_catalog

e6ff3fa  Merge branch 't/30223' into t/30337

3e1df8c  added const to half cube

0d92ec4  Merge branch 't/30329' into t/30337

ac3ed1a  Merge branch 't/30337' into t/30343

376d459  convert matrices in bilinearFormsGraph to integers to lower memory requirements

11d9953  Merge branch 't/30337' into t/30343

5367858  some code formatting

comment:6 Changed 17 months ago by
 Status changed from needs_work to needs_review
comment:7 followup: ↓ 8 Changed 17 months ago by
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 17 months ago by
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 2what'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 17 months ago by
 Commit changed from 536785851ff1731af9f7aa4539554c2a1ef8d633 to d127e7a81c27aaca23b24334277130b2eae7530b
Branch pushed to git repo; I updated commit sha1. New commits:
d127e7a  fix typos, English, cut/paste errors

comment:10 Changed 17 months ago by
 Reviewers set to Dima Pasechnik
 Status changed from needs_review to positive_review
OK, looks good.
comment:11 Changed 16 months ago by
 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:
4bcdb3c  typos and TeX fixes

feabf4f  better index section, uniform naming

8c12a8f  Merge branch 't/30329' into t/30337

1fdcad9  fixed typo

c97bda5  Merge branch 't/30329' into t/30337

3024980  faster implementation of HalfCube

898fbee  added positions to HalfCube

d9c9149  Merge branch 't/30509' into t/30337

3449361  Merge branch 9.2.beta12 into t/30337

b99474b  Merge branch 't/30337' into t/30343

comment:12 Changed 16 months ago by
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 16 months ago by
 Commit changed from b99474be2280fb282eca5f47f42a2ede62192dbb to 7d17b7d3832609d0d34a7f3e00818cba7225f964
Branch pushed to git repo; I updated commit sha1. New commits:
7d17b7d  removed blank lines

comment:14 Changed 16 months ago by
The patchbot still complains about the docstrings, but I can't see any issue in the built html.
comment:15 followup: ↓ 20 Changed 16 months ago by
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.
comment:16 Changed 16 months ago by
 Commit changed from 7d17b7d3832609d0d34a7f3e00818cba7225f964 to b4a3c1852bb0eda6ca682ec784a9fdad555b414e
Branch pushed to git repo; I updated commit sha1. New commits:
b4a3c18  sagenb is gone

comment:17 Changed 16 months ago by
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 16 months ago by
yes, both are bugs. Probably many things are broken, even if only because they depend on sagenb
comment:19 Changed 16 months ago by
 Commit changed from b4a3c1852bb0eda6ca682ec784a9fdad555b414e to d152871f354a7b8b4d0d5c77a4c068d8c1fe847a
Branch pushed to git repo; I updated commit sha1. New commits:
d152871  remote extra spaces

comment:20 in reply to: ↑ 15 Changed 16 months ago by
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 misreporting 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:22 Changed 16 months ago by
 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/buildbotsage/slave/sage_git/build/local/lib/python3.8/sitepackages/sage/doctest/forker.py", line 720, in _run self.compile_and_execute(example, compiler, test.globs) File "/Users/buildbotsage/slave/sage_git/build/local/lib/python3.8/sitepackages/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) <ipythoninput16dbe64b36795> in <module> > 1 graphs.GeneralisedHexagonGraph(Integer(3), Integer(3)) ~/slave/sage_git/build/local/lib/python3.8/sitepackages/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/sitepackages/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 16 months ago by
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?
comment:24 Changed 16 months ago by
 Commit changed from d152871f354a7b8b4d0d5c77a4c068d8c1fe847a to 8c81bdc38c27128a923f708810f18283b975e36d
Branch pushed to git repo; I updated commit sha1. New commits:
8c81bdc  typo in the graph name string

comment:25 followup: ↓ 26 Changed 16 months ago by
It might be one of the dependent tickets...
comment:26 in reply to: ↑ 25 Changed 16 months ago by
 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 masstest 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 16 months ago by
 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 16 months ago by
sage: libgap.AtlasGroup("G2(3)") fail
comment:29 Changed 16 months ago by
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 16 months ago by
The test is marked with gap_packages. Is the syntax wrong or is an issue with the testing?
comment:31 Changed 15 months ago by
 Milestone changed from sage9.2 to sage9.3
comment:32 Changed 13 months ago by
This ticket seems to be blocking a number of positively reviewed tickets that have it as a dependency
comment:33 Changed 13 months ago by
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 202012121037040c0dc92b. 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 warnlong 203.5 randomseed=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 sagelocation, probably because a new package was installed. Cleaning up, do not interrupt this. Done cleaning. Running doctests with ID 20201212114044e3fae3fc. 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 warnlong 203.5 randomseed=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 13 months ago by
maybe there is a line missing the tag ?
+ sage: G = graphs.GeneralisedHexagonGraph(3, 3)
comment:35 Changed 13 months ago by
Right, may be we should tag all the tests of these methods with gap_packages
, even the trivial ones
comment:36 Changed 13 months ago by
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 13 months ago by
 Commit changed from 8c81bdc38c27128a923f708810f18283b975e36d to 1ade78be95f0ffe4885917bc9ce36196d2b6d5e6
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
eeef08b  added generalised polygons and related private functions

a90bc7c  fix doctests

1aa0bbf  some code formatting

19ada2c  fix typos, English, cut/paste errors

74e52dd  removed blank lines

126b2cb  sagenb is gone

47b0aba  remote extra spaces

ad0c3bb  typo in the graph name string

1ade78b  missing #optional tag added

comment:38 Changed 13 months ago by
 Status changed from needs_work to needs_review
rebased and added a missing tag in https://git.sagemath.org/sage.git/commit/?id=1ade78be95f0ffe4885917bc9ce36196d2b6d5e6
comment:39 Changed 13 months ago by
you must also tag the 2 lines after in the test. Depends on the result.
comment:40 Changed 13 months ago by
 Commit changed from 1ade78be95f0ffe4885917bc9ce36196d2b6d5e6 to a176e0b0263fc580e1cdcb438c1fca32c849cc75
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
a176e0b  missing #optional tag added

comment:41 Changed 13 months ago by
 Status changed from needs_review to positive_review
OK, it all works now.
comment:42 Changed 13 months ago by
 Branch changed from public/graphs/30343 to a176e0b0263fc580e1cdcb438c1fca32c849cc75
 Resolution set to fixed
 Status changed from positive_review to closed
Last 10 new commits:
added file
added code
cleaned up code; added docstring; added tests
removed gap int; fixed some docstrings
added references
Merge 30223 into drg_fam2
added code to generate drg from GQs
fix doctests; added references
added generalised polygons and related private functions
fix doctests