Clean IncidenceStructure #16553

videlec · 2014-06-26T12:25:09Z

In #16552 we discovered that IncidenceStructure is not adapted to deal with projective spaces. The class should be able:

to be a base class for inheritance to create other designs (like GDD or specialized one such as DesarguesianProjectivePlane)
... (maybe more)

see also: #16534

CC: @nathanncohen @brettpim

Component: combinatorial designs

Author: Nathann Cohen, Vincent Delecroix

Branch/Commit: 0698433

Reviewer: Nathann Cohen, Vincent Delecroix

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

The text was updated successfully, but these errors were encountered:

videlec · 2014-06-26T13:06:36Z

comment:1

Some more remarks:

I think we also want another bijection blocks <-> {0, ..., b-1} to have well defined incidence matrices. It would also help to choose proper labels for the dual incidence structure.
A better name for IncidenceStructure would be Design... and we also need a class for GroupDivisibleDesign and for them we need an other bijection groups <-> {0, ..., g-1}.

to fit with enumerated set the natural terminology for the bijection would be rank/unrank

class Design:
    def rank_point(self, point):    # index of ``point``
    def unrank_point(self, n):      # ``n``-th point
    def rank_block(self, block):    # index of ``block``
    def unrank_block(self, n):      # ``n``-th block

nathanncohen · 2014-06-26T13:14:29Z

comment:2

Yo !

I think we also want another bijection blocks <-> {0, ..., b-1} to have well defined incidence matrices. It would also help to choose proper labels for the dual incidence structure.

Well, the points of the dual incidence structure could be ... Sets ?.. Or tuples. I mean, the labels of the points of a dual incidence structure could be the blocks of the original incidence structure.

ANd of course, the blocks would be .. Sets of points from the ground set ?

That's what we want, isn't it ?

A better name for IncidenceStructure would be Design...

Or hypergraph ?... A friend of mine says "geometry" instead of "hypergraph". Truth it, an incidence structure is a pretty general thing :

http://en.wikipedia.org/wiki/Incidence_structure

and we also need a class for GroupDivisibleDesign and for them we need an other bijection groups <-> {0, ..., g-1}.

Well, we may need to have ".groups()" indeed. We would have GDD at the bottom, them PBD, BIBD, transversal designs...

The main problem is that orthogonal arrays are not really designs in this sense.

to fit with enumerated set the natural terminology for the bijection would be rank/unrank

class Design:
    def rank_point(self, point):    # index of ``point``
    def unrank_point(self, n):      # ``n``-th point
    def rank_block(self, block):    # index of ``block``
    def unrank_block(self, n):      # ``n``-th block

Really ? Ewww.. Honestly I'd be glad to avoid things like that and keep the integer names internal. Users do not need to see that !

Nathann

videlec · 2014-06-26T13:33:30Z

comment:3

Replying to @nathanncohen:

Yo !

I think we also want another bijection blocks <-> {0, ..., b-1} to have well defined incidence matrices. It would also help to choose proper labels for the dual incidence structure.

Well, the points of the dual incidence structure could be ... Sets ?.. Or tuples. I mean, the labels of the points of a dual incidence structure could be the blocks of the original incidence structure.

ANd of course, the blocks would be .. Sets of points from the ground set ?

This is confusing. Basically, we do not care too much about the data type of the blocks as soon as __len__, __iter__ and __contains__ are correctly implemented, right... But it does not work with dual.

One option is to do like posets where the ordering is implemented in the poset itself and not in the elements. We would implement the incidence structure at the level of IncidenceStructure and not at the level of points/blocks. In other words we would forbid p in block.

A better name for IncidenceStructure would be Design...

Or hypergraph ?... A friend of mine says "geometry" instead of "hypergraph". Truth it, an incidence structure is a pretty general thing :

http://en.wikipedia.org/wiki/Incidence_structure

Yes, we need Hypergraph.to_incidence_structure and IncidenceStructure.to_hypergraph... or only one class?

and we also need a class for GroupDivisibleDesign and for them we need an other bijection groups <-> {0, ..., g-1}.

Well, we may need to have ".groups()" indeed. We would have GDD at the bottom, them PBD, BIBD, transversal designs...

The main problem is that orthogonal arrays are not really designs in this sense.
to fit with enumerated set the natural terminology for the bijection would be rank/unrank
class Design:
    def rank_point(self, point):    # index of ``point``
    def unrank_point(self, n):      # ``n``-th point
    def rank_block(self, block):    # index of ``block``
    def unrank_block(self, n):      # ``n``-th block
Really ? Ewww.. Honestly I'd be glad to avoid things like that and keep the integer names internal. Users do not need to see that !

All right.

Vincent

nathanncohen · 2014-06-26T13:48:02Z

comment:4

This is confusing.

What is confusing ? That blocks are sets of points ? O_o

Basically, we do not care too much about the data type of the blocks as soon as __len__, __iter__ and __contains__ are correctly implemented, right... But it does not work with dual.

Why doesn't it work with duals ?

One option is to do like posets where the ordering is implemented in the poset itself and not in the elements. We would implement the incidence structure at the level of IncidenceStructure and not at the level of points/blocks. In other words we would forbid p in block.

............

Yeah, let's make it impossible to iterate on blocks. That will be better.

Yes, we need Hypergraph.to_incidence_structure and IncidenceStructure.to_hypergraph... or only one class?

Forget about hypergraphs for the moment. Nobody but I knows it exists, and it can do nothing useful except displaying stuff, and once more I am the only one who knows that it does that :-P

Incidence Structure will be the most basic thing we have. Then we will have GDD, then all we need above that.

Nathann

videlec · 2014-06-26T14:40:01Z

comment:5

Replying to @nathanncohen:

This is confusing.

What is confusing ? That blocks are sets of points ? O_o

No, that points are blocks of the dual!

Basically, we do not care too much about the data type of the blocks as soon as __len__, __iter__ and __contains__ are correctly implemented, right... But it does not work with dual.

Why doesn't it work with duals ?

Because the blocks of the duals are the point. And the dual of the dual is (canonically isomorphic) to the initial design.

One option is to do like posets where the ordering is implemented in the poset itself and not in the elements. We would implement the incidence structure at the level of IncidenceStructure and not at the level of points/blocks. In other words we would forbid p in block.

............

Yeah, let's make it impossible to iterate on blocks. That will be better.

All right, then we need a class DualDesign whose points and blocks would be wrappers. Is it what you want?

Vincent

nathanncohen · 2014-06-26T14:46:47Z

comment:6

All right, then we need a class DualDesign whose points and blocks would be wrappers. Is it what you want?

No. What I want is to stop trying to solve problems that already have an easy solution, especially when what you call "solving them" means sacrificing definitely useful stuff like being able to iterate on blocks. We can just make the .dual() function return a design along with a dictionary associating a vertex with the block it has become.

Nathann

videlec · 2014-06-26T15:19:49Z

comment:7

Replying to @videlec:

Replying to @nathanncohen:

This is confusing.

What is confusing ? That blocks are sets of points ? O_o

No, that points are blocks of the dual!

Basically, we do not care too much about the data type of the blocks as soon as __len__, __iter__ and __contains__ are correctly implemented, right... But it does not work with dual.

Why doesn't it work with duals ?

Because the blocks of the duals are the point. And the dual of the dual is (canonically isomorphic) to the initial design.

One option is to do like posets where the ordering is implemented in the poset itself and not in the elements. We would implement the incidence structure at the level of IncidenceStructure and not at the level of points/blocks. In other words we would forbid p in block.

............

Yeah, let's make it impossible to iterate on blocks. That will be better.

All right: what about intersection? do we want b1.intersection(b2) available?

nathanncohen · 2014-06-26T15:23:34Z

comment:8

All right: what about intersection? do we want b1.intersection(b2) available?

Why we would need that ?...

Nathann

videlec · 2014-06-26T15:31:34Z

comment:9

Replying to @nathanncohen:

All right: what about intersection? do we want b1.intersection(b2) available?

Why we would need that ?...

To compute the intersection numbers (see definition 1.5 of the Handbook).

nathanncohen · 2014-06-26T15:34:45Z

comment:10

To compute the intersection numbers (see definition 1.5 of the Handbook).

That's not a reason to restrict the input. If we need to compute stuff like that we can copy the data in whatever structure we need to make it go faster, but that is not sufficient to change the input of the whole class.

Nathann

videlec · 2014-06-26T21:32:55Z

Branch: public/16553

videlec · 2014-06-26T21:32:55Z

New commits:

`a5c4dbc`	`trac #16553: reimplement IncidenceStructure`

videlec · 2014-06-26T21:32:55Z

Commit: a5c4dbc

videlec · 2014-06-26T21:34:06Z

comment:12

I did not know what to do with def block_design_checker(self, t, v, k, lmbda, type=None):... help!

Vincent

nathanncohen · 2014-06-27T07:20:16Z

comment:13

Vincent, it would be cool if you could say what you did in there, because you do a thousand things at once and it is difficult to list them all while reading the patch. You should have done several thematic commits.

First, why do you rename BlockDesign to TDesign ? A GDD is not exactly a 2-design (although it's admittedly not far) so we will not be able to use TDesign as a base class for our methods later.

Then, things like "return len(self.blocks())" is criminal as it requires to build the whole list only to compute its lengths. Given that you are writing methods of the very class you are allowed to use private variables, you know ? :-P

You also seem to add methods and this should go into a different patch. Really, it is very hard to understand what you do here from the diff file, so it is not the place to ad new stuff that will have to be discussed.

You seem to remove classes without deprecation, like BlockDesign.

Nathann

videlec · 2014-06-27T07:46:09Z

comment:14

Replying to @nathanncohen:

Vincent, it would be cool if you could say what you did in there, because you do a thousand things at once and it is difficult to list them all while reading the patch. You should have done several thematic commits.

I can do that. But I am not sure you want to know the real history of my commits.

First, why do you rename BlockDesign to TDesign ? A GDD is not exactly a 2-design (although it's admittedly not far) so we will not be able to use TDesign as a base class for our methods later.

The definition of block design used in Sage is wrong. A block design is a synonym for incidence structure (as it can be checked on wikipedia or the Handbok of combinatorial designs). What was considered are t-designs for which you have well defined parameters t-(v,k,\lambda). It is a particular case of block design. Hopefully right now there is only one class and making BlockDesign = IncidenceStructure looks safe enough to me.

Then, things like "return len(self.blocks())" is criminal as it requires to build the whole list only to compute its lengths. Given that you are writing methods of the very class you are allowed to use private variables, you know ? :-P

Right!

You also seem to add methods and this should go into a different patch. Really, it is very hard to understand what you do here from the diff file, so it is not the place to ad new stuff that will have to be discussed.

The only stuff I added is just to simplify the is_t_design function (like t_indices, replication_numbers, etc).

You seem to remove classes without deprecation, like BlockDesign.

Nope. It is now a complete synonym of IncidenceStructure without any further check.

Vincent

nathanncohen · 2014-06-27T07:59:37Z

comment:15

Yo !

I can do that. But I am not sure you want to know the real history of my commits.

Not "the real history". That's why we create several patches for several things, and that's why we can add several commits in the same ticket : so that we may present the changes in a way that makes them easy to review. You didn't want to see the real history of my design commits eithers :-P

The definition of block design used in Sage is wrong. A block design is a synonym for incidence structure (as it can be checked on wikipedia or the Handbok of combinatorial designs). What was considered are t-designs for which you have well defined parameters t-(v,k,\lambda). It is a particular case of block design. Hopefully right now there is only one class and making BlockDesign = IncidenceStructure looks safe enough to me.

Well, right now tdesign returns an incidence structure too. Okay, one question : should we deprecate BlockDesign in favor of IncidenceStructure ? Also, it seems weird to have an upper case T in TDesign, given that this "t" is a variable.... What about tDesign ?

What I don't like about this is that we do not need a tDesign class at all, so why would we create one ? We create classes for the wrong reason and we have nothing to put in them.

The only stuff I added is just to simplify the is_t_design function (like t_indices, replication_numbers, etc).

I have never heard of "t indices" anywhere. Where did you find this terminology ? It just seems to be the degree of a point, taken as a hypergraph ...

Nathann

videlec · 2014-06-27T08:12:37Z

comment:16

Replying to @nathanncohen:

Yo !

The definition of block design used in Sage is wrong. A block design is a synonym for incidence structure (as it can be checked on wikipedia or the Handbok of combinatorial designs). What was considered are t-designs for which you have well defined parameters t-(v,k,\lambda). It is a particular case of block design. Hopefully right now there is only one class and making BlockDesign = IncidenceStructure looks safe enough to me.

Well, right now tdesign returns an incidence structure too. Okay, one question : should we deprecate BlockDesign in favor of IncidenceStructure ? Also, it seems weird to have an upper case T in TDesign, given that this "t" is a variable.... What about tDesign ?

What I don't like about this is that we do not need a tDesign class at all, so why would we create one ? We create classes for the wrong reason and we have nothing to put in them.

I propose to remove tDesign and have IncidenceStructure (in incidence_structure.py) and set BlockDesign = IncidenceStructure as an alias (in block_design.py).

The only stuff I added is just to simplify the is_t_design function (like t_indices, replication_numbers, etc).

I have never heard of "t indices" anywhere. Where did you find this terminology ? It just seems to be the degree of a point, taken as a hypergraph ...

Handbook definition I.1.5. If it is not standard I can change it. To me, degree looks more natural.

nathanncohen · 2014-06-27T08:14:43Z

comment:17

Yo !

I propose to remove tDesign and have IncidenceStructure (in incidence_structure.py) and set BlockDesign = IncidenceStructure as an alias (in block_design.py).

Works for me.

Handbook definition I.1.5. If it is not standard I can change it. To me, degree looks more natural.

+1 to degree. However having a "degree" method is a bit of a lie given that the data structure of IncidenceStructure is not at all meant to compute the degree of points... Unless we cache it ?

Nathann

videlec · 2014-06-27T08:15:48Z

comment:18

There is right now the possibility of having repeated elements in the blocks. The block_design_checker(binary=True) answers if it is. It is used nowhere... what should we do with that?

Vincent

nathanncohen · 2014-06-27T08:24:57Z

comment:19

Yo !

There is right now the possibility of having repeated elements in the blocks.

>_<

The block_design_checker(binary=True) answers if it is. It is used nowhere... what should we do with that?

Let's remove this. It does not appear in what is commonly accepted as an incidence structure. Those things are meant to be sets.

Nathann

videlec · 2014-06-27T08:26:55Z

comment:20

Another question: why steiner triple systems are incidence structure but quadruple ones are tuples of tuples? It is ugly in the doctest

sage: S3_9 = designs.steiner_triple_system(9)
sage: S3_9.is_t_design(return_parameters=True)
(True, [2, 9, 3, 1])

sage: blocks = designs.steiner_quadruple_system(8)
sage: S8 = designs.IncidenceStructure(8, blocks)
sage: S8.is_t_design(return_parameters=True)
(True, [3, 8, 4, 1])

nathanncohen · 2014-06-27T08:29:06Z

comment:21

Yo !

Another question: why steiner triple systems are incidence structure but quadruple ones are tuples of tuples? It is ugly in the doctest

Just because I hate classes. You can make them BlockDesign if you like, Dima will be happy too.

By the way, is_t_design is wrong as it is written. Turns out that you cannot write this function without "knowing" the value of t. There is no such thing as "the largest t such that a design is a t-design.

Nathann

vbraun · 2014-06-30T05:23:09Z

comment:138

There is another .points that was introduced in #16535

sagetrac-git · 2014-07-01T07:38:55Z

Changed commit from 3c0dd71 to 51476ff

sagetrac-git · 2014-07-01T07:38:55Z

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

`09a8a4b`	`trac #16553: merge #16535`
`8e45f07`	`trac #16553: deprecated alias for .points() + fix`
`51476ff`	`trac #16553: merge updated #16528`

videlec · 2014-07-01T07:39:57Z

comment:140

Needs review!

Vincent

nathanncohen · 2014-07-01T07:57:39Z

comment:141

apparently it does not apply on the latest release, the branch name's in red. Instead of merging tickets you should go back to trac #16553v3: change .points() -> .ground_set() and merge with beta5.

Nathann

sagetrac-git · 2014-07-01T08:06:39Z

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

`52b7177`	`trac #16553: merge sage 6.3.beta5`
`0698433`	`trac #16553: deprecated alias .points() + fix`

sagetrac-git · 2014-07-01T08:06:39Z

Changed commit from 51476ff to 0698433

nathanncohen · 2014-07-01T08:19:15Z

comment:144

For the tenth time ...

videlec · 2014-07-01T08:32:21Z

comment:145

Replying to @nathanncohen:

For the tenth time ...

and the last... (I hope)

vbraun · 2014-07-01T21:55:18Z

Changed branch from public/16553v3 to 0698433

videlec added this to the sage-6.3 milestone Jun 26, 2014

videlec added c: combinatorial designs labels Jun 26, 2014

videlec added the s: needs review label Jun 26, 2014

nathanncohen mannequin added s: needs info and removed s: needs review labels Jun 27, 2014

nathanncohen mannequin added s: positive review and removed s: needs review labels Jun 29, 2014

vbraun added s: needs work and removed s: positive review labels Jun 30, 2014

videlec added s: needs review and removed s: needs work labels Jul 1, 2014

nathanncohen mannequin added s: needs work and removed s: needs review labels Jul 1, 2014

videlec added s: needs review and removed s: needs work labels Jul 1, 2014

nathanncohen mannequin added s: positive review and removed s: needs review labels Jul 1, 2014

vbraun removed the s: positive review label Jul 1, 2014

vbraun closed this as completed in d3c2d68 Jul 1, 2014

brettpim mannequin mentioned this issue Dec 29, 2022

Basic Block design methods #16534

Open

This was referenced Dec 29, 2022

oval in finite projective plane #16552

Open

Singer difference set and fix OA_9_135 #16597

Closed

This was referenced Aug 11, 2014

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

Closed

Deprecate Hypergraph in favor of IncidenceStructure #16622

Closed

zabrocki mannequin mentioned this issue Nov 26, 2015

remove expired deprecations in sage/combinat #19513

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Clean IncidenceStructure #16553

Clean IncidenceStructure #16553

videlec commented Jun 26, 2014

videlec commented Jun 26, 2014

nathanncohen mannequin commented Jun 26, 2014

videlec commented Jun 26, 2014

nathanncohen mannequin commented Jun 26, 2014

videlec commented Jun 26, 2014

nathanncohen mannequin commented Jun 26, 2014

videlec commented Jun 26, 2014

nathanncohen mannequin commented Jun 26, 2014

videlec commented Jun 26, 2014

nathanncohen mannequin commented Jun 26, 2014

videlec commented Jun 26, 2014

videlec commented Jun 26, 2014

videlec commented Jun 26, 2014

videlec commented Jun 26, 2014

nathanncohen mannequin commented Jun 27, 2014

videlec commented Jun 27, 2014

nathanncohen mannequin commented Jun 27, 2014

videlec commented Jun 27, 2014

nathanncohen mannequin commented Jun 27, 2014

videlec commented Jun 27, 2014

nathanncohen mannequin commented Jun 27, 2014

videlec commented Jun 27, 2014

nathanncohen mannequin commented Jun 27, 2014

vbraun commented Jun 30, 2014

sagetrac-git mannequin commented Jul 1, 2014

sagetrac-git mannequin commented Jul 1, 2014

videlec commented Jul 1, 2014

nathanncohen mannequin commented Jul 1, 2014

sagetrac-git mannequin commented Jul 1, 2014

sagetrac-git mannequin commented Jul 1, 2014

nathanncohen mannequin commented Jul 1, 2014

videlec commented Jul 1, 2014

vbraun commented Jul 1, 2014

Clean IncidenceStructure #16553

Clean IncidenceStructure #16553

Comments

videlec commented Jun 26, 2014

videlec commented Jun 26, 2014

nathanncohen mannequin commented Jun 26, 2014

videlec commented Jun 26, 2014

nathanncohen mannequin commented Jun 26, 2014

videlec commented Jun 26, 2014

nathanncohen mannequin commented Jun 26, 2014

videlec commented Jun 26, 2014

nathanncohen mannequin commented Jun 26, 2014

videlec commented Jun 26, 2014

nathanncohen mannequin commented Jun 26, 2014

videlec commented Jun 26, 2014

videlec commented Jun 26, 2014

videlec commented Jun 26, 2014

videlec commented Jun 26, 2014

nathanncohen mannequin commented Jun 27, 2014

videlec commented Jun 27, 2014

nathanncohen mannequin commented Jun 27, 2014

videlec commented Jun 27, 2014

nathanncohen mannequin commented Jun 27, 2014

videlec commented Jun 27, 2014

nathanncohen mannequin commented Jun 27, 2014

videlec commented Jun 27, 2014

nathanncohen mannequin commented Jun 27, 2014

vbraun commented Jun 30, 2014

sagetrac-git mannequin commented Jul 1, 2014

sagetrac-git mannequin commented Jul 1, 2014

videlec commented Jul 1, 2014

nathanncohen mannequin commented Jul 1, 2014

sagetrac-git mannequin commented Jul 1, 2014

sagetrac-git mannequin commented Jul 1, 2014

nathanncohen mannequin commented Jul 1, 2014

videlec commented Jul 1, 2014

vbraun commented Jul 1, 2014