New empty design classes for a better user interface and new is_group_divisible_design Cython function

[nathanncohen]

This branch defines:

• GroupDivisibleDesign
• PairwiseBalancedDesign
• BalancedIncompleteBlockDesign
• TransversalDesign

All these classes (which inherit from IncidenceStructure) make it easier to do things like compute the automorphism_group of a transversal design.

The branch also adds a function is_group_divisible_design in designs_pyx.pyx, and an empty is_pairwise_balanced_design that call it. We can thus get rid of the ugly _check_pbd.

Nathann

Depends on #16553
Depends on #16766

CC: @videlec

Component: combinatorial designs

Author: Nathann Cohen

Branch/Commit: 5f1fb98

Reviewer: Vincent Delecroix

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

[nathanncohen]

Branch: u/ncohen/16553

[nathanncohen]

Commit: ff72248

[nathanncohen]

New commits:

ff72248

trac #16553: Clean IncidenceStructure

[nathanncohen]

Dependencies: #16553

[nathanncohen]

Changed branch from u/ncohen/16553 to u/ncohen/16598

[nathanncohen]

New commits:

4dc250a	trac #16553: Clean IncidenceStructure
bd609fc	trac #16553: is_t_design
11994ef	trac #16553: Review
e7a97ea	trac #16553: doc fix + deprecation is_block_design
3c0dd71	trac #16553v3: change .points() -> .ground_set()
52b7177	trac #16553: merge sage 6.3.beta5
0698433	trac #16553: deprecated alias .points() + fix
1575f31	trac #16598: Useless new classes and a replacement for _check_pbd

[nathanncohen]

Changed commit from ff72248 to 1575f31

[sagetrac-git]

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

cdaf1e2

trac #16598: Useless new classes and a replacement for _check_pbd

[sagetrac-git]

Changed commit from 1575f31 to cdaf1e2

[videlec]

comment:4

Hey Nathann,

In group divisible design, there must be more parameters:

• v the size of the ground set
• K the admissible size of the blocks
• G the admissible size of the groups
  The definition seems to be standard (see the big paper of Hanani and the definition IV.1.3 of the Handbook)

Anyway, GDD is just a strict generalization of PBD and it is very clear from Handbook IV.1.3.
That way, your is_pbd would just be a lambda function.

Actually, it would be nicer that IncidenceStructure would actually be a GroupDivisibleDesign (groups being the partition into points). The points can be ordered in such way that the groups are

0 1 ... g1-1|g1 g1+1 ... g1+g2-1|...

and then the new class would just need an extra ._group_sizes attribute that would be an integer partition.

Some methods are not well adapted to group divisible designs

• dual: is the dual well defined for GDD?
• incidence_matrix: must be the incidence matrix group/block (or put a flag allowing to have points/blocks)
• automorphis_group is wrong since it must preserver the groups

Why do you use tuples where everywhere in IncidenceStructure there are lists?

Would you mind having a "stupid" .group_sizes() method?

Vincent

[videlec]

comment:5

Note that a solution for computing the automorphism group is as follows:

1. compute the automorphism group of the partition into groups (the generators can be provided by hand, and I can provide a function for it)
2. compute the automorphism group of the block design (ie forget about the groups)
3. make the intersection

I think that it is not that bad in terms of efficiency.

Vincent

[nathanncohen]

comment:6

Yo !

In group divisible design, there must be more parameters:

• v the size of the ground set
• K the admissible size of the blocks
• G the admissible size of the groups
  The definition seems to be standard (see the big paper of Hanani and the definition IV.1.3 of the Handbook)

Seems more than we need at the moment, but okay ...

Anyway, GDD is just a strict generalization of PBD and it is very clear from Handbook IV.1.3.
That way, your is_pbd would just be a lambda function.

lambda functions have no documentation. But yes, the code just takes one line.

Actually, it would be nicer that IncidenceStructure would actually be a GroupDivisibleDesign (groups being the partition into points). The points can be ordered in such way that the groups are

0 1 ... g1-1|g1 g1+1 ... g1+g2-1|...

and then the new class would just need an extra ._group_sizes attribute that would be an integer partition.

Until we want GDD to be defined on something different than 0,...,n-1 just like you did for IncidenceStructure

Some methods are not well adapted to group divisible designs

• dual: is the dual well defined for GDD?

Given that the GDD is a set of blocks, why not ? Plus you wanted two lines above that GDD be equal to an IncidenceStructure.

• incidence_matrix: must be the incidence matrix group/block (or put a flag allowing to have points/blocks)

Why ?

• automorphis_group is wrong since it must preserver the groups

Then the implementation is correct.

Why do you use tuples where everywhere in IncidenceStructure there are lists?

Would you mind having a "stupid" .group_sizes() method?

Yes, I hate those methods. Write it if you want one.

Nathann

[sagetrac-git]

Changed commit from cdaf1e2 to 3f8cebb

[sagetrac-git]

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

3f8cebb

trac #16598: G and K as arguments of GDD

[nathanncohen]

comment:9

Then the implementation is correct.

i.e. an automorphism send a non-covered pair of vertices u,v on another non-covered pair of vertices u,v. So a group is sent on another group with the same cardinality.

It corresponds to the notion of automorphism group you expect for BIBD (K=[1]), and it also corresponds to the notion of group that you expect on transversal designs (K=[k]).

Nathann

[videlec]

comment:10

I got it for the automorphism group! Thanks. But your definition of gdd is wrong: any pair of points is either in a group or in lambda blocks but not both. And this is why the blocks completely determine the groups: two points are in the same group if they are not in a block!

What do you think of having only one class (with blocks and groups) and methods:

• .is_t_design(self,t,v,k,l)
• .is_group_divisible_design(self,v,G,K,l)
• .is_partially_balanced_design(self,v,K,l)
  I do not like the fact of having one extra empty class whose only purpose is a check at creation... Moreover, if we switch to mutable classes it would be cool that after transformations we check the kind of thing we obtain. The only thing that bother me a little bit is this dual method which does not make any sense for groups (perhaps it does??).

Why do you not translate the groups over integers as it is the case for blocks?

You really like to use tuple of tuples for groups and list of lists for blocks (see comment:4 above)?

Vincent

[nathanncohen]

comment:11

Hello !

I got it for the automorphism group! Thanks. But your definition of gdd is wrong:

Ahahahahah. Well, that's what I intended, but... is the new version clearer ?

What do you think of having only one class (with blocks and groups) and methods:

• .is_t_design(self,t,v,k,l)
• .is_group_divisible_design(self,v,G,K,l)
• .is_partially_balanced_design(self,v,K,l)

How would you call the class ? If you want to have these functions as methods of something, the only choice I see is IncidenceStructure. We would have no .groups() method but those functions could get the groups as an argument.

I do not like the fact of having one extra empty class whose only purpose is a check at creation...

I just created GDD because it was the common generalization of TD and PBD. Mostly for the doc at the moment, and we will have some place to put code that works on groups.

Moreover, if we switch to mutable classes it would be cool that after transformations we check the kind of thing we obtain.

Hmmmm... I don't expect that GDD or anything that inherits from it will ever be mutable. IncidenceStructure could be mutable someday, though. It wouldn't be cool to have a GDD object which is not a GDD. Plus as you noticed, most of these objects are created from others, rarely modified inplace.

The only thing that bother me a little bit is this dual method which does not make any sense for groups (perhaps it does??).

Well, it just does not consider them. To me those "groups" are a parameter of the design, nothing else... The dual of a dual of a GDD is a GDD, so everything is cool. The blocks are forgotten (they can be re-computed automatically anyway), but who cares ? I don't think that you would find any other definition of the dual of a GDD anywhere...

Why do you not translate the groups over integers as it is the case for blocks?

Oh. I thought that I would only define GDD for integer ground set, but indeed it also handles the non-integer case almost for free as we know that "._blocks" are already translated to integers. You are right. I will updated that in a second.

You really like to use tuple of tuples for groups and list of lists for blocks (see comment:4 above)?

I don't understand. .groups() returns lists at the moment (before my commit)

def groups(self):
    return map(list,self._groups)

Oh, I see ! You meant for internal storage ! Fixed in the new commit.

Nathann

P.S. : While writing the commit, I made IncidenceStructure mutable. But it's not reaaaaaaaaaaallly a problem, it preserves all the structure ! :-D

[nathanncohen]

comment:40

Could we move _relabel_bibd as a method of BalancedIncompleteBlockDesign?

Hmmmm.. Well, it woud mean that we have to build BIBD objects during the recursive constructions too... I'd prefer to keep it this way if you don't mind :-/

(not very important) Why did you put the classes PairwiseBalancedDesign and BalancedIncompleteBlockDesign in the file bibd.py and not in incidence_structure.py? I am not sure about what is the best organization should be, but right now it is not clear at all where to look to find something.

Well, that BalancedIncompleteBlockDesign is defined is bibd.py is hardly a surprise. I feel that PBD are very close to BIBD but indeed, if GDD are in IncidenceStructure then indeed it can be moved there. What do you think ?

Nathann

[sagetrac-git]

Changed commit from 8a44b83 to ea8b144

[sagetrac-git]

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

ea8b144

trac #16598: Code simplification

[videlec]

comment:42

Replying to @nathanncohen:

YOoooooooo !

1. There is a problem with your relabel method

Gloops. Sorry 'bout that :-/

There is still a subtle issue. When we ask for a relabeling we do not necessarily want to relabel the points. More precisely, if the ground set is {0,1,2,3} and I want to relabel {0:1, 1:3, 2:1, 3:0} I would like the ground set to be fixed and the blocks to be changed... what do you think?

3. This is very bad

round(sqrt(len(blocks)))

(i.e. it involves the symbolic ring).

Is it bad to involve the symbolic ring ? O_o

Yes: SR is very slow and unreliable (though for sqrt of integers it should be ok).

Vincent

[videlec]

comment:43

updated version at u/vdelecroix/16598 (above 6.3.rc1 and #16766)

Vincent

[nathanncohen]

comment:44

Yoooooooo !!

There is still a subtle issue. When we ask for a relabeling we do not necessarily want to relabel the points. More precisely, if the ground set is {0,1,2,3} and I want to relabel {0:1, 1:3, 2:1, 3:0} I would like the ground set to be fixed and the blocks to be changed... what do you think?

I don't understand. You are just relabeling with the same ground sets, what's the problem with that ? And how does that badly affect the blocks ? Some will change, some will not, what's the problem ?

Yes: SR is very slow and unreliable (though for sqrt of integers it should be ok).

"Bôf". If it does not work it's a bug report, and if Sage cannot compute square roots safely we should fork it quick :-P

Nathann

[nathanncohen]

Changed commit from ea8b144 to 1a9ae44

[nathanncohen]

New commits:

081aa8b	trac #16598: merge with 6.3.rc1
49ae09d	trac #16766: Improve the doc of combinat/designs/
d626290	trac #16766: we don t want designs.deprecated_function_alias
8f9ee77	trac #16766: Broken doctests
47cebb3	trac #16766: Broken doctest
6cda4b6	trac #16766: Git 101: How to create a conflict with 10 others patches in needs_review
06e330b	trac #16766: form -> from
1a9ae44	trac #16598: merge #16766 (documentation update)

[nathanncohen]

Changed branch from u/ncohen/16598 to u/vdelecroix/16598

[videlec]

Changed dependencies from #16553 to #16553, #16766

[videlec]

comment:47

Replying to @nathanncohen:

Yoooooooo !!

There is still a subtle issue. When we ask for a relabeling we do not necessarily want to relabel the points. More precisely, if the ground set is {0,1,2,3} and I want to relabel {0:1, 1:3, 2:1, 3:0} I would like the ground set to be fixed and the blocks to be changed... what do you think?

I don't understand. You are just relabeling with the same ground sets, what's the problem with that ? And how does that badly affect the blocks ? Some will change, some will not, what's the problem ?

sage: I = IncidenceStructure(4,[[0,1,2],[1,3]])
sage: I.ground_set()
[0, 1, 2, 3]
sage: I.relabel({0:3,1:2,2:1,3:0})
sage: I.ground_set()
[3, 2, 1, 0]

the ground set has changed...

Vincent

[nathanncohen]

comment:48

Yooooo !

sage: I = IncidenceStructure(4,[[0,1,2],[1,3]])
sage: I.ground_set()
[0, 1, 2, 3]
sage: I.relabel({0:3,1:2,2:1,3:0})
sage: I.ground_set()
[3, 2, 1, 0]

the ground set has changed...

Well, as a list it has, not as a set...

I think that being smart here only raises new problems. Relabelling all blocks takes much more time and memory than relabelling the points only. We could hide that by returning a sorted list of points, but well...

Nathann

[videlec]

comment:49

Hello,

All right, we will see in the future.

Vincent

[vbraun]

comment:51

Reviewer name

[videlec]

Reviewer: Vincent Delecroix

[nathanncohen]

Changed branch from u/vdelecroix/16598 to public/16598

[nathanncohen]

New commits:

5f1fb98

trac #16598: Merged with 6.3

[nathanncohen]

Changed commit from 1a9ae44 to 5f1fb98

[vbraun]

Changed branch from public/16598 to 5f1fb98