Opened 7 years ago

Closed 7 years ago

#16553 closed enhancement (fixed)

Clean IncidenceStructure

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-6.3
Component: combinatorial designs Keywords:
Cc: ncohen, brett Merged in:
Authors: Nathann Cohen, Vincent Delecroix Reviewers: Nathann Cohen, Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 0698433 (Commits) Commit: 0698433258c4f863cc1585ece2065b5e4e1b41eb
Dependencies: Stopgaps:

Description (last modified by ncohen)

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

Change History (146)

comment:1 follow-up: 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: 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 :

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

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

Replying to 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 ?

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

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

comment:4 in reply to: ↑ 3 ; follow-up: 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: Changed 7 years ago by vdelecroix

Replying to ncohen:

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: Changed 7 years ago by vdelecroix

Replying to vdelecroix:

Replying to ncohen:

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: 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: Changed 7 years ago by vdelecroix

Replying to ncohen:

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:

a5c4dbctrac #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: 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: Changed 7 years ago by vdelecroix

Replying to ncohen:

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: 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: Changed 7 years ago by vdelecroix

Replying to ncohen:

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: 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: 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: 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: Changed 7 years ago by vdelecroix

Replying to 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.

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: 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: 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

Replying to ncohen:

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: 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: Changed 7 years ago by vdelecroix

Replying to ncohen:

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

Replying to 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

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:

6cc8889trac #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:

3e01acbtrac #16430: micro improvements
81b9448trac #16430: put back the seealso
0fa89d5trac #16347: Wilson's construction with two truncated groups
828ff22trac #16437: cut the branches in W. dec. with two trunc. blocks
8ebd21btrac #16347: use is_sum_of_squares_pyx instead of two_squares
0175134trac #16347: doc + simplifications
0d79982trac #16446: merge #16347
6559eectrac #16446: fix doctest
16a0c5dtrac #16446: use deprecated_function_alias instead
9243ef1trac #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:

0883515trac #16553: reviewer comments 1
c7d3e79trac #16553: better degree implementation
428113ctrac #16553: remove t_design_parameters

comment:38 follow-up: 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: 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: Changed 7 years ago by vdelecroix

Replying to 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.

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

Replying to 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.

agreed. I will modify that.

Replying to 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 ?

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:

d697009trac #16553: make everything tuples and hide _degree stuff

comment:46 follow-up: 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: 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: 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: Changed 7 years ago by vdelecroix

  • Status changed from needs_review to needs_work

Replying to 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.

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.

....

What about this ?..

-        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: Changed 7 years ago by vdelecroix

Replying to 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 !

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:

b51512dtrac #16553: less stupid implementation of _t_design_parameters

comment:55 follow-up: 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: 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: Changed 7 years ago by vdelecroix

Replying to 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 ?

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: 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: Changed 7 years ago by vdelecroix

Replying to 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 ?..

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: 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: Changed 7 years ago by vdelecroix

Replying to 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 ?

fine.

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

fine.

It is located at public/16553v2

Nathann

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

Replying to ncohen:

fine.

It is located at public/16553v2

Thanks. What should we do for is_t_design?

comment:65 in reply to: ↑ 64 ; follow-up: 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: Changed 7 years ago by vdelecroix

Replying to 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 ?

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: 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

Replying to ncohen:

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: 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

Replying to 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.

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:

ff72248trac #16553: Clean IncidenceStructure
ad9f241trac #16553: is_t_design

comment:75 follow-up: 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:

b8012e7trac #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: Changed 7 years ago by vdelecroix

Replying to ncohen:

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: 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: Changed 7 years ago by vdelecroix

Replying to 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.

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: 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: Changed 7 years ago by vdelecroix

Replying to ncohen:

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: 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

Replying to 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 ?

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: 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

Replying to 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 ?

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:

9be78f4trac #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: 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: 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: Changed 7 years ago by vdelecroix

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

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:

24a7ef8trac #16553: Clean IncidenceStructure
cebb061trac #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:

102389etrac #16553: Clean IncidenceStructure
0741a69trac #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: Changed 7 years ago by vdelecroix

git diff 9be78f42a2e26008661462f6db66b5646849ee76 \
         0741a69bb10de397690869ad98140e085ddab994
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:

ff72248trac #16553: Clean IncidenceStructure
ad9f241trac #16553: is_t_design
b8012e7trac #16553: Forgotten lines
9be78f4trac #16553: make it work with points other than integers
dffcc4atrac #16553: reclean

comment:110 Changed 7 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:111 Changed 7 years ago by ncohen

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

comment:97

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

comment:117 follow-up: 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: 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?

about 117:

  • 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: 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: Changed 7 years ago by vdelecroix

Why aren't we using bipartite graph?

Replying to ncohen:

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:

7e829datrac #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:

d15cc7etrac #16553: Review

comment:127 follow-up: 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: 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

Replying to ncohen:

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:

828ff22trac #16437: cut the branches in W. dec. with two trunc. blocks
8ebd21btrac #16347: use is_sum_of_squares_pyx instead of two_squares
0175134trac #16347: doc + simplifications
0d79982trac #16446: merge #16347
6559eectrac #16446: fix doctest
16a0c5dtrac #16446: use deprecated_function_alias instead
4dc250atrac #16553: Clean IncidenceStructure
bd609fctrac #16553: is_t_design
11994eftrac #16553: Review
a9f825ctrac #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:

e7a97eatrac #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:

3c0dd71trac #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:

09a8a4btrac #16553: merge #16535
8e45f07trac #16553: deprecated alias for .points() + fix
51476fftrac #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:

52b7177trac #16553: merge sage 6.3.beta5
0698433trac #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: Changed 7 years ago by ncohen

  • Status changed from needs_review to positive_review

For the tenth time ...

comment:145 in reply to: ↑ 144 Changed 7 years ago by vdelecroix

Replying to ncohen:

For the tenth time ...

and the last... (I hope)

comment:146 Changed 7 years ago by vbraun

  • Branch changed from public/16553v3 to 0698433258c4f863cc1585ece2065b5e4e1b41eb
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.