Opened 7 years ago

Closed 7 years ago

# Clean IncidenceStructure

Reported by: Owned by: vdelecroix major sage-6.3 combinatorial designs ncohen, brett Nathann Cohen, Vincent Delecroix Nathann Cohen, Vincent Delecroix N/A 0698433 (Commits) 0698433258c4f863cc1585ece2065b5e4e1b41eb

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)

### comment:1 follow-up: ↓ 2 Changed 7 years ago by vdelecroix

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


### comment:2 in reply to: ↑ 1 ; follow-up: ↓ 3 Changed 7 years ago by ncohen

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 :

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

### comment:3 in reply to: ↑ 2 ; follow-up: ↓ 4 Changed 7 years ago by vdelecroix

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 :

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

Last edited 7 years ago by vdelecroix (previous) (diff)

### comment:4 in reply to: ↑ 3 ; follow-up: ↓ 5 Changed 7 years ago by ncohen

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

### comment:5 in reply to: ↑ 4 ; follow-ups: ↓ 6 ↓ 7 Changed 7 years ago by vdelecroix

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

### comment:6 in reply to: ↑ 5 Changed 7 years ago by ncohen

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

### comment:7 in reply to: ↑ 5 ; follow-up: ↓ 8 Changed 7 years ago by vdelecroix

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?

### comment:8 in reply to: ↑ 7 ; follow-up: ↓ 9 Changed 7 years ago by ncohen

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

Why we would need that ?...

Nathann

### comment:9 in reply to: ↑ 8 ; follow-up: ↓ 10 Changed 7 years ago by vdelecroix

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

### comment:10 in reply to: ↑ 9 Changed 7 years ago by ncohen

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

### comment:11 Changed 7 years ago by vdelecroix

• Branch set to public/16553
• Commit set to a5c4dbc9d1b77315d90dd3dd7a8ccea780f59ecf
• Status changed from new to needs_review

New commits:

 ​a5c4dbc trac #16553: reimplement IncidenceStructure

### comment:12 Changed 7 years ago by vdelecroix

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

Vincent

### comment:13 follow-up: ↓ 14 Changed 7 years ago by ncohen

• Status changed from needs_review to needs_info

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

### comment:14 in reply to: ↑ 13 ; follow-up: ↓ 15 Changed 7 years ago by vdelecroix

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

### comment:15 in reply to: ↑ 14 ; follow-up: ↓ 16 Changed 7 years ago by ncohen

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

### comment:16 in reply to: ↑ 15 ; follow-up: ↓ 17 Changed 7 years ago by vdelecroix

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.

### comment:17 in reply to: ↑ 16 Changed 7 years ago by ncohen

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

### comment:18 follow-up: ↓ 19 Changed 7 years ago by vdelecroix

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

### comment:19 in reply to: ↑ 18 Changed 7 years ago by ncohen

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

### comment:20 follow-up: ↓ 21 Changed 7 years ago by vdelecroix

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])


### comment:21 in reply to: ↑ 20 ; follow-up: ↓ 22 Changed 7 years ago by ncohen

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

### comment:22 in reply to: ↑ 21 ; follow-up: ↓ 23 Changed 7 years ago by vdelecroix

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.

Why not? It is well defined as soon as t is assumed to be smaller than the block size. Note that if you have a t-(v,k,lambda) design it is also a s-(v,k,lambda_s) design with

lambda_s = lambda binomial(v-s,t-s) / binomial(k-s,t-s).


(Handbook theorem II.4.8)

I think that we should forbid lambda=0, that's all.

### comment:23 in reply to: ↑ 22 ; follow-up: ↓ 28 Changed 7 years ago by ncohen

Why not? It is well defined as soon as t is assumed to be smaller than the block size. Note that if you have a t-(v,k,lambda) design it is also a s-(v,k,lambda_s) design with

lambda_s = lambda binomial(v-s,t-s) / binomial(k-s,t-s).


(Handbook theorem II.4.8)

I think that we should forbid lambda=0, that's all.

Hmmmmmm... Makes total sense, sorry O_o

Nathann

### comment:24 follow-up: ↓ 25 Changed 7 years ago by ncohen

Also, what would you think of deprecating dual_design and dual_incidence_structure in favor of... .dual() ?

Nathann

### comment:25 in reply to: ↑ 24 Changed 7 years ago by vdelecroix

Also, what would you think of deprecating dual_design and dual_incidence_structure in favor of... .dual() ?

Nathann

I would love that!

### comment:26 follow-up: ↓ 27 Changed 7 years ago by ncohen

Also, do you know where on earth IncidenceStructure.args, IncidenceStructure.keywords and IncidenceStructure.func come from ? O_O;;;;

Nathann

### comment:27 in reply to: ↑ 26 ; follow-up: ↓ 29 Changed 7 years ago by vdelecroix

Also, do you know where on earth IncidenceStructure.args, IncidenceStructure.keywords and IncidenceStructure.func come from ? O_O;;;;

might be the SageObject. I can remove the inheritance.

### comment:28 in reply to: ↑ 23 Changed 7 years ago by vdelecroix

Why not? It is well defined as soon as t is assumed to be smaller than the block size. Note that if you have a t-(v,k,lambda) design it is also a s-(v,k,lambda_s) design with

lambda_s = lambda binomial(v-s,t-s) / binomial(k-s,t-s).


(Handbook theorem II.4.8)

I think that we should forbid lambda=0, that's all.

Hmmmmmm... Makes total sense, sorry O_o

And actually:

• a design whose blocks have all the same lenght is a 0-design
• a 0-design for which each point has the same degree is a 1-design

I should modify the function to take care of that...

### comment:29 in reply to: ↑ 27 Changed 7 years ago by ncohen

might be the SageObject. I can remove the inheritance.

Good idea ! It will also remove these 9 functions we don't need

SageObject.category    SageObject.dump        SageObject.mro         SageObject.reset_name  SageObject.version
SageObject.db          SageObject.dumps       SageObject.rename      SageObject.save


Nathann

### comment:30 Changed 7 years ago by git

• Commit changed from a5c4dbc9d1b77315d90dd3dd7a8ccea780f59ecf to 6cc8889f344f5cefb72ed123190838b25487ce4e

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

 ​6cc8889 trac #16553: reimplement IncidenceStructure

### comment:31 Changed 7 years ago by vdelecroix

Hi Nathann,

As I completely rewrote the infrastructure it does not make much sense to have separated commits. I decided to implement a t_design_parameters (as a cached method) and a is_t_design. It is much more readable that way.

I am not sure what to do with the caching of degrees... for sure we do not want to do it on startup. And for now, as the datastructure is still in basic state I vote for keeping it the way it is. If we will cache it in the future then we should remove the @cached_method on t_design_parameters.

Neeeeeds review!

Vincent

### comment:32 Changed 7 years ago by vdelecroix

• Status changed from needs_info to needs_review

### comment:33 Changed 7 years ago by git

• Commit changed from 6cc8889f344f5cefb72ed123190838b25487ce4e to 9243ef16bf0e7ad800bca41fa6d5001042859d76

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

 ​3e01acb trac #16430: micro improvements ​81b9448 trac #16430: put back the seealso ​0fa89d5 trac #16347: Wilson's construction with two truncated groups ​828ff22 trac #16437: cut the branches in W. dec. with two trunc. blocks ​8ebd21b trac #16347: use is_sum_of_squares_pyx instead of two_squares ​0175134 trac #16347: doc + simplifications ​0d79982 trac #16446: merge #16347 ​6559eec trac #16446: fix doctest ​16a0c5d trac #16446: use deprecated_function_alias instead ​9243ef1 trac #16553: merge #16446

### comment:34 Changed 7 years ago by vdelecroix

there was small conflicts with #16446 so I did the merge.

### comment:35 Changed 7 years ago by ncohen

First passe review:

• Deprecated argument for BlockDesign(test=...)
• _relabel_bibd(BalancedIncompleteBlockDesign(N,k).blocks(),N) remove .blocks(), avoids a copy
• is_block_design -> t_design_parameters O_o ??? is_t_design ?
• Why remove OA_to_projective_plane ?
• Why this ?
-    A 3-design::
-
-        sage: D = IncidenceStructure(range(32),designs.steiner_quadruple_system(32))
-        sage: D.is_block_design()
-        (True, [3, 32, 4, 1])

• lines t_design_parameters with an optional flag ? Why ?
• WHy this ?
-        sage: BD = designs.WittDesign(12)  # optional - gap_packages (design package)
-        sage: BD.is_block_design()         # optional - gap_packages (design package)
-        (True, [5, 12, 6, 1])

• IncidenceStructure(matrix) broken ?
• function that builds *and* incidence structure from a matrix
• The doc of IncidenceStructure? needs an INPUT block. It is useless to have one in __init__, nobody sees it and it does not appear in the html doc.
• "point -- the points" is not very informative. Especially when you handle integers or iterables.
• Instead of doing
+            for i in range(b):
+                for j in range(v):
+                    if not M[j,i].is_zero():
+                        blocks[i].append(j)


You can use matrix methods, like rows() columns() dans their to_dictionary() function (you get the nonzero entries easily)

• self.points() == other.points() and self.blocks() == other.blocks() : compare private variables immediately, possibly avoids a copy
• What is the point of __ne__ when you have __eq__ ?
• points() and blocks() for the classes I am implementing I thought we should make them COPY the data instead of return it immediately by default, otherwise the users can change what is inside of them. With a copy=False flag to prevent this. What do you think ?
• replication_number -> degree ?
• intersection_number -> needs a definition
• intersection_number -> use itertools.combination
• Note that the dual of a block design may not be a block design. --> ?
• replication_number, intersection_number, degrees --> another ticket. By the way, the implementation of degrees is ridiculous. Think of the algorithmics behind instead of using fancy "reduce" functions.
• is_t_design and t_design_parameters should be the same function. Let's just have optional t,v,k,l parameters in is_t_design.

Nathann

### comment:36 Changed 7 years ago by ncohen

• Status changed from needs_review to needs_work

### comment:37 Changed 7 years ago by git

• Commit changed from 9243ef16bf0e7ad800bca41fa6d5001042859d76 to 428113c0bef095a97189239435c6fb4a92dbe099

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

 ​0883515 trac #16553: reviewer comments 1 ​c7d3e79 trac #16553: better degree implementation ​428113c trac #16553: remove t_design_parameters

### comment:38 follow-up: ↓ 39 Changed 7 years ago by vdelecroix

I adressed the issues you mentioned. I only answer to those for which there was a problem

• _relabel_bibd(BalancedIncompleteBlockDesign(N,k).blocks(),N) remove .blocks(), avoids a copy

done. But it is not clear to me:

• are we allowed to modify the output of blocks?
• are we allowed to modify the output of __iter__?

If both answers are yes, then there are copy anyway (I did not implement the copy=False idea).

• Why remove OA_to_projective_plane ?

Sorry, I should have said this: it was *completely* broken!!

• Why this ?
-    A 3-design::
-
-        sage: D = IncidenceStructure(range(32),designs.steiner_quadruple_system(32))
-        sage: D.is_block_design()
-        (True, [3, 32, 4, 1])


It has nothing to do here (in the doc of AffineGeometryDesign).

• Why this ?
-        sage: BD = designs.WittDesign(12)  # optional - gap_packages (design package)
-        sage: BD.is_block_design()         # optional - gap_packages (design package)
-        (True, [5, 12, 6, 1])


The same test above is copied I guess 5 times all over the place.

• What is the point of __ne__ when you have __eq__ ?

It is not automatically set up to not __eq__. You should learn your python

sage: class A(object):
....:     def __eq__(self, other):
....:         return True
....:
sage: a = A()
sage: b = A()
sage: a == b
True
sage: a != b
True


• IncidenceStructure(matrix) broken ?

It was. Now if the input is a matrix there is a check

• replication_number -> degree ?

removed, it was equivalent to .degrees(1)

• intersection_number -> needs a definition
• intersection_number -> use itertools.combination

removed, it was equivalent to .degrees(2)

• replication_number, intersection_number, degrees --> another ticket. By the way, the implementation of degrees is ridiculous. Think of the algorithmics behind instead of using fancy "reduce" functions.

degrees can not be in another commit since it is used in .is_t_design. I implemented a more reasonable version (but a bit ugly because of the cached_method over an iterator...)

Vincent

### comment:39 in reply to: ↑ 38 Changed 7 years ago by ncohen

Yo !

done. But it is not clear to me:

• are we allowed to modify the output of blocks?
• are we allowed to modify the output of __iter__?

If both answers are yes, then there are copy anyway (I did not implement the copy=False idea).

The point is that we cannot cache any answer unless the design is immutable. Then, if it is immutable we can do things like store the blocks internally as tuples. This way we can write __iter__ by returning the blocks directly, and they will not be modified by the user.

For .blocks(), we can (by default) return a copy of them or (if the user asks) return the thing directly.

Ideally, we could have copy=True/False arguments in the constructor and in blocks(). This way, if the user (=us, the developpers) say copy=False it means that we know that we are doing and that no copy occurs.

We can also do this when we compute a design without this class wrapping, then return the design. We can set copy=False and return the new design as we know that nobody else will modify the lists afterwards.

Sorry, I should have said this: it was *completely* broken!!

And it wasn't used anywhere ? Why on earth did we write this in the first place ? O_o

It has nothing to do here (in the doc of AffineGeometryDesign).

Okay

The same test above is copied I guess 5 times all over the place.

Okay.

Those two things are the kind of stuff that is pretty hard to find out while looking at the diff file unless you explain it....

• IncidenceStructure(matrix) broken ?

It was. Now if the input is a matrix there is a check

Okayyy...

degrees can not be in another commit since it is used in .is_t_design.

This function was already implemented before.

Nathann

### comment:40 Changed 7 years ago by ncohen

It all looks good to me, thanks for all the work ! There is only this degrees thing to solve now. I don't believe that we should have such a function. The "degree" is usually defined for a point. You can define it for larger things, but certainly not make it the default... Especially when you don't have a way to compute the degree of a vertex..

I mean.. Really, that's an internal function ...

Nathann

### comment:41 Changed 7 years ago by ncohen

About _degree_iterator(self): : I have no idea of what this function does, there is absolutely no documentation.

About _t_design_parameters and is_t_design : if I want to know whether my design is a 2-design, I sure as hell don't want Sage to beging enumerating 5-tuples, even if my design is a 5-design.

Nathann

### comment:42 follow-up: ↓ 43 Changed 7 years ago by ncohen

By the way I do not get what you want to do with this "degrees" function. The work was already done in the previous version of this function. Why did you break it into a "degrees" function ?

That's why it is good to explain what you do in the commits. I mean. Yeah, why did you break this function ? What was wrong with it ?

Nathann

### comment:43 in reply to: ↑ 42 ; follow-up: ↓ 44 Changed 7 years ago by vdelecroix

Yo !

done. But it is not clear to me:

• are we allowed to modify the output of blocks?
• are we allowed to modify the output of __iter__?

If both answers are yes, then there are copy anyway (I did not implement the copy=False idea).

The point is that we cannot cache any answer unless the design is immutable. Then, if it is immutable we can do things like store the blocks internally as tuples. This way we can write __iter__ by returning the blocks directly, and they will not be modified by the user.

For .blocks(), we can (by default) return a copy of them or (if the user asks) return the thing directly.

Ideally, we could have copy=True/False arguments in the constructor and in blocks(). This way, if the user (=us, the developpers) say copy=False it means that we know that we are doing and that no copy occurs.

We can also do this when we compute a design without this class wrapping, then return the design. We can set copy=False and return the new design as we know that nobody else will modify the lists afterwards.

Easiest way: store everything as tuple of tuples. Is it ok for you?

About _degree_iterator(self): : I have no idea of what this function does, there is absolutely no documentation.

About _t_design_parameters and is_t_design : if I want to know whether my design is a 2-design, I sure as hell don't want Sage to beging enumerating 5-tuples, even if my design is a 5-design.

agreed. I will modify that.

By the way I do not get what you want to do with this "degrees" function. The work was already done in the previous version of this function. Why did you break it into a "degrees" function ?

I thought it might be useful to have degrees. But on the other hand, you are right, it is not very nice within this datastructure.

That's why it is good to explain what you do in the commits. I mean. Yeah, why did you break this function ? What was wrong with it ?

It was badly implemented. You can cut the last loop on t quickly most of the time.

Vincent

### comment:44 in reply to: ↑ 43 Changed 7 years ago by ncohen

Easiest way: store everything as tuple of tuples. Is it ok for you?

Yeah yeah but it would be nice to not HAVE to copy stuff if we don't want to... I hate classes T_T

It was badly implemented. You can cut the last loop on t quickly most of the time.

Isn't it possible to just fix that ?..

Nathann

### comment:45 Changed 7 years ago by git

• Commit changed from 428113c0bef095a97189239435c6fb4a92dbe099 to d69700920609cd6112d2496b8858f94da3642531

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

 ​d697009 trac #16553: make everything tuples and hide _degree stuff

### comment:46 follow-up: ↓ 48 Changed 7 years ago by vdelecroix

Hi Nathann,

Everything are now tuples of tuples. I do not know how to do cleaner for is_t_design rather than having three cached method. If you see let me know. The previous version was broken in several places.

Vincent

### comment:47 Changed 7 years ago by vdelecroix

• Status changed from needs_work to needs_review

### comment:48 in reply to: ↑ 46 ; follow-up: ↓ 52 Changed 7 years ago by ncohen

Everything are now tuples of tuples.

WHYYYYYYYYYYYYYYYYYYYYY everything ?????? Even incomplete_orthogonal_array ? WHy ???? And why steiner triple systems too ????

Why not only what belongs to a mutable class or is cached ?

This does not maky ANY sense :

self._points = tuple(range(v))


Why are you converting this to a tuple given that you created it yourself ? Nobody will change it !

I do not know how to do cleaner for is_t_design rather than having three cached method. If you see let me know. The previous version was broken in several places.

Tell me where.

Nathann

### comment:49 follow-up: ↓ 50 Changed 7 years ago by ncohen

I mean : tell me where the function which is implemented in the last release of Sage is broken. And why you broke it into several functions, i.e. the question from comment:42.

Nathann

### comment:50 in reply to: ↑ 49 ; follow-up: ↓ 51 Changed 7 years ago by vdelecroix

• Status changed from needs_review to needs_work

I mean : tell me where the function which is implemented in the last release of Sage is broken. And why you broke it into several functions, i.e. the question from comment:42.

This one is a 0-(4,0,3) design

sage: I = IncidenceStructure(range(4), [[],[],[]])
sage: I.is_block_design()
(False, [0, 0, 0, 0])


And this one is a 0-(4,1,2) design

sage: I = IncidenceStructure(range(4), [[0],[1]])
sage: I.is_block_design()
False


And this one is a 1-(4,1,1) design

sage: I = IncidenceStructure(range(4), [[0],[1],[2],[3]])
sage: I.is_block_design()
(False, [0, 0, 0, 0])


I broke it into several pieces in order to allow an argument t to the function. But I agree that comparing to the old version I can do much better with the degree stuff...

Vincent

### comment:51 in reply to: ↑ 50 Changed 7 years ago by ncohen

Yo !

This one is a 0-(4,0,3) design

And this one is a 0-(4,1,2) design

And this one is a 1-(4,1,1) design

....

Well, that's hardly a problem, is it ? Handling the trivial cases is usually done separately at the beginning of the function

I broke it into several pieces in order to allow an argument t to the function.

....

-        for t in range(2,min(v,k+1)):
+        for t in (range(2,min(v,k+1)) if t is None else [t]):


Nathann

Last edited 7 years ago by ncohen (previous) (diff)

### comment:52 in reply to: ↑ 48 ; follow-up: ↓ 53 Changed 7 years ago by vdelecroix

Everything are now tuples of tuples.

WHYYYYYYYYYYYYYYYYYYYYY everything ?????? Even incomplete_orthogonal_array ? WHy ???? And why steiner triple systems too ????

Why not only what belongs to a mutable class or is cached ?

This does not maky ANY sense :

self._points = tuple(range(v))


Why are you converting this to a tuple given that you created it yourself ? Nobody will change it !

and then

sage: BD = designs.IncidenceStructure(4)
sage: BD.points().append(19)
sage: BD.points()
[0, 1, 2, 3, 19]


Should we do a copy each time somebody asked for points?

### comment:53 in reply to: ↑ 52 Changed 7 years ago by ncohen

and then

sage: BD = designs.IncidenceStructure(4)
sage: BD.points().append(19)
sage: BD.points()
[0, 1, 2, 3, 19]


Should we do a copy each time somebody asked for points?

That's hardly a problem if we do a copy for blocks anyway. Plus one can directly access ._points to avoid that. But agreed, it's not a very bad problem anyway.

Nathann

### comment:54 Changed 7 years ago by git

• Commit changed from d69700920609cd6112d2496b8858f94da3642531 to b51512d642a603ea91d9358ea3d7877f184938d0

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

 ​b51512d trac #16553: less stupid implementation of _t_design_parameters

### comment:55 follow-up: ↓ 57 Changed 7 years ago by vdelecroix

Hi Nathann,

Sorry, I was being stupid... With the last commit, it is back to normal.

I still have a _t_design_parameters(self,t) (that only depends on t) and a is_t_design(self,t,v,k,l). We can always make only one function using an "output wrapper":

def make_the_output_the_user_want(t,v,k,l,vv,tt,kk,ll,return_parameters):
....


but I prefer the current version. Better idea?

EDIT: possibility, have only one parameter in is_t_design. But I think that it is very cool to have all of them available.

Vincent

Last edited 7 years ago by vdelecroix (previous) (diff)

### comment:56 Changed 7 years ago by vdelecroix

• Status changed from needs_work to needs_review

### comment:57 in reply to: ↑ 55 ; follow-up: ↓ 58 Changed 7 years ago by ncohen

Hello !

I still have a _t_design_parameters(self,t) (that only depends on t) and a is_t_design(self,t,v,k,l). We can always make only one function using an "output wrapper":

def make_the_output_the_user_want(t,v,k,l,vv,tt,kk,ll,return_parameters):
....


but I prefer the current version. Better idea?

What do you think of having only a is_t_design(t=None,v=None,k=None,l=None) ?

It would return pairs (a_boolean,(t,v,k,l)), such that the parameter is equal to the parameter given as input unless it was equal to None ?

It is easy to guess v,k, you already did the job for t, and as I don't think anybody will want to compute B.is_t_design(l=395) I guess we can say that "t must be defined if lambda is defined". I don't think anybody would complain.

It can be implemented anyway if needed, it will just be ugly.

Nathann

### comment:58 in reply to: ↑ 57 ; follow-up: ↓ 59 Changed 7 years ago by vdelecroix

Hello !

I still have a _t_design_parameters(self,t) (that only depends on t) and a is_t_design(self,t,v,k,l). We can always make only one function using an "output wrapper":

def make_the_output_the_user_want(t,v,k,l,vv,tt,kk,ll,return_parameters):
....


but I prefer the current version. Better idea?

What do you think of having only a is_t_design(t=None,v=None,k=None,l=None) ? It would return pairs (a_boolean,(t,v,k,l)), such that the parameter is equal to the parameter given as input unless it was equal to None ?

I would like it for sure if its purpose was only to return a boolean! A function that starts with is must return a boolean, otherwise it is a mess:

if m.is_even():
print "m is even"


bad luck: .is_even() return a pair "(boolean, m divided by 2)" (remember the concrete example in #16464).

It is easy to guess v,k, you already did the job for t, and as I don't think anybody will want to compute B.is_t_design(l=395) I guess we can say that "t must be defined if lambda is defined". I don't think anybody would complain.

It can be implemented anyway if needed, it will just be ugly.

It is implemented, not very ugly and not very useful!

Vincent

### comment:59 in reply to: ↑ 58 ; follow-up: ↓ 60 Changed 7 years ago by ncohen

I would like it for sure if its purpose was only to return a boolean! A function that starts with is must return a boolean, otherwise it is a mess:

if m.is_even():
print "m is even"


bad luck: .is_even() return a pair "(boolean, m divided by 2)" (remember the concrete example in #16464).

return_parameters=True...

It is implemented, not very ugly and not very useful!

What about all the stuff you converted to tuples ?..

Nathann

### comment:60 in reply to: ↑ 59 ; follow-up: ↓ 61 Changed 7 years ago by vdelecroix

I would like it for sure if its purpose was only to return a boolean! A function that starts with is must return a boolean, otherwise it is a mess:

if m.is_even():
print "m is even"


bad luck: .is_even() return a pair "(boolean, m divided by 2)" (remember the concrete example in #16464).

return_parameters=True...

It is implemented, not very ugly and not very useful!

What about all the stuff you converted to tuples ?..

I do not understand your point, in 58 you proposed is_t_design(self,t,v,k,l). Now, you want to keep the return_parameters=False/True. Fine, but it will be ugly if you make only one function.

If you want to propose some code, do it! I am lost!

Vincent

### comment:61 in reply to: ↑ 60 ; follow-up: ↓ 62 Changed 7 years ago by ncohen

I do not understand your point, in 58 you proposed is_t_design(self,t,v,k,l). Now, you want to keep the return_parameters=False/True. Fine, but it will be ugly if you make only one function.

I never had anything again return_parameters flags O_o

That's what I always do when I need a test function which can also return useful information it already computed...

If you want to propose some code, do it! I am lost!

Ahahah. And how do you think I am ? Your branch has something like 8 commits that undo each other, and you still haven't answered important things like : why do you convert everything to tuples ???

Do you mind if I rewrite history just a bit and merge all your commits into one, on top of #16466 ?

Nathann

### comment:62 in reply to: ↑ 61 ; follow-up: ↓ 63 Changed 7 years ago by vdelecroix

I do not understand your point, in 58 you proposed is_t_design(self,t,v,k,l). Now, you want to keep the return_parameters=False/True. Fine, but it will be ugly if you make only one function.

I never had anything again return_parameters flags O_o

That's what I always do when I need a test function which can also return useful information it already computed...

If you want to propose some code, do it! I am lost!

Ahahah. And how do you think I am ? Your branch has something like 8 commits that undo each other, and you still haven't answered important things like : why do you convert everything to tuples ???

Do you mind if I rewrite history just a bit and merge all your commits into one, on top of #16466 ?

fine.

### comment:63 in reply to: ↑ 62 ; follow-up: ↓ 64 Changed 7 years ago by ncohen

fine.

It is located at public/16553v2

Nathann

### comment:64 in reply to: ↑ 63 ; follow-up: ↓ 65 Changed 7 years ago by vdelecroix

fine.

It is located at public/16553v2

Thanks. What should we do for is_t_design?

### comment:65 in reply to: ↑ 64 ; follow-up: ↓ 66 Changed 7 years ago by ncohen

Thanks. What should we do for is_t_design?

Well the interface is nice, so why don't we just move the code of _t_design_parameters into it ?

Also, what about all the tuple stuff ? I think I asked this question 3 times already.

Nathann

### comment:66 in reply to: ↑ 65 ; follow-up: ↓ 67 Changed 7 years ago by vdelecroix

Thanks. What should we do for is_t_design?

Well the interface is nice, so why don't we just move the code of _t_design_parameters into it ?

Hmmmm. There are plenty of if condition: return blah in _t_design_parameters. Duplicating the code in is_t_design as many times would be awful.

Also, what about all the tuple stuff ? I think I asked this question 3 times already.

Yes, yes, yes. Either we hold immutable stuff or we copy on output. Note that I introduced the keyword copy which allows you to feed it with list. What do you want?

Vincent

### comment:67 in reply to: ↑ 66 Changed 7 years ago by ncohen

Hmmmm. There are plenty of if condition: return blah in _t_design_parameters. Duplicating the code in is_t_design as many times would be awful.

Okay I will give it a try then.

Yes, yes, yes. Either we hold immutable stuff or we copy on output. Note that I introduced the keyword copy which allows you to feed it with list. What do you want?

About incomplete_orthogonal_array and steiner triple systems, for instance ?...

Nathann

### comment:68 Changed 7 years ago by ncohen

Oh, steiner triple systems are probably incidence structures already, so that's okay.

Nathann

### comment:69 follow-up: ↓ 70 Changed 7 years ago by ncohen

BTW I am working on the is_t_design function right now.

Nathann

### comment:70 in reply to: ↑ 69 Changed 7 years ago by vdelecroix

BTW I am working on the is_t_design function right now.

Yes. This is what I understod and I am working on #16535

### comment:71 follow-up: ↓ 72 Changed 7 years ago by ncohen

DId you notice that ALL incidence structures are 0-designs ? And so that .is_t_design() ALWAYS return True ?

I'm removing all this t=0,1 shit. t>=2.

Nathann

### comment:72 in reply to: ↑ 71 Changed 7 years ago by vdelecroix

DId you notice that ALL incidence structures are 0-designs ? And so that .is_t_design() ALWAYS return True ?

I'm removing all this t=0,1 shit. t>=2.

All right.

Vincent

### comment:73 Changed 7 years ago by ncohen

The code at public/16553v2 works for all cases. Et ca m'a completement niqué la soirée. Deux heures a me payer des cas de merde de t=0 et t=1 dont tout le monde se branle.

Nathann

Last edited 7 years ago by ncohen (previous) (diff)

### comment:74 Changed 7 years ago by ncohen

• Branch changed from public/16553 to public/16553v2
• Commit changed from b51512d642a603ea91d9358ea3d7877f184938d0 to ad9f241f36f033dc449703bad527b2a8497c0315

New commits:

 ​ff72248 trac #16553: Clean IncidenceStructure ​ad9f241 trac #16553: is_t_design

### comment:75 follow-up: ↓ 79 Changed 7 years ago by ncohen

Okay, three questions :

• Should BlockDesign be deprecated ?
• is self._degrees_cache used anywhere ? If not, remove it
• self._incidence_matrix is set to None even when the Incidence Structure has been defined from the incidence matrix
• is_simple() does not work when the input is not copied and not necessarily sorted.

Nathann

### comment:76 Changed 7 years ago by ncohen

I will add commit to remove ten lines I had forgotten to remove in my last commit.

Nathann

### comment:77 Changed 7 years ago by git

• Commit changed from ad9f241f36f033dc449703bad527b2a8497c0315 to b8012e72038dffa51cc60b0af19283881dec2860

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

 ​b8012e7 trac #16553: Forgotten lines

### comment:78 Changed 7 years ago by ncohen

And of course you need to review my code too.

Nathann

### comment:79 in reply to: ↑ 75 ; follow-up: ↓ 80 Changed 7 years ago by vdelecroix

Okay, three questions :

• Should BlockDesign be deprecated ?

It is cool to have as an alias for incidence structure. If you find confusing to have an alias, then yes we should deprecate it.

• is self._degrees_cache used anywhere ? If not, remove it

Not anymore. I will.

• self._incidence_matrix is set to None even when the Incidence Structure has been defined from the incidence matrix

Yes, because of the reordering of the columns. But we can avoid reordering the columns and keep the matrix. But then, matrices are mutable... hopefully, we can do m.set_immutable() as soon as we use it.

• is_simple() does not work when the input is not copied and not necessarily sorted.

And the implementation is stupid, if the blocks are sorted, one would do

B = self._blocks
return any(B[i] == B[i+1] for i in xrange(len(B)-1))


And... Haaaa.... it is very bad to reorder the blocks:

sage: D = designs.IncidenceStructure(2, [[0]])
sage: D == D.dual().dual()
False


Taking dual should just be matrix transposition!! One question: what do you think of not reordering the blocks? (which is a different from the question "sorting each block")

Vincent

### comment:80 in reply to: ↑ 79 ; follow-up: ↓ 81 Changed 7 years ago by ncohen

Yo !

Yes, because of the reordering of the columns.

Ok !

And the implementation is stupid, if the blocks are sorted, one would do

Yep.

And... Haaaa.... it is very bad to reorder the blocks: Taking dual should just be matrix transposition!! One question: what do you think of not reordering the blocks? (which is a different from the question "sorting each block")

You should stop letting this function decide of how we should implement everything else. An incidence structure is isomorphic to its double dual and that's cool. We have more things to care about than making the vertex set equal to the set of blocks when we take the dual : anyway we cannot do that without losing the ability to iterate on the elements of a block.

Accept that.

Nathann

### comment:81 in reply to: ↑ 80 ; follow-up: ↓ 82 Changed 7 years ago by vdelecroix

Yo !

Yes, because of the reordering of the columns.

Ok !

And the implementation is stupid, if the blocks are sorted, one would do

Yep.

And... Haaaa.... it is very bad to reorder the blocks: Taking dual should just be matrix transposition!! One question: what do you think of not reordering the blocks? (which is a different from the question "sorting each block")

You should stop letting this function decide of how we should implement everything else. An incidence structure is isomorphic to its double dual and that's cool. We have more things to care about than making the vertex set equal to the set of blocks when we take the dual : anyway we cannot do that without losing the ability to iterate on the elements of a block.

Accept that.

No. It is more than isomorphic. There is a canonical isomorphism (that is lost because of the reordering)! But, for the sake of that ticket let say that I do accept that.

### comment:82 in reply to: ↑ 81 Changed 7 years ago by ncohen

No. It is more than isomorphic. There is a canonical isomorphism (that is lost because of the reordering)!

Mathematicians in book say "let us take a bijection between two things". But they are the same guys who, in front of the computer, want their vertices to be correctly labelled.

But, for the sake of that ticket let say that I do accept that.

Excellent ! :-P

Nathann

### comment:83 Changed 7 years ago by ncohen

By the way we will have an IncidenceStructure.relabel function someday.

### comment:84 follow-up: ↓ 85 Changed 7 years ago by ncohen

By the way this ticket was supposed to deal with ground sets different from {0,...,n-1}. What happened with that ?

Nathann

### comment:85 in reply to: ↑ 84 ; follow-up: ↓ 86 Changed 7 years ago by vdelecroix

By the way this ticket was supposed to deal with ground sets different from {0,...,n-1}. What happened with that ?

Does not work.

Are you done with your changes?

### comment:86 in reply to: ↑ 85 ; follow-up: ↓ 88 Changed 7 years ago by ncohen

Does not work.

I see.

Are you done with your changes?

Which changes ? The .is_t_design function works, it's all I had to do, wasn't it ?

Nathann

### comment:87 Changed 7 years ago by ncohen

• Description modified (diff)

### comment:88 in reply to: ↑ 86 Changed 7 years ago by vdelecroix

Does not work.

I see.

Are you done with your changes?

Which changes ? The .is_t_design function works, it's all I had to do, wasn't it ?

But Sage does not start. Is that what you want?

I will start from where it is!

Vincent

### comment:89 Changed 7 years ago by ncohen

Arg. I hadn't noticed that _t_design_parameters was an alias of something

 parameters = deprecated_function_alias(16553, _t_design_parameters)


Nathann

### comment:90 follow-up: ↓ 91 Changed 7 years ago by ncohen

I can add the old code, why not ?.. It is a deprecated function after all. Are you already working on this or can I do it ?

Nathann

### comment:91 in reply to: ↑ 90 Changed 7 years ago by vdelecroix

I can add the old code, why not ?.. It is a deprecated function after all. Are you already working on this or can I do it ?

Yes. I started again working on it.

Last edited 7 years ago by vdelecroix (previous) (diff)

### comment:92 Changed 7 years ago by ncohen

Okay. I was about to copy/paste the old parameters function and deprecate it.

Nathann

### comment:93 Changed 7 years ago by git

• Commit changed from b8012e72038dffa51cc60b0af19283881dec2860 to 9be78f42a2e26008661462f6db66b5646849ee76

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

 ​9be78f4 trac #16553: make it work with points other than integers

### comment:94 Changed 7 years ago by vdelecroix

• Status changed from needs_review to needs_work

### comment:95 Changed 7 years ago by ncohen

HMmm... You can't make equality depend on the ordering of the blocks.. Perhaps this copy=True on input is not very easy to work with :-/

Nathann

### comment:96 Changed 7 years ago by ncohen

Also, I wonder if it is a good idea to store the "labelled blocks" or if we should work with blocks on 0,...,n-1 and have dictionary to translate stuff when needed.. O_o

I have been bitten once or twice by the time it took to hash vertex labels in graphs -_-

Nathann

### comment:97 Changed 7 years ago by ncohen

Also, you can't sort something that you did not create yourself. If the "labels" on the points are something like sets (i.e. not totally ordered) then you can't assume that blocks are totally ordered either, and so you can't sort them either.

Nathann

### comment:98 follow-up: ↓ 99 Changed 7 years ago by vdelecroix

• It makes sense to translate everything on {0,...,n-1} internally. It will save a lot of pain.
• For the blocks we can put it into a fixed datastructure: i.e. a sparse incidence matrix (that way even the blocks are numbered). Sparse integer matrices have methods
def _nonzero_positions_by_row(self, copy=True)
def _nonzero_positions_by_column(self, copy=True)


It is a bit stupid for our purpose to use GMP integers... but at least these are fast methods.

What do you think of getting rid of the attribute ._blocks and use only ._incidence_matrix.

Vincent

### comment:99 in reply to: ↑ 98 ; follow-up: ↓ 100 Changed 7 years ago by ncohen

Yo !

• It makes sense to translate everything on {0,...,n-1} internally. It will save a lot of pain.

+1

• For the blocks we can put it into a fixed datastructure: i.e. a sparse incidence matrix (that way even the blocks are numbered). Sparse integer matrices have methods
def _nonzero_positions_by_row(self, copy=True)
def _nonzero_positions_by_column(self, copy=True)


It is a bit stupid for our purpose to use GMP integers... but at least these are fast methods.

What do you think of getting rid of the attribute ._blocks and use only ._incidence_matrix.

I don't like it, because I don't trust complicated datatypes. What do we earn by storing this as a matrix ? I expect it to be heavier (because it has to remember the '1' in each cell, it is not meant to be a binary matrix) and less practical (we iterate on the blocks all day long)..

The best data structure for this is a bipartite graph, isn't it ?

But even then, I personally prefer simple data types. Otherwise we will constantly do work on list of lists, translate everything to a matrix/graph, then export everything to list of lists, then build another incidence structure ...

What do you think ?

Nathann

Nathann

### comment:100 in reply to: ↑ 99 ; follow-up: ↓ 101 Changed 7 years ago by vdelecroix

Yo !

• It makes sense to translate everything on {0,...,n-1} internally. It will save a lot of pain.

+1

• For the blocks we can put it into a fixed datastructure: i.e. a sparse incidence matrix (that way even the blocks are numbered). Sparse integer matrices have methods
def _nonzero_positions_by_row(self, copy=True)
def _nonzero_positions_by_column(self, copy=True)


It is a bit stupid for our purpose to use GMP integers... but at least these are fast methods.

What do you think of getting rid of the attribute ._blocks and use only ._incidence_matrix.

I don't like it, because I don't trust complicated datatypes. What do we earn by storing this as a matrix ? I expect it to be heavier (because it has to remember the '1' in each cell, it is not meant to be a binary matrix) and less practical (we iterate on the blocks all day long)..

Right.

The best data structure for this is a bipartite graph, isn't it ?

It is the same as a binary matrix...

But even then, I personally prefer simple data types. Otherwise we will constantly do work on list of lists, translate everything to a matrix/graph, then export everything to list of lists, then build another incidence structure ...

What do you think ?

True, but we have to fix the way it is stored, otherwise everything is broken (e.g. equality, is_simple). Let's go for sorted tuples of sorted tuples of integers and add a flag do_not_copy_or_check_the_input_and_I_am_sure_that_it_is_what_I_want in the constructor. Is that good for you?

Vincent

### comment:101 in reply to: ↑ 100 Changed 7 years ago by ncohen

Yo !

It is the same as a binary matrix...

Not exactly. But anyway, a binary matrix is meant to be binary, while a Matrix isn't as far as I know.

True, but we have to fix the way it is stored, otherwise everything is broken (e.g. equality, is_simple). Let's go for sorted tuples of sorted tuples of integers and add a flag do_not_copy_or_check_the_input_and_I_am_sure_that_it_is_what_I_want in the constructor. Is that good for you?

What is the problem ? If you translate the input to 0,...,n-1 anyway we never have any reason to accept what the users gives us without a copy, do we ? And so you can sort it as you want, given that it is your data and that you will never give it as it is to anybody else.

Nathann

### comment:102 Changed 7 years ago by git

• Commit changed from 9be78f42a2e26008661462f6db66b5646849ee76 to cebb0617ea30551ee1e1562e152d5da1068c6bb1

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

 ​24a7ef8 trac #16553: Clean IncidenceStructure ​cebb061 trac #16553: is_t_design

### comment:103 Changed 7 years ago by git

• Commit changed from cebb0617ea30551ee1e1562e152d5da1068c6bb1 to 0741a69bb10de397690869ad98140e085ddab994

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

 ​102389e trac #16553: Clean IncidenceStructure ​0741a69 trac #16553: is_t_design

### comment:104 Changed 7 years ago by vdelecroix

• Status changed from needs_work to needs_review

All right,

Now:

• ._points are the points
• ._point_index might be None or a correspondence between point and integers
• ._blocks is a sorted tuple of sorted blocks on {0, ..., v-1}

(It is explained in the documentation)

I also removed all other hidden attributes. All doctest pass, and doc builds.

... needs review!

Vincent

### comment:105 Changed 7 years ago by vdelecroix

PS: I slightly modified your commit since it broke the documentation.

### comment:106 Changed 7 years ago by ncohen

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

And how the hell am I supposed to see the differences ?

Nathann

### comment:107 follow-up: ↓ 108 Changed 7 years ago by vdelecroix

git diff 9be78f42a2e26008661462f6db66b5646849ee76 \

Last edited 7 years ago by vdelecroix (previous) (diff)

### comment:108 in reply to: ↑ 107 Changed 7 years ago by ncohen

• Status changed from needs_review to needs_work
git diff 9be78f42a2e26008661462f6db66b5646849ee76 0741a69bb10de397690869ad98140e085ddab994


Good. Use that to produce a third commit.

Nathann

### comment:109 Changed 7 years ago by git

• Commit changed from 0741a69bb10de397690869ad98140e085ddab994 to dffcc4a8118a8bc5d9dfa6c1ab1aabe7aaaaa25a

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

 ​ff72248 trac #16553: Clean IncidenceStructure ​ad9f241 trac #16553: is_t_design ​b8012e7 trac #16553: Forgotten lines ​9be78f4 trac #16553: make it work with points other than integers ​dffcc4a trac #16553: reclean

### comment:110 Changed 7 years ago by vdelecroix

• Status changed from needs_work to needs_review

Thanks

### comment:112 Changed 7 years ago by ncohen

What about comment:95 ? If you make equality depend on the ordering, it may be broken when copy=False...

### comment:113 Changed 7 years ago by ncohen

I would say that the best is to sort the input even when copy=False, what do you think ? With a warning in the documentation of the copy argument of course, saying that the list/blocks will be reordered (and that the user should not touch that) ?...

This being said, the way equality is written it will still return false negatives as [1,2,3] != (1,2,3) ...

Nathann

### comment:114 Changed 7 years ago by ncohen

Oh, you removed "copy" in the next commit ....

### comment:115 Changed 7 years ago by ncohen

You add documentation for "copy" in the first commit, and remove it in the next.. This is really pleasant to review ...

Nathann

### comment:116 Changed 7 years ago by ncohen

sage: a = Set([1,2]); b = Set([3,4])
sage: IncidenceStructure([a,b],[]) == IncidenceStructure([b,a],[])
False


### comment:117 follow-up: ↓ 118 Changed 7 years ago by ncohen

• Status changed from needs_review to needs_work

Short of those comments it looks good !!

Two questions:

• What about renaming _point_index to _point_to_index to make its purpose clearer ?
• Should block_sizes return map(len,self._blocks) or wrap them in a set ?

Too bad that it is not very easy to have everything work with a "copy" argument :-/

Nathann

### comment:118 in reply to: ↑ 117 ; follow-up: ↓ 119 Changed 7 years ago by vdelecroix

about 116/97 and non-ordered stuff:

• one possibility: we can avoid sorting the ground set and consider [0,1,2], and [2,0,1] as different sets. For blocks, we convert everything to tuple of integers and it is fine for them to do the comparison. What do you think?

• What about renaming _point_index to _point_to_index to make its purpose clearer ?

no problem.

• Should block_sizes return map(len,self._blocks) or wrap them in a set ?

You are right, it is the way it was before. So I will put it back. And just for fun, here is the verbatim old implementation:

def block_sizes(self):
self._block_sizes = map(len, self.blocks())
return self._block_sizes


Too bad that it is not very easy to have everything work with a "copy" argument :-/

All right: I can put it back, but assume that the user feed the object with sorted tuples of tuples. It is not that complicated. Is that ok for you? I would like it to not waste my time with the constructor.

Not for this ticket

• right now the structure are immutable but it would makes sense to have mutable ones (that can be turn into immutable ones). For example, removing/adding blocks that contain a given point is a useful operation...
Last edited 7 years ago by vdelecroix (previous) (diff)

### comment:119 in reply to: ↑ 118 ; follow-up: ↓ 120 Changed 7 years ago by ncohen

Yo !

• one possibility: we can avoid sorting the ground set and consider [0,1,2], and [2,0,1] as different sets. For blocks, we convert everything to tuple of integers and it is fine for them to do the comparison. What do you think?

NOnonono, saying that the order of the vertices matters for equality really isn't what one would expect ! But it isn't so bad to make equality test slower, is it ? I mean, does anybody use it for anything ? I wonder why such methods are even defined...

Just to play it safe, we can rewrite this to relabel+convert to set the blocks of self and other before comparing them. It is slow but it is correct, and we can change the data structure later if it becomes a problem. Or use graphs as a data structure, as they do that already :-PPP

I don't mind not having an equality test, but if there is one I want to be sure that it works as expected. Because otherwise I cannot complain constantly about #14019, and that's important to me :-P

You are right, it is the way it was before. So I will put it back. And just for fun, here is the verbatim old implementation:

def block_sizes(self):
self._block_sizes = map(len, self.blocks())
return self._block_sizes


GNIiiiiiiiiiiiiiiiiiii >_<

All right: I can put it back, but assume that the user feed the object with sorted tuples of tuples. It is not that complicated. Is that ok for you? I would like it to not waste my time with the constructor.

What we can do is something like "set 'copy=False' if you do not want the constructor to make a copy of your data, but know that it will be modified. Use this flag only if you will not use your data anymore afterwards, or if you know what you are doing".

• right now the structure are immutable but it would makes sense to have mutable ones (that can be turn into immutable ones). For example, removing/adding blocks that contain a given point is a useful operation...

Ahahahaah. Yeah.... Like a bipartite graph ? :-P

Nathann

### comment:120 in reply to: ↑ 119 ; follow-up: ↓ 121 Changed 7 years ago by vdelecroix

Why aren't we using bipartite graph?

All right: I can put it back, but assume that the user feed the object with sorted tuples of tuples. It is not that complicated. Is that ok for you? I would like it to not waste my time with the constructor.

What we can do is something like "set 'copy=False' if you do not want the constructor to make a copy of your data, but know that it will be modified. Use this flag only if you will not use your data anymore afterwards, or if you know what you are doing".

Could you be more precise. We aim to store tuple of tuples of integers. What do you mean by modifying but not copying the data?

Vincent

### comment:121 in reply to: ↑ 120 Changed 7 years ago by ncohen

Why aren't we using bipartite graph?

Because I hate complicated data structure T_T

I love lists.

Could you be more precise. We aim to store tuple of tuples of integers. What do you mean by modifying but not copying the data?

Oh. I thought that we could store lists of lists in this case. I just hate tuple. Knowing that you have to copy the whole data (a list) to make it immutable (a tupple) horrifies me already.

Nathann

### comment:122 Changed 7 years ago by git

• Commit changed from dffcc4a8118a8bc5d9dfa6c1ab1aabe7aaaaa25a to 7e829da2d0b30ced9cc25e32efa78ffd40f59d01

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

 ​7e829da trac #16553: use list of lists + better equality

### comment:123 Changed 7 years ago by vdelecroix

• Status changed from needs_work to needs_review

All right, the commit message says it all. I also fixed the issue you mentioned.

Needs review!

Vincent

### comment:124 Changed 7 years ago by ncohen

HMmmmmmmm...

Well, I'd say that it is good O_O

Another pass on the whole branch, and then ...

Nathann

### comment:125 Changed 7 years ago by ncohen

• Reviewers set to Nathann Cohen, Vincent Delecroix

Yo !

If you agree with this additional commit, you can switch to positive_review !

Nathann

### comment:126 Changed 7 years ago by git

• Commit changed from 7e829da2d0b30ced9cc25e32efa78ffd40f59d01 to d15cc7eb29c85446655ec4f092583db9ec94b455

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

 ​d15cc7e trac #16553: Review

### comment:127 follow-up: ↓ 128 Changed 7 years ago by vdelecroix

Great!!

Should I rewrite the history since the global change on ext_rep.py/bibd.py is actually 0?

### comment:128 in reply to: ↑ 127 ; follow-up: ↓ 129 Changed 7 years ago by ncohen

Should I rewrite the history since the global change on ext_rep.py/bibd.py is actually 0?

What for ? O_o

Nathann

### comment:129 in reply to: ↑ 128 Changed 7 years ago by vdelecroix

Should I rewrite the history since the global change on ext_rep.py/bibd.py is actually 0?

What for ? O_o

• improve my skills with git rebase
• have git blame do better job
• simplification

### comment:130 Changed 7 years ago by vdelecroix

• Branch changed from public/16553v2 to public/16553v3
• Commit changed from d15cc7eb29c85446655ec4f092583db9ec94b455 to a9f825c496c0ab9769ff55589764f0c7aea83eaf
• Status changed from needs_review to positive_review

Same diff, better history... so I guess it is better.

Last 10 new commits:

 ​828ff22 trac #16437: cut the branches in W. dec. with two trunc. blocks ​8ebd21b trac #16347: use is_sum_of_squares_pyx instead of two_squares ​0175134 trac #16347: doc + simplifications ​0d79982 trac #16446: merge #16347 ​6559eec trac #16446: fix doctest ​16a0c5d trac #16446: use deprecated_function_alias instead ​4dc250a trac #16553: Clean IncidenceStructure ​bd609fc trac #16553: is_t_design ​11994ef trac #16553: Review ​a9f825c trac #16553: doc fix

### comment:131 Changed 7 years ago by vbraun

• Status changed from positive_review to needs_work
sage -t --long src/sage/matroids/catalog.py
**********************************************************************
File "src/sage/matroids/catalog.py", line 1349, in sage.matroids.catalog.Block_9_4
Failed example:
BlockDesign(9, B).is_block_design()
Exception raised:
Traceback (most recent call last):
File "/home/release/Sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 480, in _run
self.execute(example, compiled, test.globs)
File "/home/release/Sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 839, in execute
exec compiled in globs
File "<doctest sage.matroids.catalog.Block_9_4[5]>", line 1, in <module>
BlockDesign(Integer(9), B).is_block_design()
AttributeError: 'IncidenceStructure' object has no attribute 'is_block_design'
**********************************************************************
File "src/sage/matroids/catalog.py", line 1376, in sage.matroids.catalog.Block_10_5
Failed example:
BlockDesign(10, B).is_block_design()
Exception raised:
Traceback (most recent call last):
File "/home/release/Sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 480, in _run
self.execute(example, compiled, test.globs)
File "/home/release/Sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 839, in execute
exec compiled in globs
File "<doctest sage.matroids.catalog.Block_10_5[5]>", line 1, in <module>
BlockDesign(Integer(10), B).is_block_design()
AttributeError: 'IncidenceStructure' object has no attribute 'is_block_design'
**********************************************************************


### comment:132 Changed 7 years ago by git

• Commit changed from a9f825c496c0ab9769ff55589764f0c7aea83eaf to e7a97ea3ca390627aed24693e5314568234dfdf3

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

 ​e7a97ea trac #16553: doc fix + deprecation is_block_design

### comment:133 Changed 7 years ago by vdelecroix

• Status changed from needs_work to needs_review

### comment:134 Changed 7 years ago by git

• Commit changed from e7a97ea3ca390627aed24693e5314568234dfdf3 to 3c0dd71a1ecaf61af062ff7ddedf4e95f38d5b22

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

 ​3c0dd71 trac #16553v3: change .points() -> .ground_set()

### comment:135 Changed 7 years ago by vdelecroix

All right, final review needed!

Vincent

### comment:136 Changed 7 years ago by ncohen

Funny. I would have expected .points() to appear more often in the code :-)

Nathann

### comment:137 Changed 7 years ago by ncohen

• Status changed from needs_review to positive_review

make ptestlong + make doc-clean + make doc + make doc-pdf.

And the latter failed during "a tour of Sage' but that's only because other documents always require one thousand different languages to be installed I believe.

Good !

Nathann

### comment:138 Changed 7 years ago by vbraun

• Status changed from positive_review to needs_work

There is another .points that was introduced in #16535

### comment:139 Changed 7 years ago by git

• Commit changed from 3c0dd71a1ecaf61af062ff7ddedf4e95f38d5b22 to 51476ff0e94c0260dd7d13143b8c5f3bd390f95b

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

### comment:140 Changed 7 years ago by vdelecroix

• Status changed from needs_work to needs_review

Needs review!

Vincent

### comment:141 Changed 7 years ago by ncohen

• Status changed from needs_review to needs_work

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

### comment:142 Changed 7 years ago by git

• Commit changed from 51476ff0e94c0260dd7d13143b8c5f3bd390f95b to 0698433258c4f863cc1585ece2065b5e4e1b41eb

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`

### comment:143 Changed 7 years ago by vdelecroix

• Status changed from needs_work to needs_review

### comment:144 follow-up: ↓ 145 Changed 7 years ago by ncohen

• Status changed from needs_review to positive_review

For the tenth time ...