Basic Block design methods

[brettpim]

includes complement, supplement, block derivation, block residue and union of block designs

Depends on #16553

CC: @KPanComputes @videlec @sagetrac-melissah @sagetrac-danziger

Component: combinatorial designs

Keywords: Block Design, Incidence Structure, Residual, Derived, Complement, Supplement, Union

Author: Brett Stevens

Branch/Commit: u/brett/design @ 910b437

Issue created by migration from https://trac.sagemath.org/ticket/16534

[KPanComputes]

comment:2

Hmm, a part of this was the intent of the ticket #16287. However, a linear combination of my own laziness and limited internet and sage access has made it impossible for me to finish the ticket. We should probably close that one in favour of this which mentions one more operation: the union of block designs.

[videlec]

comment:3

Hey,

On #16552 we are talking about reimplementing IncidenceStructure. Do you already have code for that ticket? I do not want to create interference.

Vincent

[videlec]

comment:4

Replying to @videlec:

Hey,

On #16552 we are talking about reimplementing IncidenceStructure. Do you already have code for that ticket? I do not want to create interference.

All right, the best will be to build your work above #16553. Otherwise, it will be a complete mess.

Vincent

[videlec]

Dependencies: #16553

[brettpim]

Branch: u/brett/design

[brettpim]

New commits:

f72a8ed

Added basic design theory methods

[brettpim]

Commit: f72a8ed

[brettpim]

comment:8

I rebuilt my old code on top of Vincent's major changes to the file.

[brettpim]

comment:9

I would also like to discuss the "maximal packing" method that Vincent created in his revisions. Where is the appropriate space to have this discussion?

[brettpim]

comment:10

How can I close/delete #7422

[brettpim]

Changed keywords from none to Block Design, Incidence Structure, Residual, Derived, Complement, Supplement, Point Deletion

[nathanncohen]

comment:13

I would also like to discuss the "maximal packing" method that Vincent created in his revisions. Where is the appropriate space to have this discussion?

By email or on sage-devel, depending on who you want to involve. If you want to discuss it by email I would be glad to be in Cc, by the way :-)

Nathann

[nathanncohen]

comment:14

Hellooooooo Brett,

Here is a first-pass review of your branch:

• About giving credit to the authors: I believe that this part of your branch is
  a bit too verbose, if I may say. I am not saying that you should not leave a
  trace of what you do in the source code, but on the other hand we are many to
  work on the same files, and we patch them very often. We cannot leave a 'log'
  of what is being done to the files every time, for if we did most of the files
  would be credit to the authors.

  To give you an idea: after all the work we did recently in the design code
  (around 60+ tickets), my name and Vincent's appear for a total of three times
  in the whole designs/ folder.

  Furthermore, we used to advise developers to add their name in the functions
  that they implement, just in case we need to find out who wrote them later on:
  it turns out that the 'git blame' command does that 1000x more easily, so
  this is not needed anymore. Added to that, it is often true that some function
  initially written by X is then totally rewritten by Y... and only the name of
  X appears in the function's doc.

  http://git-scm.com/docs/git-blame

  Thus please, if you do want to leave your name somewhere, add a line with a
  short description of what you did. Vincent left the following comment at the
  head of incidence_structure.py:

  - Vincent Delecroix (2014): major rewrite
  

• About line length: we try to keep lines of doc/code to a maximum of 80
  characters (unless that makes the doc/code much harder to read)

• We try to write the documentation of each function following a pattern:

  1. A one-line description of what the function does

  2. Longer explanations if needed in the next paragraph

  See
  http://www.sagemath.org/doc/developer/coding_basics.html#the-docstring-of-a-function-content

• In the specific case of incidence_structure.py, you will find at the top of
  the page an index of all methods, which makes it easier to browse. Please add
  yours to that list.

  http://www.sagemath.org/doc/reference/graphs/sage/combinat/designs/incidence_structures.html

• Could you use backticks `x` instead of $x$ in this file? This is
  the style that is used there.

• pt in self.ground_set() builds the list of points only to throw it away
  afterwards. You will find how to do that in the code of other functions.

• A big block of code from derived_incidence_structure_at_point seems to be
  equivalent to

  [[x for x in B if x!=p] for B in self if p in self]
  

  I also do not understand to what end you sort the sets.

• about derived_incidence_structure_at_block/point and
  residual_incidence_structure_at_block/point. I would be for turning these
  two very similar functions to something like
  derived_incidence_structure(at_point=p) and
  derived_incidence_structure(at_block=b). Actually, perhaps
  derived_structure and residual_structure may be sufficient.

• about delete_points -- I feel a bit uneasy with respect to this function, as
  contrarily to what 'graph' does it does not remove the points 'inplace' but
  returns a copy. Furthermore, 'removing' a point x always leaves some
  uncertainty with respect to the blocks containing x: are they reduced?
  deleted?

• We already have .induced_substructure and .trace which more or less do the
  job. Perhaps we could add an argument to them in order to remove points from
  the whole design, instead of giving the list of those that will stay?

Tell me what you think about the points above. Cheers,

Nathann

[brettpim]

comment:15

Replying to @nathanncohen:

Hellooooooo Brett,

Here is a first-pass review of your branch:

• About giving credit to the authors: I believe that this part of your branch is
  a bit too verbose, if I may say. I am not saying that you should not leave a
  trace of what you do in the source code, but on the other hand we are many to
  work on the same files, and we patch them very often. We cannot leave a 'log'
  of what is being done to the files every time, for if we did most of the files
  would be credit to the authors.

To give you an idea: after all the work we did recently in the design code
(around 60+ tickets), my name and Vincent's appear for a total of three times
in the whole designs/ folder.

Furthermore, we used to advise developers to add their name in the functions
that they implement, just in case we need to find out who wrote them later on:
it turns out that the 'git blame' command does that 1000x more easily, so
this is not needed anymore. Added to that, it is often true that some function
initially written by X is then totally rewritten by Y... and only the name of
X appears in the function's doc.

http://git-scm.com/docs/git-blame

Thus please, if you do want to leave your name somewhere, add a line with a
short description of what you did. Vincent left the following comment at the
head of incidence_structure.py:

- Vincent Delecroix (2014): major rewrite

OK, I will put my name at the top and remove from code.

• About line length: we try to keep lines of doc/code to a maximum of 80
  characters (unless that makes the doc/code much harder to read)

• We try to write the documentation of each function following a pattern:

1. A one-line description of what the function does

2. Longer explanations if needed in the next paragraph

See
http://www.sagemath.org/doc/developer/coding_basics.html#the-docstring-of-a-function-content

This should be no problem

• In the specific case of incidence_structure.py, you will find at the top of
  the page an index of all methods, which makes it easier to browse. Please add
  yours to that list.

http://www.sagemath.org/doc/reference/graphs/sage/combinat/designs/incidence_structures.html

sure, in any particular order?

• Could you use backticks `x` instead of $x$ in this file? This is
  the style that is used there.

sure

• pt in self.ground_set() builds the list of points only to throw it away
  afterwards. You will find how to do that in the code of other functions.

You mean in the other functions I will see how to have the same functionality without the waste of time and space?

• A big block of code from derived_incidence_structure_at_point seems to be
  equivalent to

[[x for x in B if x!=p] for B in self if p in self]

this is much nicer!

I also do not understand to what end you sort the sets.

way back when I started these methods, the blocks were not sorted and this led to __eq__ not working properly, so I do this to makes sure that everything is in a invarient form.

• about derived_incidence_structure_at_block/point and
  residual_incidence_structure_at_block/point. I would be for turning these
  two very similar functions to something like
  derived_incidence_structure(at_point=p) and
  derived_incidence_structure(at_block=b). Actually, perhaps
  derived_structure and residual_structure may be sufficient.

• about delete_points -- I feel a bit uneasy with respect to this function, as
  contrarily to what 'graph' does it does not remove the points 'inplace' but
  returns a copy. Furthermore, 'removing' a point x always leaves some
  uncertainty with respect to the blocks containing x: are they reduced?
  deleted?

In design theory when we delete points we keep the blocks that had the point, we just remove the points from them. This is like truncating a group in a TD (you keep the group) or going from projective plane to the affine plane it contains (you keep all the lines, except the one which ends up empty). I don't mind this doing this inplace like the graphs.

• We already have .induced_substructure and .trace which more or less do the
  job. Perhaps we could add an argument to them in order to remove points from
  the whole design, instead of giving the list of those that will stay?

induced is not at all the same method (as that throws away blocks which lose any points)

you are right it seems that trace does what I am doing for "delete_points" do you agree from my description above?

Tell me what you think about the points above. Cheers,

Nathann

[brettpim]

comment:16

In general when should a method return a new incidence structure and when should it modify the current incidence structure in place?

Is there a sage philosophy for this?

[nathanncohen]

comment:17

Hello,

sure, in any particular order?

As you see fit. I would say 'respect the alphabetical order' if the existing entries do, otherwise reorder them, otherwise add them to the end of the list, otherwise [...].

You mean in the other functions I will see how to have the same functionality without the waste of time and space?

Indeed.

way back when I started these methods, the blocks were not sorted and this led to __eq__ not working properly, so I do this to makes sure that everything is in a invarient form.

Oh I see. Well, this has been solved some time ago and you do not have to sort the blocks anymore. You can, optionally, give the blocks to IncidenceStructure and 'swear' that they are already sorted: this is only useful to save some time when you know that the blocks are already as they should.

In design theory when we delete points we keep the blocks that had the point, we just remove the points from them. This is like truncating a group in a TD (you keep the group) or going from projective plane to the affine plane it contains (you keep all the lines, except the one which ends up empty). I don't mind this doing this inplace like the graphs.

Well, doing this inplace raises new problems: you cannot do that in an object of type BIBD as it will not remain a BIBD (most of the time). We are somehow stuck there, which is why I proposed this optional argument to trace/induced_substructure.

Cheers,

Nathann

[brettpim]

comment:18

I know how to skip lines of output in a doctest and still have the testing recognize the output:

sage: BD2.residual_incidence_structure(at_block=[0,2,4])
Traceback (most recent call last):
...
ValueError: Block [0, 2, 4] is not in the block set.

But how can I skip part of a line of output and makes sure the test still recognizes the output?

[brettpim]

comment:19

OK, I figured out how to make what I needed work:

sage: BD3 = BD1.derived_incidence_structure()
doctest:...: UserWarning: no point nor block given to derive at.  Simply returning self.

where the ellipsis match the line number that appears between the colons. But I had tried ellipsis in other various ways and they did not work. I cannot find a clear explanation of exactly what ellipsis will match in the output of a doctest. Do any of you know exactly how they work?

[sagetrac-git]

Changed commit from f72a8ed to 0da6340

[sagetrac-git]

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

0da6340

new basic design theory methods

[sagetrac-git]

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

dc5e9c6

add basic design theory methods and modified packing method

[nathanncohen]

comment:29

Hello Brett,

It seems that your branch still includes traces of a failed merge. Look for strings like ">>>>" in the design/ files and you will find them.

Also, I had to ask you about the two "todo" that you add: we have a .is_resolvable function and all designs are already checked at construction time. You will find the 'actual' code in designs_pyx.pyx, and the calls appear in the __init__ functions of each class.

Nathann

P.S.: Also, something weird happened as every commit appears twice in your branch. You will see that if you click on the 'commits' link that appears right next to the name of your branch at the head of the ticket.

[nathanncohen]

comment:30

(it is much easier to use git if you have some graphical way to visualize the branches. I use 'tig' which works in command line, but there are many others)

[sagetrac-git]

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

13280d9

fixed more merging issues

[sagetrac-git]

Changed commit from 2a3ec4b to 13280d9

[brettpim]

comment:32

Replying to @nathanncohen:

Hello Brett,

It seems that your branch still includes traces of a failed merge. Look for strings like ">>>>" in the design/ files and you will find them.

I think I got them all this time.

Also, I had to ask you about the two "todo" that you add: we have a .is_resolvable function and all designs are already checked at construction time. You will find the 'actual' code in designs_pyx.pyx, and the calls appear in the __init__ functions of each class.

An incidence structure is group divisible iff its dual is resolvable so the is_resolvable method can be used to determine if the IS is group divisible. The question is if we find that a IS is group divisible, what do we want to do. Do we want to store the groups as a part fo the IS?

Nathann

P.S.: Also, something weird happened as every commit appears twice in your branch. You will see that if you click on the 'commits' link that appears right next to the name of your branch at the head of the ticket.

I am using

git add src/sage/combinat/designs/incidence_structures.py
git commit
git trac push 16534 

should I be doing something differently?

[nathanncohen]

comment:33

Hello,

I think I got them all this time.

You did.

An incidence structure is group divisible iff its dual is resolvable so the is_resolvable method can be used to determine if the IS is group divisible. The question is if we find that a IS is group divisible, what do we want to do. Do we want to store the groups as a part fo the IS?

From your question I wonder if we are talking about the same thing. I was simply saying that we have a function is_group_divisible_design that tells you if an incidence structure is a group divisible design. Is that also what you have in mind?

In particular, I do not understand how that could be equivalent to finding out whether the dual is resolvable: we have a .is_resolvable function, but it is rather slow.

I am using

git add src/sage/combinat/designs/incidence_structures.py
git commit
git trac push 16534 

should I be doing something differently?

No, those commands look okay. It must be something that happened before.

Nathann

[brettpim]

comment:34

Replying to @nathanncohen:

P.S.: Also, something weird happened as every commit appears twice in your branch. You will see that if you click on the 'commits' link that appears right next to the name of your branch at the head of the ticket.

could this have been caused by my rebasing to develop?

[brettpim]

comment:35

Replying to @nathanncohen:

An incidence structure is group divisible iff its dual is resolvable so the is_resolvable method can be used to determine if the IS is group divisible. The question is if we find that a IS is group divisible, what do we want to do. Do we want to store the groups as a part fo the IS?

From your question I wonder if we are talking about the same thing. I was simply saying that we have a function is_group_divisible_design that tells you if an incidence structure is a group divisible design. Is that also what you have in mind?

It looks to me as if your is_group_divisible_design requires the user to hand the method the groups.

I was thinking of building a function to determine if an IS is group divisible without knowing what the groups might be.

I was slightly incorrect before. A more accurate statement would be that the dual of a resolvable IS is an group divisible IS with the property that the blocks are transversal.

It is important to note that neither may be designs.

This fact follows from dualising thew definition of resolvable:

A IS is resolvable if there exists a partition of the blocks into classes such that every point is incident with exactly one block in each class.

the dual of this statement is

there exists a partition of the points into classes (groups) such that every block is incident with exactly one point in each class (group)

In particular, I do not understand how that could be equivalent to finding out whether the dual is resolvable: we have a .is_resolvable function, but it is rather slow.

[nathanncohen]

comment:36

Hello,

It looks to me as if your is_group_divisible_design requires the user to hand the method the groups.

It does.

I was thinking of building a function to determine if a deign is group divisible without knowing what the groups might be.

Okay.

I was slightly incorrect before. A more accurate statement would be that the dual of a resolvable IS is an group divisible IS with the property that the blocks are transversal.

Oh, I see. I found it weird that there could exist a way to not solve the actual packing problem ;-)

Nathann

[sagetrac-git]

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

0c935a3

made TODO more precise

[sagetrac-git]

Changed commit from 13280d9 to 0c935a3

[nathanncohen]

comment:39

Hellooooooooooo again,

Some remarks follow... It is a bit long, which is one of the reasons why we try
to keep the patches 'focused'.. Sorry for that ^^;

• 'union' does not appear in the index of methods

• A 'the' is missing several times, e.g.: "Return complementary incidence
  structure."

• Sage's source code is not the right place to ask questions. What about turning
  this 'todo' into a trac ticket?

• It is not very efficient to look for an element in a list. You could do the
  following replacement for a better runtime:

-  if delete:
-      int_points = frozenset(int(x) for x in self._points if x not in points)
-  else:
-      int_points = frozenset(int(x) for x in points)
+  if delete:
+      int_points = frozenset(self._points).difference(points)
+  else:
+      int_points = frozenset(int(x) for x in points)

The same pattern appears several times.

• In the sentence {{{Specify whether the objective function is to maximize the
  cardinality of blocks in the packing}}}, could you say "is to maximize the
  number of blocks" instead? I believe that this could avoid confusion.

• The indentation of + # Maximum number of blocks is not correct by one
  space.

• The following replacement also makes the code simpler:

-            p.set_objective(p.sum([b[i]*len(self._blocks[i]) for i in range(self.num_blocks())]))
+            p.set_objective(p.sum([b[i]*len(bi) for i,bi in enumerate(self._blocks)]))

• We try to keep the LaTeX readable both in html form and in text form (for
  those who query the help from the command line) whenever possible. Could you
  replace "\mid" by "|" in your formulas? The latter is much easier to decrypt.

• In derived_incidence_structure a "
  neq" is wrongly displayed in the html
  version of the doc.

• The documentation of the derived incidence structure could be made easier to
  read as

  At **a point**: Given a [...]
  At **a block**: Given a [...]
  

• Isn't the derived incidence structure "at a block" equal to the trace of the
  incidence structure on that block? Is only 'B' missing?

• "Otherwise there is no guarantee that the derived incidence structure at a
  block is a block design": I do not think that this is actually necessary,
  though it is not very important.

• Could you specify in the INPUT section of derived_incidence_structure that
  exactly one of at_point and at_block must be defined?

• The documentation of a function is no place to ask questions on its desired
  behaviour. Please specify in the documentation how it behaves on multiple
  blocks if that troubles you. You can use a '.. NOTE' environment.

• If neither at_point nor at_block is specified, I would say that the
  correct behaviour is an exception. You can use the following pattern:

  if (at_point is None) + (at_block is None) != 1:
      raise ValueError("Exactly one of at_block and at_point must be specified")
  if at_point:
      <code>
  else:
      <code>
  

• if not(at_block in self.blocks()):: this can be rewritten as at_block not in self. It is less wasteful, as it does not build the list of blocks
  only to throw it away afterwards. In general not(a in b) is I believe
  equivalent to a not in b.

• residual_incidence_structure: the formulas do not appear correctly in the
  html doc, probably because of the '
  '.

• Could you specify in residual_incidence_structure and in
  derived_incidence_structure where those definitions are taken?

• supplementary_incidence_structure: again, testing containment in a list is
  slow. Could you use a set instead? Then, containment tests involve equality
  test: a==b is fast when a,b are integers but the points of an incidence
  structure may be arbitrary objects and their equality tests may be slower. It
  is best to work on the integers directly.

• complementary_incidence_structure: the iterators from itertools are usually
  faster than their 'combinat' counterpart. It is probably faster to use them:

  sage: list(combinations([1,2,3,4],2))
  [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
  

  Here again, it is better to work on integers directly.

• Do you think that it could be useful to add a 'simple' option to 'union'? It
  would return the union of the two structures while ignoring duplicated blocks.

• It feels a bit weird to carry the class' name in its methods' names. What
  about renaming 'supplementary_incidence_structure' to 'supplement',
  "residual_incidence_structure" to "residual", etc?..

Nathann

[sagetrac-git]

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

910b437

clean up, improve documentation readibility, added simple option to union, added repeated block choice to user in residual and derived, improved speed with sets and integer cals when sets not possible, shortened method names, added citation for residual and derived.

[sagetrac-git]

Changed commit from 0c935a3 to 910b437

[brettpim]

comment:41

How do I link the places I use the [Col2007] reference with its appearance in the reference list?

I did not change residual and derived to use trace because I thought they are probably fine as they are and deleting a block to create a new IS only to then call trace on it seemed not particularly efficient

I have done everything else.

[nathanncohen]

comment:42

Helloooooooo Brett,

• Replaced the links to [Col2007] to links toward the existing bibliographical
  entry [DesignHandbook]. In order to link toward a bibliographical entry, you
  must type '[DesignHandbook]_'.

• Replaced ``complementary`` (appears as Python code) with
  *complementary* appears in italic.

• Several lines contained what we call "trailing whitespaces". I removed them,
  which explains why some lines of my commit seem to make no modification at
  all.

• {{{int_points = frozenset(self._point_to_index[x] for x in
  points).difference(points)}}}: leads to that:

  sage: IncidenceStructure([['a','b','c']]).trace(['a','b']).blocks()
  [['a', 'b']]
  sage: IncidenceStructure([['a','b','c']]).trace(['a','b'],delete=True).blocks()
  [['a', 'b']]
  

  I fixed it and added a doctest.

• Please do not leave commented lines in the code (unless you think we might
  need them later), e.g.

  #        from sage.combinat.combination import Combinations                                                                                                                                       
  

• The following modifications is a bit incorrect, as what it describes is a pair
  of Python variables. I reverted it.

  -          ``(boolean_answer,(t,v,k,l))``.
  +          (boolean_answer,`(t,v,k,l)`).

• The implemented code of 'derived' does not match the definition. If there are
  repeated blocks you only remove one of them as you compare the indices. Do
  whatever you think is best, but please make the doc consistent with the
  implementation.

• derived (and some other functions I believe) do not handle non-integer
  ground sets:

  sage: IncidenceStructure([[1,2,3],['a','b','c'],['a','b']]).residual(at_block=['a','b','c'])
  ...
  ValueError: ['a', 'b', 'c'] is not in list
  

• keep_repeats -- is this keyword different from the simple keyword used
  elsewhere?

• These objects are incidence structures, thus the exceptions should not mention
  a 'design'.

• {{{
  sage: IncidenceStructure("abc",["ab"]).complement()
  Incidence structure with 3 points and 0 blocks
  }}}

I added a commit on top of yours at public/16534. Please mind corner-cases in
your code (e.g. empty list of blocks, non-integer labels) and what actually
happens in each command (useless copies of possibly big data).

Cheers,

Nathann