Opened 22 months ago
Closed 20 months ago
#30337 closed enhancement (fixed)
Graphs: obtain distanceregular graphs from generalised quadrangles
Reported by:  ghIvoMaffei  Owned by:  

Priority:  major  Milestone:  sage9.2 
Component:  graph theory  Keywords:  
Cc:  dimpase  Merged in:  
Authors:  Ivo Maffei  Reviewers:  Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  3449361 (Commits, GitHub, GitLab)  Commit:  344936159a22dcfe08d64c516496bf688cba49e1 
Dependencies:  #30223, #30509  Stopgaps: 
Description
Added code that constructs distanceregular graphs from generalised quadrangles with spread. Also added a function that checks whether an distanceregular graph can be built using the method above.
Change History (35)
comment:1 Changed 22 months ago by
 Branch set to public/graphs/30337
 Cc dimpase added
 Commit set to b98b5e0161582c1a0ebe5593bf00258dceebd7bb
 Status changed from new to needs_review
comment:2 Changed 22 months ago by
 Commit changed from b98b5e0161582c1a0ebe5593bf00258dceebd7bb to 7753054764ee230c3dd584e31c2e195408733701
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

comment:3 Changed 21 months ago by
it seems that the latest changes should be merged in.
comment:4 Changed 21 months ago by
 Commit changed from 7753054764ee230c3dd584e31c2e195408733701 to 0d92ec49345b05ab42118406755808d60a06d79a
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
48395a1  use integer vectors in bilinear form to represents matrices

339b4f5  fix docstrings

c081dde  Merge branch '30312' into 30329

ac45a62  some code formatting and docstrings

e96c7c7  Merge branch '30329' into 30337

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

comment:5 Changed 21 months ago by
I still got Memory Error in the longest bilinear forms graphs test,
so here is an optimisation that reduces memory consumption by packing matrices into int
, with it all tests pass.

src/sage/graphs/generators/distance_regular.pyx
diff git a/src/sage/graphs/generators/distance_regular.pyx b/src/sage/graphs/generators/distance_regular.pyx index 094f9bdc6a..7f8df1250d 100644
a b def BilinearFormsGraph(const int d, const int e, const int q): 648 648 sage: K.is_isomorphic(G) 649 649 True 650 650 """ 651 from sage.combinat.integer_vector import IntegerVectors651 from itertools import product as cartprod 652 652 653 653 Fq = GF(q) 654 654 Fqelems = list(Fq) 655 matricesOverq = IntegerVectors(k=d*e, max_part=q1) 656 655 dim = d*e 656 matricesOverq = cartprod(*([range(q)]*dim)) 657 qv = [int(q**jj) for jj in range(dim)] 657 658 rank1Matrices = [] 659 vsp = VectorSpace(Fq, e) 658 660 for u in VectorSpace(Fq, d): 659 661 if u.is_zero() or not u[u.support()[0]].is_one(): 660 662 continue 661 663 662 for v in VectorSpace(Fq, e):664 for v in vsp: 663 665 if v.is_zero(): 664 666 continue 665 667 666 668 sig_check() 667 M = [0] * (d*e)669 M = [0] * dim 668 670 for row in range(d): 669 671 for col in range(e): 670 672 M[e*row + col] = u[row] * v[col] … … def BilinearFormsGraph(const int d, const int e, const int q): 673 675 674 676 edges = [] 675 677 for m1 in matricesOverq: 676 m1 = tuple(map(lambda x: Fqelems[x], m1)) 678 im1 = 0 679 for jj in range(dim): 680 im1 += m1[jj] * qv[jj] 677 681 for m2 in rank1Matrices: 678 682 sig_check() 679 m3 = tuple([m1[i] + m2[i] for i in range(d*e)]) 680 edges.append((m1, m3)) 683 im3 = 0 684 for jj in range(dim): 685 im3 += Fqelems.index(Fqelems[m1[jj]] + m2[jj]) * qv[jj] 686 edges.append((im1, im3)) 681 687 682 688 G = Graph(edges, format='list_of_edges') 683 689 G.name("Bilinear forms graphs over F_%d with parameters (%d, %d)"%(q, d, e))
comment:6 followup: ↓ 8 Changed 21 months ago by
Is this conversion to integers needed for the other forms graphs?
comment:7 Changed 21 months ago by
 Commit changed from 0d92ec49345b05ab42118406755808d60a06d79a to 376d459639fd29d6d73487d4d4271a88fdebcbd8
Branch pushed to git repo; I updated commit sha1. New commits:
376d459  convert matrices in bilinearFormsGraph to integers to lower memory requirements

comment:8 in reply to: ↑ 6 Changed 21 months ago by
Replying to ghIvoMaffei:
Is this conversion to integers needed for the other forms graphs?
it certainly lowers memory consumption, but I would not worry too much about it. There are much better ways to handle this, as implemented in GAP package GRAPE.
comment:9 Changed 21 months ago by
 Reviewers set to Dima Pasechnik
 Status changed from needs_review to positive_review
comment:10 Changed 21 months ago by
 Commit changed from 376d459639fd29d6d73487d4d4271a88fdebcbd8 to ec4456053d07fb45a78270c9dc2d66756b0f2659
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
ec44560  a python style fix

comment:11 Changed 21 months ago by
 Status changed from needs_review to positive_review
comment:12 Changed 21 months ago by
 Status changed from positive_review to needs_work
********************************************************************** File "src/sage/graphs/generators/distance_regular.pyx", line 629, in sage.graphs.generators.distance_regular.BilinearFormsGraph Failed example: G = graphs.BilinearFormsGraph(3,3,3) # long time (20 s) Exception raised: Traceback (most recent call last): File "/home/buildbot/slave/sage_git/build/local/lib/python3.7/sitepackages/sage/doctest/forker.py", line 715, in _run File "/home/buildbot/slave/sage_git/build/local/lib/python3.7/sitepackages/sage/doctest/forker.py", line 1139, in compile_and_execute File "<doctest sage.graphs.generators.distance_regular.BilinearFormsGraph[2]>", line 1, in <module> G = graphs.BilinearFormsGraph(Integer(3),Integer(3),Integer(3)) # long time (20 s) File "sage/graphs/generators/distance_regular.pyx", line 691, in sage.graphs.generators.distance_regular.BilinearFormsGraph (build/cythonized/sage/graphs/generators/distance_regular.c:11929) File "/home/buildbot/slave/sage_git/build/local/lib/python3.7/sitepackages/sage/graphs/graph.py", line 1261, in __init__ File "/home/buildbot/slave/sage_git/build/local/lib/python3.7/sitepackages/sage/graphs/generic_graph.py", line 10935, in add_edges File "sage/graphs/base/sparse_graph.pyx", line 1645, in sage.graphs.base.sparse_graph.SparseGraphBackend.add_edge (build/cythonized/sage/graphs/base/sparse_graph.c:17623) File "sage/graphs/base/sparse_graph.pyx", line 1096, in sage.graphs.base.sparse_graph.SparseGraph.add_arc_label (build/cythonized/sage/graphs/base/sparse_graph.c:13067) MemoryError ********************************************************************** File "src/sage/graphs/generators/distance_regular.pyx", line 630, in sage.graphs.generators.distance_regular.BilinearFormsGraph Failed example: G.order() # long time (due to above) Expected: 19683 Got: 512 **********************************************************************
comment:13 Changed 21 months ago by
Does that really test a code path that cannot be tested in <1s?
comment:14 Changed 21 months ago by
I cannot reproduce the error.
All my code do is calling Graph(edges, format='list_of_edges')
.
The edges
list is long (6652854) but I believe the code path (i.e. the full stack of function calls) should not differ from Graph([(0,1)], format='list_of_edges')
.
I can change the doctest to importing BilinearFormsGraph
directly from sage.graphs.generators.distance_regular
if this solves the issue, but I don't know how to test it myself.
comment:15 Changed 21 months ago by
I agree with Volker (vbraun) that this doctest takes way too long.
Mark it not tested
and add graphs.BilinearFormsGraph(3,4,2)
instead  this takes <3 sec.
comment:16 Changed 21 months ago by
 Commit changed from ec4456053d07fb45a78270c9dc2d66756b0f2659 to 59776810db8b3352985cc688c82b9ea6e48a70dc
Branch pushed to git repo; I updated commit sha1. New commits:
5977681  removed long doctests

comment:17 Changed 21 months ago by
Please run
./sage tp long verbose src/sage/graphs/generators/distance_regular.pyx
to see what tests are the longest. This file is still by far the slowest to test in sage/graphs/
,
3 times as long as anything else there.
GrassmannGraph(2, 6, 3)
and DoubleGrassmannGraph(3, 2)
are the two slowest ones (>30 sec each on my oldish X1 Carbon Lenovo, and they aren't even tagged long time
!), but there are more.
comment:18 Changed 21 months ago by
 Commit changed from 59776810db8b3352985cc688c82b9ea6e48a70dc to 3c3b4b5648d28b7224dee103da30bcf1732f601f
Branch pushed to git repo; I updated commit sha1. New commits:
3c3b4b5  added long time flags

comment:19 Changed 21 months ago by
I marked everything that took more than 1s as long.
I think one should change the default value for warnlong (it is usually 2 min) if 30s are long.
comment:20 Changed 21 months ago by
The buildbot limits the available memory to encourage writing efficient unit tests, hence the MemoryError?
comment:21 Changed 21 months ago by
 Commit changed from 3c3b4b5648d28b7224dee103da30bcf1732f601f to f8803529b1b0007f7a0be54d75b8b6ad4705a78d
comment:22 followup: ↓ 23 Changed 21 months ago by
let's wait for the next beta/rc, to lessen the rebase work.
comment:23 in reply to: ↑ 22 Changed 21 months ago by
Replying to dimpase:
let's wait for the next beta/rc, to lessen the rebase work.
I'm having issues with beta11 not starting for an import error on libgsl.23.dylib Has this issue been brought up yet or am I the only one?
comment:24 Changed 21 months ago by
How do you get gsl
in your installation? Does it come from the system/Homebrew/conda, or do you build it?
comment:25 Changed 21 months ago by
It is in sage/local/lib/. I can send you the crash report, if you wish
comment:26 Changed 21 months ago by
gsl has been updated in just merged #29483.
Perhaps you need to run ./sage f gsl && make build
comment:27 Changed 21 months ago by
 Commit changed from f8803529b1b0007f7a0be54d75b8b6ad4705a78d to 8c12a8f333132858ec3b9e39cd21523786b41dc1
Branch pushed to git repo; I updated commit sha1. New commits:
05c9593  Merge branch 'develop' of git://trac.sagemath.org/sage into t/30337

97f0450  Merge branch 'develop' into t/30312

2a1861d  Merge branch 't/30312' into t/30329

5344f35  added long time flags and fixed van Lint name

9e69f0d  missing # long time

49cdcc1  Merge branch 't/30312' into t/30329

ea30040  added long time flags

4bcdb3c  typos and TeX fixes

feabf4f  better index section, uniform naming

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

comment:28 Changed 21 months ago by
 Status changed from needs_work to needs_review
comment:29 Changed 21 months ago by
 Commit changed from 8c12a8f333132858ec3b9e39cd21523786b41dc1 to c97bda5c59adcfa6f5822587e0d0adaf57d1c38b
comment:30 Changed 21 months ago by
 Commit changed from c97bda5c59adcfa6f5822587e0d0adaf57d1c38b to d9c9149b5e5a60850b15cd90849e63c57898bea2
comment:31 Changed 21 months ago by
 Dependencies changed from #30223, #30329 to #30223, #30509
comment:32 Changed 21 months ago by
please also merge in the latest develop beta, beta12.
comment:33 Changed 21 months ago by
 Commit changed from d9c9149b5e5a60850b15cd90849e63c57898bea2 to 344936159a22dcfe08d64c516496bf688cba49e1
Branch pushed to git repo; I updated commit sha1. New commits:
3449361  Merge branch 9.2.beta12 into t/30337

comment:35 Changed 20 months ago by
 Branch changed from public/graphs/30337 to 344936159a22dcfe08d64c516496bf688cba49e1
 Resolution set to fixed
 Status changed from positive_review to closed
This is where #30223 gets used.
Last 10 new commits:
Merge 30312 into 30329
code for symmetric matrices
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