Opened 3 years ago
Closed 3 years ago
#29959 closed enhancement (fixed)
Extended the construction of BIBDs to allow for \lambda different from 1
Reported by: | gh-Ivo-Maffei | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.2 |
Component: | combinatorial designs | Keywords: | bibd combinatorial-designs |
Cc: | Dima Pasechnik | Merged in: | |
Authors: | Ivo Maffei | Reviewers: | Dima Pasechnik |
Report Upstream: | N/A | Work issues: | |
Branch: | a607693 (Commits, GitHub, GitLab) | Commit: | a60769317c4d0a0d601270ee1123318cebee8564 |
Dependencies: | #29887 | Stopgaps: |
Description (last modified by )
Extended the function balanced_incomplete_block_design
(aka BIBD) to allow arbitrary values for the parameter \lambda
.
More on BIBDs may be found here: https://en.wikipedia.org/wiki/Block_design
Change History (35)
comment:1 Changed 3 years ago by
Cc: | Dima Pasechnik added |
---|---|
Status: | new → needs_review |
comment:2 Changed 3 years ago by
Reviewers: | → Dima Pasechnik |
---|---|
Status: | needs_review → needs_work |
Work issues: | → correct error messages |
comment:3 Changed 3 years ago by
here is the fix - and also a fix for 2 typos:
-
src/sage/combinat/designs/bibd.py
a b def balanced_incomplete_block_design(v, k, lambd=1, existence=False, use_LJCR=Fa 162 162 sage: designs.balanced_incomplete_block_design(1171,10) 163 163 (1171,10,1)-Balanced Incomplete Block Design 164 164 165 And we know some inexistence results::165 And we know some nonexistence results:: 166 166 167 167 sage: designs.balanced_incomplete_block_design(21,6,existence=True) 168 168 False … … def balanced_incomplete_block_design(v, k, lambd=1, existence=False, use_LJCR=Fa 176 176 sage: designs.balanced_incomplete_block_design(37,9,8) 177 177 (37,9,8)-Balanced Incomplete Block Design 178 178 sage: designs.balanced_incomplete_block_design(15,7,3) 179 g(15,7,3)-Balanced Incomplete Block Design179 (15,7,3)-Balanced Incomplete Block Design 180 180 """ 181 181 182 182 # Trivial BIBD … … def balanced_incomplete_block_design(v, k, lambd=1, existence=False, use_LJCR=Fa 270 270 if existence: 271 271 return Unknown 272 272 else: 273 raise NotImplementedError("I don't know how to build a ({},{}, 1)-BIBD!".format(v, k))273 raise NotImplementedError("I don't know how to build a ({},{},{})-BIBD!".format(v, k, lambd)) 274 274 275 275 def steiner_triple_system(n): 276 276 r"""
comment:4 Changed 3 years ago by
the typo tells me that you didn't run doctests :-)
comment:5 Changed 3 years ago by
Description: | modified (diff) |
---|
comment:6 Changed 3 years ago by
Commit: | b6a7f0147272177b407d518dc9628c242086e757 → 9a9705cc2292fe59816b3f3c0a9c7e8a14700406 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
9a9705c | fixed typos
|
comment:7 follow-up: 19 Changed 3 years ago by
Thanks for the review. The dockets pass, the issue with the g
is that I often start typing "git" before the os has fully switch from the editor to the console. I should definitely be more careful, but they are tricky to catch as I have run all tests before I use git.
I'll try and implement the biplane now, otherwise I will end up forgetting.
comment:8 Changed 3 years ago by
Status: | needs_work → needs_review |
---|
comment:9 Changed 3 years ago by
not all doctests pass - namely, the following gets broken by this branch on Sage 9.1.beta2
sage -t --warn-long 67.2 src/sage/graphs/strongly_regular_db.pyx ********************************************************************** File "src/sage/graphs/strongly_regular_db.pyx", line 487, in sage.graphs.strongly_regular_db.is_goethals_seidel Failed example: g = t[0](*t[1:]); g Exception raised: Traceback (most recent call last): File "/mnt/opt/Sage/sage-clang/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 680, in _run self.compile_and_execute(example, compiler, test.globs) File "/mnt/opt/Sage/sage-clang/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 1104, in compile_and_execute exec(compiled, globs) File "<doctest sage.graphs.strongly_regular_db.is_goethals_seidel[5]>", line 1, in <module> g = t[Integer(0)](*t[Integer(1):]); g File "/mnt/opt/Sage/sage-clang/local/lib/python3.7/site-packages/sage/graphs/generators/families.py", line 1287, in GoethalsSeidelGraph for i in row]) File "/mnt/opt/Sage/sage-clang/local/lib/python3.7/site-packages/sage/graphs/generators/families.py", line 1287, in <listcomp> for i in row]) IndexError: pop from empty list
comment:10 Changed 3 years ago by
Status: | needs_review → needs_work |
---|
comment:11 Changed 3 years ago by
you managed to break incidence_matrix:
sage: designs.balanced_incomplete_block_design(16,2).incidence_matrix() 16 x 240 sparse matrix over Integer Ring (use the '.str()' method to see the entries)
it should be 16x120.
comment:12 Changed 3 years ago by
or perhaps just blocks in such a trivial case:
sage: d=designs.balanced_incomplete_block_design(3,2,1) sage: d.blocks() [[0, 1], [0, 1], [0, 2], [0, 2], [1, 2], [1, 2]]
comment:13 Changed 3 years ago by
I have fixed the issue. However, I think I'm missing something when running the doctests.
Usually, I execute sage -t src/sage/combinat/designs/bibd.py
. How did you end up testing strongly_regular_db
?
Do I need to run all doctests (make ptest
) or is there a way to only test the dependencies?
comment:14 Changed 3 years ago by
I ran sage -tp src/sage/combinat/
and sage -tp src/sage/graphs/
Yes, ideally you should run make ptestlong
- takes time.
comment:16 Changed 3 years ago by
Commit: | 9a9705cc2292fe59816b3f3c0a9c7e8a14700406 → 437afc8a6d12509b31fd3c76466349695a02eef2 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
437afc8 | fixed bug with k=2
|
comment:18 Changed 3 years ago by
Status: | needs_work → needs_review |
---|---|
Work issues: | correct error messages |
comment:19 Changed 3 years ago by
Replying to gh-Ivo-Maffei:
I'll try and implement the biplane now, otherwise I will end up forgetting.
in any event, it makes sense to implement https://en.wikipedia.org/wiki/Bruck%E2%80%93Ryser%E2%80%93Chowla_theorem
to rule out sets of parameters for symmetric BIBDs - so far it is only done in Sage for
pojective planes, see projective_plane
in src/sage/combinat/designs/block_design.py
comment:21 Changed 3 years ago by
Status: | positive_review → needs_work |
---|
The patchbots report pyflakes and pycodestyles errors.
comment:22 Changed 3 years ago by
If I interpret the pyflakes report correctly, it complains about ".block_design.BlockDesign imported but unused".
That's wrong as BlockDesign
is used at line 227. However, I think we could (and should) use BalancedIncompleteBlockDesign
there.
I'm now running the doctests to make sure I'm not wrong.
I fixed the pycodestyle errors, but I personally believe that code (especially the 10 lines of if ... else if ...) looked better before. Anyway, I'll push the changes as soon as the tests pass.
comment:23 Changed 3 years ago by
Thanks for explaining. I don't feel strongly about it, feel free to set back to positive review.
comment:25 Changed 3 years ago by
Commit: | 437afc8a6d12509b31fd3c76466349695a02eef2 → 5186f8f9f3f4b3c8f33d6bfb229595e2e94d17bc |
---|---|
Status: | positive_review → needs_review |
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
5186f8f | small code formatting
|
comment:26 Changed 3 years ago by
I apologise for the delay, but I finally got round to swap the BlockDesign
use to BalancedIncompleteBlockDesign
. It took longer than expected as some tests were failing, but they are completely unrelated.
comment:27 Changed 3 years ago by
Commit: | 5186f8f9f3f4b3c8f33d6bfb229595e2e94d17bc → d2d340e040d05aa8be6326913576bdf7cda44d23 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
d2d340e | forgot to delete old import
|
comment:28 Changed 3 years ago by
a typo in docstring:
In particular, Sage can build a `(v,k,1)`-BIBD when one exists for all `k\leq
there should be \lambda
instead of 1
.
comment:29 Changed 3 years ago by
a typo in docstring:
In particular, Sage can build a `(v,k,1)`-BIBD when one exists for all `k\leq
there should be \lambda
instead of 1
.
Also, change the previous line
sage: BIBD = designs.balanced_incomplete_block_design(7,3)
to use (7,3,1)
.
comment:30 Changed 3 years ago by
I'll change the (7,3,1)
, but I'm not sure the other sentence should be changed.
On my computer designs.balanced_incomplete_block_design(6,3,2)
raises a NotImplementedError
and Wikipedia states that there is such a BIBD (https://en.wikipedia.org/wiki/Block_design#Examples).
comment:31 Changed 3 years ago by
Commit: | d2d340e040d05aa8be6326913576bdf7cda44d23 → a60769317c4d0a0d601270ee1123318cebee8564 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
a607693 | changed docstring
|
comment:32 Changed 3 years ago by
Status: | needs_review → positive_review |
---|
comment:34 Changed 3 years ago by
Bibd(6,3,2) is probably another story. Not sure how it is built from what we have already
comment:35 Changed 3 years ago by
Branch: | u/gh-Ivo-Maffei/bibd → a60769317c4d0a0d601270ee1123318cebee8564 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
looks great, adds a lot of nice stuff, but error messages need to be adjusted (lambda=1 is fixed there I suppose):
(BIBD(79,13,2) is a largest known biplane (cf. https://en.wikipedia.org/wiki/Block_design#Biplanes), so it would eventually be nice to have, but not on this ticket.