Opened 5 years ago

Closed 5 years ago

#15288 closed enhancement (fixed)

Balanced Incomplete Block Designs with k=4

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.2
Component: combinatorics Keywords:
Cc: dimpase, vbraun, wdj, rbeezer Merged in:
Authors: Nathann Cohen Reviewers: Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: ed87e48 (Commits) Commit: ed87e483d75300a216ba0f00890b0f8cedccfa2c
Dependencies: #15287 Stopgaps:

Description

End of a loong queue of patches, here it is ! The constructions for BIBD with k=4 as found in Douglas Stinson's book "Combinatorial Designs: Constructions and Analysis", which uses the constructions given in #15286 (Latin Squares) and #15287 (Orthogonal Arrays).

This patch creates a file named bibd.py in combinat/design/ for the BIBD we already know how to build and the future ones (I will make sure of that :-P)

Change History (31)

comment:1 Changed 5 years ago by ncohen

  • Branch set to u/ncohen/15288
  • Dependencies set to #15287
  • Status changed from new to needs_review

comment:2 Changed 5 years ago by git

  • Commit set to a4bc0ac8088a90380e5bc215d8ba72603a6b0e61

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

[changeset:a4bc0ac]Move steiner_striple_system from block_design.py to bibd.py
[changeset:a6f66e8]Balanced Incomplete Block Designs and construction for k=4
[changeset:7c1b651]Orthogonal arrays
[changeset:d93abcd]Latin Squares
[changeset:2ec76c7]Bug in AffineGeometryDesign?
[changeset:cf71d58]Rebase on 5.13.beta0
[changeset:9fcfb13]Rename the method from ProjectivePlaneDesign? to DesarguesianProjectivePlaneDesign?
[changeset:363badb]trac 15107 -- reviewer's comments
[changeset:ee6d412]Projective Plane designs constructor

comment:3 Changed 5 years ago by git

  • Commit changed from a4bc0ac8088a90380e5bc215d8ba72603a6b0e61 to 1ad0da955ede3b98b75548c2efc1d59d7750d1f2

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

1ad0da9Rebase on 5.13.beta2

comment:4 Changed 5 years ago by git

  • Commit changed from 1ad0da955ede3b98b75548c2efc1d59d7750d1f2 to 995ba31e9d9933759ba131390aa5aec8c07635f1

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

995ba31Trac #15288 : Theorem 7.20 is now a function of its own, plus some fixes

comment:5 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:6 Changed 5 years ago by git

  • Commit changed from 995ba31e9d9933759ba131390aa5aec8c07635f1 to 92aed30ffcd946c1969794501628b7e185164e06

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

e32c6deOrthogonal arrays -- bugfix
59f340bOrthogonal arrays -- doctest
bbc682atrac #15287: merge with updated #15286
23bc728Merge branch 'u/ncohen/15287' of trac.sagemath.org:sage into u/tscrim/15287
8bae37eReview changes to orthogonal_arrays.py.
849598eLast minor tweak.
92aed30trac #15288: Rebase on updated #15287

comment:7 Changed 5 years ago by git

  • Commit changed from 92aed30ffcd946c1969794501628b7e185164e06 to 31fa8c1730ae72753733fa52a632ce4d1ad861fe

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

31fa8c1trac #15288: Rebase on updated #15287

comment:8 Changed 5 years ago by ncohen

Just rebased on the latest version of its last dependency. Hey guys, all the dependencies are reviewed now ! We can get this in !

Look at what it can do. Isn't it totally cool ? :-PPP

sage: designs.BalancedIncompleteBlockDesign(13,4)

Nathann

comment:9 Changed 5 years ago by dimpase

while building docs, I get

OSError: [combinat ] /usr/local/src/sage/sage-6.1.rc0/local/lib/python2.7/site-packages/sage/combinat/designs/bibd.py:docstring of sage.combinat.designs.bibd.BalancedIncompleteBlockDesign:27: ERROR: Unknown target name: "http://www.argilo.net/files/bibd.pdf".

any clues?

comment:10 Changed 5 years ago by ncohen

It is probably this

`http://www.argilo.net/files/bibd.pdf`_

You can remove the link if it is a problem to compile the doc, it is not very important.

Nathann

comment:11 Changed 5 years ago by dimpase

  • Branch changed from u/ncohen/15288 to u/dimpase/ticket/15288
  • Created changed from 10/16/13 15:02:16 to 10/16/13 15:02:16
  • Modified changed from 03/27/14 20:12:59 to 03/27/14 20:12:59

comment:12 Changed 5 years ago by dimpase

  • Commit changed from 31fa8c1730ae72753733fa52a632ce4d1ad861fe to 58bb9e3b4241db1e857b1cc707063a61b300832f

I pushed the fix for this and one more small doc-related issue.


New commits:

58bb9e3adding <> around inline url and renaming a reference to avoid duplicate

comment:13 Changed 5 years ago by dimpase

  • Status changed from needs_review to needs_work

I don't like that designs.BalancedIncompleteBlockDesign() returns a list of blocks, whereas it should obviously return an IncidenceStructure, e.g. as designs.ProjectivePlaneDesign() does. Please fix this.

comment:14 follow-up: Changed 5 years ago by ncohen

  • Branch changed from u/dimpase/ticket/15288 to public/15288
  • Commit changed from 58bb9e3b4241db1e857b1cc707063a61b300832f to 79386587dc542a0741cb16f7bc99bd0792e4fe75
  • Status changed from needs_work to needs_review

Done. But honestly you are just enforcing your own subjective point of view there, and I do not like what I am doing.

It is very nice if for you a BIBD is a Incidence Structure, but for me this thing is a collection of set. That's all. I could also return a complete graph along with a collection of subgraphs to show that a BIBD is a decomposition of a complete graph into smaller ones, and this does not make any sense at all. For me a BIBD is a collection of sets, and if you want some specific additional structure on top of it you are quite free to set it yourself.

Besides this IncidenceStructure class spends its lifetime sorting stuff I never asked to sort, and copying stuff around for no reason. That's for the loss of computational time resulting for enforcing a subjective point of view.

In the end, I just end up calling .blocks() every time I build a BIBD, and I don't see why I should pay cycles to IncidenceStructure in exchange for that.

Nathann


New commits:

7938658trac #15288: Dima wants the BIBD to be BlockDesigns.....

comment:15 in reply to: ↑ 14 ; follow-up: Changed 5 years ago by dimpase

Replying to ncohen:

Done. But honestly you are just enforcing your own subjective point of view there, and I do not like what I am doing.

I am enforcing consistency, as I indicated quite clearly, I hope. The thing I complained about is akin to graphs.blah() returning a list of edges instead of a Graph.

It is very nice if for you a BIBD is a Incidence Structure, but for me this thing is a collection of set. That's all. I could also return a complete graph along with a collection of subgraphs to show that a BIBD is a decomposition of a complete graph into smaller ones, and this does not make any sense at all. For me a BIBD is a collection of sets, and if you want some specific additional structure on top of it you are quite free to set it yourself.

Besides this IncidenceStructure class spends its lifetime sorting stuff I never asked to sort, and copying stuff around for no reason. That's for the loss of computational time resulting for enforcing a subjective point of view.

well, this just means that IncidenceStructure class is in need of an improvement; perhaps it should get several backends just as Graph has.

comment:16 in reply to: ↑ 15 ; follow-up: Changed 5 years ago by ncohen

I am enforcing consistency, as I indicated quite clearly, I hope.

You are enforcing consistency because consistency is a way to enforce what you like. If I tell you that designs.steiner_quadruple_systems returns tuples then you will tell me (as before) that "It's not because I did something wrong once that I should be allowed to do it again".

Dear, dear consistency :-P

The thing I complained about is akin to graphs.blah() returning a list of edges instead of a Graph.

Yep. Exactly like here, and for the same reason.

well, this just means that IncidenceStructure class is in need of an improvement; perhaps it should get several backends just as Graph has.

Changes nothing. All backends have a cost, all of them mean duplicating stuff uselessly, and none of them is as "simple and understandable" as a list. If you want a data structure to do something specific, pick the data structure that you like. I don't think we should pick a specific data structure over another one, and so I prefer to return the most basic types. The types that the functions actually work with. No copy, easy-to-understand data.

I personally have NOTHING to do of all methods of IncidenceStructure, yet I am the one who implements that code. Isn't that a proof that it is not the right data structure ? :-P

Nathann

comment:17 in reply to: ↑ 16 ; follow-up: Changed 5 years ago by dimpase

Replying to ncohen:

I am enforcing consistency, as I indicated quite clearly, I hope.

You are enforcing consistency because consistency is a way to enforce what you like. If I tell you that designs.steiner_quadruple_systems returns tuples then you will tell me (as before) that "It's not because I did something wrong once that I should be allowed to do it again".

Dear, dear consistency :-P

Do you understand the meaning of the word consistency? Just wondering...

I don't have time to control all the code you produce for consistency, sorry. But, indeed, I am of opinion that designs.* must all return the stuff from the same class. And I am sure the majority on sage-devel would support me on this, if you think that I am not sufficient authority for you.

The thing I complained about is akin to graphs.blah() returning a list of edges instead of a Graph.

Yep. Exactly like here, and for the same reason.

But graphs.* do not do this, and designs.* do. Some have to give, and it's certainly designs.*.

well, this just means that IncidenceStructure class is in need of an improvement; perhaps it should get several backends just as Graph has.

Changes nothing. All backends have a cost, all of them mean duplicating stuff uselessly, and none of them is as "simple and understandable" as a list. If you want a data structure to do something specific, pick the data structure that you like. I don't think we should pick a specific data structure over another one, and so I prefer to return the most basic types. The types that the functions actually work with. No copy, easy-to-understand data.

No, this design (more precisely, absence of one) is crap, it throws away the fact that list in question is a list of blocks of BIBD. It's perfectly OK to have it in your private code, but not in a library code.

E.g. the fact that it is not an immutable list is inviting errors. Another thing, one might wonder what the parameters of the design are. Surely one can have a function to compute them, but it can also be implemented by storing the parameters upon the creation. Same for automorphism groups.

I personally have NOTHING to do of all methods of IncidenceStructure, yet I am the one who implements that code. Isn't that a proof that it is not the right data structure ? :-P

I did not check who wrote IncidenceStructure structure class. Does it matter? It could have been you...

comment:18 in reply to: ↑ 17 ; follow-up: Changed 5 years ago by ncohen

Do you understand the meaning of the word consistency? Just wondering...

My point was to show you that if I try to be consistent with something you don't like, the result is the same :-P

I don't have time to control all the code you produce for consistency, sorry. But, indeed, I am of opinion that designs.* must all return the stuff from the same class. And I am sure the majority on sage-devel would support me on this, if you think that I am not sufficient authority for you.

No authority is ever sufficient to enforce a bad idea. For instance you will never make "MOLS" return block designs. They return lists of sets from time to time. And Orthogonal arrays are not block designs when you call orthogonal_array. So no, these function will never all return the same thing.

But graphs.* do not do this, and designs.* do. Some have to give, and it's certainly designs.*.

graphs.something sometimes return lists of graphs, or iterators on them. Though it is true that *they* are more consistent.

No, this design (more precisely, absence of one) is crap, it throws away the fact that list in question is a list of blocks of BIBD.

Who cares ? You know it when you build it, and you do whatever you want afterwards ! You can change the sets of a block design without changing the name. Actually, with your strandards the design of BlockDesign is pretty bad, for .blocks() does not return a copy of the blocks but the blocks themselves, so I wondered at some point if it was safe to do that. See ? More copies for nothing, just because you want to wrap them in a data structure when nobody requested it.

It's perfectly OK to have it in your private code, but not in a library code.

E.g. the fact that it is not an immutable list is inviting errors.

Do you see that your way of looking at things will add useless copies everywhere ? Copies, and sorting, and equality tests, all for no new feature, but only for "good code administration" ? Do you see the cost of this, and the total lack of gain in the process ?

The code will be slower. For nothing. What's so good in "consistency" that we have to pay all this ?

Another thing, one might wonder what the parameters of the design are.

Not when one creates the design by giving it the parameters. But they can recompute them afterwards, I fixed the function recently.

Surely one can have a function to compute them, but it can also be implemented by storing the parameters upon the creation. Same for automorphism groups.

You are all crazy with your caches everywhere, immutable structures and so. You waste computations. Consider the developers as responsible beings, and you will stop having to copy/cache stuff when nobody asks you as if you wanted to protect them from themselves. They know what they are doing.

I did not check who wrote IncidenceStructure structure class. Does it matter? It could have been you...

Well, it does not do much. It builds the matrix from the blocks, or the blocks from the matrix, it computes parameters... Well, to be honest it does its job. It's just that there is no reason on earth why we should pay copies to this data structure if we don't need it.

Nathann

comment:19 Changed 5 years ago by ncohen

(Oh, by the way I just looked at the list of commits in this branch and saw that the Orthogonal Array stuff is still there : it has already been reviewed, so this part should be okay. It's not easy to know what is left to review now :-/)

comment:20 in reply to: ↑ 18 ; follow-up: Changed 5 years ago by dimpase

Replying to ncohen:

Do you understand the meaning of the word consistency? Just wondering...

My point was to show you that if I try to be consistent with something you don't like, the result is the same :-P

I don't have time to control all the code you produce for consistency, sorry. But, indeed, I am of opinion that designs.* must all return the stuff from the same class. And I am sure the majority on sage-devel would support me on this, if you think that I am not sufficient authority for you.

No authority is ever sufficient to enforce a bad idea. For instance you will never make "MOLS" return block designs. They return lists of sets from time to time. And Orthogonal arrays are not block designs when you call orthogonal_array. So no, these function will never all return the same thing.

But graphs.* do not do this, and designs.* do. Some have to give, and it's certainly designs.*.

graphs.something sometimes return lists of graphs, or iterators on them. Though it is true that *they* are more consistent.

No, this design (more precisely, absence of one) is crap, it throws away the fact that list in question is a list of blocks of BIBD.

Who cares ? You know it when you build it, and you do whatever you want afterwards !

a user can go through designs.* and call functions, like

You can change the sets of a block design without changing the name. Actually, with your strandards the design of BlockDesign is pretty bad, for .blocks() does not return a copy of the blocks but the blocks themselves, so I wondered at some point if it was safe to do that. See ? More copies for nothing, just because you want to wrap them in a data structure when nobody requested it.

ProjectivePlaneDesign() is written by you, isn't it? And it does return IncidenceStructure. Needless to say, ProjectivePlaneDesign() is a BIBD. You simply do not have a good argument to justify why in different cases you return different classes.

comment:21 in reply to: ↑ 20 Changed 5 years ago by ncohen

ProjectivePlaneDesign() is written by you, isn't it? And it does return IncidenceStructure. Needless to say, ProjectivePlaneDesign() is a BIBD. You simply do not have a good argument to justify why in different cases you return different classes.

O_O

Hey, let's make them all return lists of Sets if you don't mind ! :-D

This function returns IncidenceStructure because I copy/pasted from projective geometry design, but really I could not care less about Incidence Structure. I just never used those functions in any way. I just want the sets :-P

Nathann

comment:22 Changed 5 years ago by dimpase

  • Reviewers set to Dima Pasechnik
  • Status changed from needs_review to positive_review

OK, good.

comment:23 Changed 5 years ago by ncohen

Wow.

Wow.

BIBD with k=4 reviewed.

THaaaaaaaaaaaaaaaaaaaaaaaaaaank you so much !! :-)

I can clean the code for k=5 now.

Nathann

comment:24 Changed 5 years ago by vbraun

PDF docs don't build:

(inputenc)                in inputencoding `utf8'.

See the inputenc package documentation for explanation.
Type  H <return>  for immediate help.
 ...                                              
                                                  
l.173287 Returns a $(v,\{^^D
                            ,5,8,9,12\})-PBD$ on $v$ elements.
? 
! Emergency stop.
 ...                                              
                                                  
l.173287 Returns a $(v,\{^^D
                            ,5,8,9,12\})-PBD$ on $v$ elements.
!  ==> Fatal error occurred, no output PDF file produced!
Transcript written on combinat.log.

comment:25 Changed 5 years ago by dimpase

here is the diff to fix the thing:

--- a/src/sage/combinat/designs/bibd.py
+++ b/src/sage/combinat/designs/bibd.py
@@ -449,7 +449,7 @@ def _relabel_bibd(B,n):
 
 def PBD_4_5_8_9_12(v, check=True):
     """
-    Returns a `(v,\{\4,5,8,9,12\})-PBD` on `v` elements.
+    Returns a `(v,\{4,5,8,9,12\})-PBD` on `v` elements.
 
     A `(v,\{4,5,8,9,12\})`-PBD exists if and only if `v\equiv 0,1 \pmod 4`. The
     construction implemented here appears page 168 in [Stinson2004]_.

I have to f*cking clue how to push such a commit into the right place. Git the hard way does give recepies that push something somewhere, but certainly not where it should go to...

comment:26 Changed 5 years ago by dimpase

  • Branch changed from public/15288 to public/typofix15288
  • Commit changed from 79386587dc542a0741cb16f7bc99bd0792e4fe75 to ed87e483d75300a216ba0f00890b0f8cedccfa2c

comment:27 Changed 5 years ago by dimpase

I've modified the description of the ticket to point to the "right" branch and commit. Hope I didn't screw this too badly...

comment:28 Changed 5 years ago by vbraun

Just git push trac HEAD:public/15288 should have done it. But this is fine, too.

comment:29 Changed 5 years ago by dimpase

I don't see how this could work - unless I don't create my own branch. I did as described in Git the hard way:

git fetch trac public/15288
get checkout -b typofix15288 FETCH_HEAD
... editing the file...
git commit -a
git push --set-upstream trac HEAD:public/typofix15288` 

And trac server was not impressed :-)

I thought that the reason for this is some kind of lack of permissions to commit to a branch that is not my own... Anyhow, it's not clear from the description in the docs. Especially it's unclear under what conditions the manual changing of the branch and commit fields are not needed.

Last edited 5 years ago by dimpase (previous) (diff)

comment:30 Changed 5 years ago by vbraun

Everybody can write to branches named public/...

Trac can't possibly know that public/typofix15288 is supposed to be on this ticket, which is why you had to manually update the ticket.

comment:31 Changed 5 years ago by vbraun

  • Branch changed from public/typofix15288 to ed87e483d75300a216ba0f00890b0f8cedccfa2c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.