Opened 22 months ago
Closed 20 months ago
#30337 closed enhancement (fixed)
Graphs: obtain distance-regular graphs from generalised quadrangles
Reported by: | gh-Ivo-Maffei | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.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 distance-regular graphs from generalised quadrangles with spread. Also added a function that checks whether an distance-regular 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=q-1) 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 follow-up: ↓ 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 gh-Ivo-Maffei:
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/site-packages/sage/doctest/forker.py", line 715, in _run File "/home/buildbot/slave/sage_git/build/local/lib/python3.7/site-packages/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/site-packages/sage/graphs/graph.py", line 1261, in __init__ File "/home/buildbot/slave/sage_git/build/local/lib/python3.7/site-packages/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 --warn-long (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 follow-up: ↓ 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