Opened 2 years ago

Closed 2 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:

Status badges

Description (last modified by Dima Pasechnik)

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 2 years ago by gh-Ivo-Maffei

Cc: Dima Pasechnik added
Status: newneeds_review

comment:2 Changed 2 years ago by Dima Pasechnik

Reviewers: Dima Pasechnik
Status: needs_reviewneeds_work
Work issues: correct error messages

looks great, adds a lot of nice stuff, but error messages need to be adjusted (lambda=1 is fixed there I suppose):

sage: designs.balanced_incomplete_block_design(79,13,2)
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
<ipython-input-5-1a5677b9322f> in <module>()
----> 1 designs.balanced_incomplete_block_design(Integer(79),Integer(13),Integer(2))

/mnt/opt/Sage/sage-clang/local/lib/python3.7/site-packages/sage/combinat/designs/bibd.py in balanced_incomplete_block_design(v, k, lambd, existence, use_LJCR)
    271         return Unknown
    272     else:
--> 273         raise NotImplementedError("I don't know how to build a ({},{},1)-BIBD!".format(v, k))
    274 
    275 def steiner_triple_system(n):

NotImplementedError: I don't know how to build a (79,13,1)-BIBD!

(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.

comment:3 Changed 2 years ago by Dima Pasechnik

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 
    162162        sage: designs.balanced_incomplete_block_design(1171,10)
    163163        (1171,10,1)-Balanced Incomplete Block Design
    164164
    165     And we know some inexistence results::
     165    And we know some nonexistence results::
    166166
    167167        sage: designs.balanced_incomplete_block_design(21,6,existence=True)
    168168        False
    def balanced_incomplete_block_design(v, k, lambd=1, existence=False, use_LJCR=Fa 
    176176        sage: designs.balanced_incomplete_block_design(37,9,8)
    177177        (37,9,8)-Balanced Incomplete Block Design
    178178        sage: designs.balanced_incomplete_block_design(15,7,3)
    179         g(15,7,3)-Balanced Incomplete Block Design
     179        (15,7,3)-Balanced Incomplete Block Design
    180180    """
    181181
    182182    # Trivial BIBD
    def balanced_incomplete_block_design(v, k, lambd=1, existence=False, use_LJCR=Fa 
    270270    if existence:
    271271        return Unknown
    272272    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))
    274274
    275275def steiner_triple_system(n):
    276276    r"""
Last edited 2 years ago by Dima Pasechnik (previous) (diff)

comment:4 Changed 2 years ago by Dima Pasechnik

the typo with extra g tells me that you didn't run doctests :-)

Last edited 2 years ago by Dima Pasechnik (previous) (diff)

comment:5 Changed 2 years ago by Dima Pasechnik

Description: modified (diff)

comment:6 Changed 2 years ago by git

Commit: b6a7f0147272177b407d518dc9628c242086e7579a9705cc2292fe59816b3f3c0a9c7e8a14700406

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

9a9705cfixed typos

comment:7 Changed 2 years ago by gh-Ivo-Maffei

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 2 years ago by gh-Ivo-Maffei

Status: needs_workneeds_review

comment:9 Changed 2 years ago by Dima Pasechnik

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 2 years ago by Dima Pasechnik

Status: needs_reviewneeds_work

comment:11 Changed 2 years ago by Dima Pasechnik

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 2 years ago by Dima Pasechnik

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 2 years ago by gh-Ivo-Maffei

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 2 years ago by Dima Pasechnik

I ran sage -tp src/sage/combinat/ and sage -tp src/sage/graphs/ Yes, ideally you should run make ptestlong - takes time.

Last edited 2 years ago by Dima Pasechnik (previous) (diff)

comment:15 Changed 2 years ago by Dima Pasechnik

don't forget to push the fixes.

comment:16 Changed 2 years ago by git

Commit: 9a9705cc2292fe59816b3f3c0a9c7e8a14700406437afc8a6d12509b31fd3c76466349695a02eef2

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

437afc8fixed bug with k=2

comment:17 Changed 2 years ago by gh-Ivo-Maffei

I run make ptest this time and all seem to work.

comment:18 Changed 2 years ago by gh-Ivo-Maffei

Status: needs_workneeds_review
Work issues: correct error messages

comment:19 in reply to:  7 Changed 2 years ago by Dima Pasechnik

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:20 Changed 2 years ago by Dima Pasechnik

Status: needs_reviewpositive_review

OK, good.

comment:21 Changed 2 years ago by Samuel Lelièvre

Status: positive_reviewneeds_work

The patchbots report pyflakes and pycodestyles errors.

comment:22 Changed 2 years ago by gh-Ivo-Maffei

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 2 years ago by Samuel Lelièvre

Thanks for explaining. I don't feel strongly about it, feel free to set back to positive review.

comment:24 Changed 2 years ago by Dima Pasechnik

Status: needs_workpositive_review

OK.

comment:25 Changed 2 years ago by git

Commit: 437afc8a6d12509b31fd3c76466349695a02eef25186f8f9f3f4b3c8f33d6bfb229595e2e94d17bc
Status: positive_reviewneeds_review

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

5186f8fsmall code formatting

comment:26 Changed 2 years ago by gh-Ivo-Maffei

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 2 years ago by git

Commit: 5186f8f9f3f4b3c8f33d6bfb229595e2e94d17bcd2d340e040d05aa8be6326913576bdf7cda44d23

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

d2d340eforgot to delete old import

comment:28 Changed 2 years ago by Dima Pasechnik

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 2 years ago by Dima Pasechnik

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 2 years ago by gh-Ivo-Maffei

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 2 years ago by git

Commit: d2d340e040d05aa8be6326913576bdf7cda44d23a60769317c4d0a0d601270ee1123318cebee8564

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

a607693changed docstring

comment:32 Changed 2 years ago by Dima Pasechnik

Status: needs_reviewpositive_review

comment:33 Changed 2 years ago by Dima Pasechnik

OK

comment:34 Changed 2 years ago by Dima Pasechnik

Bibd(6,3,2) is probably another story. Not sure how it is built from what we have already

comment:35 Changed 2 years ago by Volker Braun

Branch: u/gh-Ivo-Maffei/bibda60769317c4d0a0d601270ee1123318cebee8564
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.