Opened 7 years ago
Closed 7 years ago
#16553 closed enhancement (fixed)
Clean IncidenceStructure
Reported by:  vdelecroix  Owned by:  

Priority:  major  Milestone:  sage6.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 )
Change History (146)
comment:1 followup: ↓ 2 Changed 7 years ago by
comment:2 in reply to: ↑ 1 ; followup: ↓ 3 Changed 7 years ago by
Yo !
 I think we also want another bijection
blocks <> {0, ..., b1}
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 beDesign
...
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 bijectiongroups <> {0, ..., g1}
.
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 ; followup: ↓ 4 Changed 7 years ago by
Replying to ncohen:
Yo !
 I think we also want another bijection
blocks <> {0, ..., b1}
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 beDesign
...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 bijectiongroups <> {0, ..., g1}
.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 blockReally ? 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
comment:4 in reply to: ↑ 3 ; followup: ↓ 5 Changed 7 years ago by
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 forbidp in block
.
............
Yeah, let's make it impossible to iterate on blocks. That will be better.
Yes, we need
Hypergraph.to_incidence_structure
andIncidenceStructure.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 ; followups: ↓ 6 ↓ 7 Changed 7 years ago by
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 forbidp 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
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 ; followup: ↓ 8 Changed 7 years ago by
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 forbidp 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 ; followup: ↓ 9 Changed 7 years ago by
All right: what about intersection? do we want
b1.intersection(b2)
available?
Why we would need that ?...
Nathann
comment:9 in reply to: ↑ 8 ; followup: ↓ 10 Changed 7 years ago by
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
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
 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
I did not know what to do with def block_design_checker(self, t, v, k, lmbda, type=None):
... help!
Vincent
comment:13 followup: ↓ 14 Changed 7 years ago by
 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 2design (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 ; followup: ↓ 15 Changed 7 years ago by
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
toTDesign
? A GDD is not exactly a 2design (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 tdesigns 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 ; followup: ↓ 16 Changed 7 years ago by
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 tdesigns 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 makingBlockDesign = 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 (liket_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 ; followup: ↓ 17 Changed 7 years ago by
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 tdesigns 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 makingBlockDesign = 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 (liket_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
Yo !
I propose to remove tDesign and have
IncidenceStructure
(inincidence_structure.py
) and setBlockDesign = IncidenceStructure
as an alias (inblock_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 followup: ↓ 19 Changed 7 years ago by
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
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 followup: ↓ 21 Changed 7 years ago by
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 ; followup: ↓ 22 Changed 7 years ago by
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 ; followup: ↓ 23 Changed 7 years ago by
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 oft
. There is no such thing as "the largest t such that a design is at
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(vs,ts) / binomial(ks,ts).
(Handbook theorem II.4.8)
I think that we should forbid lambda=0, that's all.
comment:23 in reply to: ↑ 22 ; followup: ↓ 28 Changed 7 years ago by
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 withlambda_s = lambda binomial(vs,ts) / binomial(ks,ts).(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 followup: ↓ 25 Changed 7 years ago by
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
Replying to ncohen:
Also, what would you think of deprecating
dual_design
anddual_incidence_structure
in favor of....dual()
?Nathann
I would love that!
comment:26 followup: ↓ 27 Changed 7 years ago by
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 ; followup: ↓ 29 Changed 7 years ago by
Replying to ncohen:
Also, do you know where on earth
IncidenceStructure.args
,IncidenceStructure.keywords
andIncidenceStructure.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
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 withlambda_s = lambda binomial(vs,ts) / binomial(ks,ts).(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 0design
 a 0design for which each point has the same degree is a 1design
I should modify the function to take care of that...
comment:29 in reply to: ↑ 27 Changed 7 years ago by
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
 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
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
 Status changed from needs_info to needs_review
comment:33 Changed 7 years ago by
 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
there was small conflicts with #16446 so I did the merge.
comment:35 Changed 7 years ago by
First passe review:
 Deprecated argument for
BlockDesign(test=...)
_relabel_bibd(BalancedIncompleteBlockDesign(N,k).blocks(),N)
remove.blocks()
, avoids a copyis_block_design
>t_design_parameters
O_o ???is_t_design
? Why remove
OA_to_projective_plane
?  Why this ?
 A 3design::   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()
andblocks()
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 acopy=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 ofdegrees
is ridiculous. Think of the algorithmics behind instead of using fancy "reduce" functions.
is_t_design
andt_design_parameters
should be the same function. Let's just have optionalt,v,k,l
parameters inis_t_design
.
Nathann
comment:36 Changed 7 years ago by
 Status changed from needs_review to needs_work
comment:37 Changed 7 years ago by
 Commit changed from 9243ef16bf0e7ad800bca41fa6d5001042859d76 to 428113c0bef095a97189239435c6fb4a92dbe099
comment:38 followup: ↓ 39 Changed 7 years ago by
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 3design::   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 ofdegrees
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
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
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
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 2design, I sure as hell don't want Sage to beging enumerating 5tuples, even if my design is a 5design.
Nathann
comment:42 followup: ↓ 43 Changed 7 years ago by
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 ; followup: ↓ 44 Changed 7 years ago by
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 inblocks()
. This way, if the user (=us, the developpers) saycopy=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
andis_t_design
: if I want to know whether my design is a 2design, I sure as hell don't want Sage to beging enumerating 5tuples, even if my design is a 5design.
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
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
 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 followup: ↓ 48 Changed 7 years ago by
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
 Status changed from needs_work to needs_review
comment:48 in reply to: ↑ 46 ; followup: ↓ 52 Changed 7 years ago by
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 followup: ↓ 50 Changed 7 years ago by
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 ; followup: ↓ 51 Changed 7 years ago by
 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
Yo !
This one is a
0(4,0,3)
designAnd this one is a
0(4,1,2)
designAnd 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
comment:52 in reply to: ↑ 48 ; followup: ↓ 53 Changed 7 years ago by
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
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
 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 followup: ↓ 57 Changed 7 years ago by
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
comment:56 Changed 7 years ago by
 Status changed from needs_work to needs_review
comment:57 in reply to: ↑ 55 ; followup: ↓ 58 Changed 7 years ago by
Hello !
I still have a
_t_design_parameters(self,t)
(that only depends ont
) and ais_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 ; followup: ↓ 59 Changed 7 years ago by
Replying to ncohen:
Hello !
I still have a
_t_design_parameters(self,t)
(that only depends ont
) and ais_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 toNone
?
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 fort
, and as I don't think anybody will want to computeB.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 ; followup: ↓ 60 Changed 7 years ago by
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 ; followup: ↓ 61 Changed 7 years ago by
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 ; followup: ↓ 62 Changed 7 years ago by
I do not understand your point, in 58 you proposed
is_t_design(self,t,v,k,l)
. Now, you want to keep thereturn_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 ; followup: ↓ 63 Changed 7 years ago by
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 thereturn_parameters=False/True
. Fine, but it will be ugly if you make only one function.I never had anything again
return_parameters
flagsO_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 ; followup: ↓ 64 Changed 7 years ago by
fine.
It is located at public/16553v2
Nathann
comment:64 in reply to: ↑ 63 ; followup: ↓ 65 Changed 7 years ago by
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 ; followup: ↓ 66 Changed 7 years ago by
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 ; followup: ↓ 67 Changed 7 years ago by
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
Hmmmm. There are plenty of
if condition: return blah
in_t_design_parameters
. Duplicating the code inis_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
Oh, steiner triple systems are probably incidence structures already, so that's okay.
Nathann
comment:69 followup: ↓ 70 Changed 7 years ago by
BTW I am working on the is_t_design
function right now.
Nathann
comment:70 in reply to: ↑ 69 Changed 7 years ago by
comment:71 followup: ↓ 72 Changed 7 years ago by
DId you notice that ALL incidence structures are 0designs ? 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
Replying to ncohen:
DId you notice that ALL incidence structures are 0designs ? 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
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
comment:74 Changed 7 years ago by
 Branch changed from public/16553 to public/16553v2
 Commit changed from b51512d642a603ea91d9358ea3d7877f184938d0 to ad9f241f36f033dc449703bad527b2a8497c0315
comment:75 followup: ↓ 79 Changed 7 years ago by
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 matrixis_simple()
does not work when the input is not copied and not necessarily sorted.
Nathann
comment:76 Changed 7 years ago by
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
 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
And of course you need to review my code too.
Nathann
comment:79 in reply to: ↑ 75 ; followup: ↓ 80 Changed 7 years ago by
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 ; followup: ↓ 81 Changed 7 years ago by
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 ; followup: ↓ 82 Changed 7 years ago by
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
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
By the way we will have an IncidenceStructure.relabel
function someday.
comment:84 followup: ↓ 85 Changed 7 years ago by
By the way this ticket was supposed to deal with ground sets different from {0,...,n1}
. What happened with that ?
Nathann
comment:85 in reply to: ↑ 84 ; followup: ↓ 86 Changed 7 years ago by
Replying to ncohen:
By the way this ticket was supposed to deal with ground sets different from
{0,...,n1}
. What happened with that ?
Does not work.
Are you done with your changes?
comment:86 in reply to: ↑ 85 ; followup: ↓ 88 Changed 7 years ago by
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
 Description modified (diff)
comment:88 in reply to: ↑ 86 Changed 7 years ago by
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
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 followup: ↓ 91 Changed 7 years ago by
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
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.
comment:92 Changed 7 years ago by
Okay. I was about to copy/paste the old parameters
function and deprecate it.
Nathann
comment:93 Changed 7 years ago by
 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
 Status changed from needs_review to needs_work
comment:95 Changed 7 years ago by
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
Also, I wonder if it is a good idea to store the "labelled blocks" or if we should work with blocks on 0,...,n1
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
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 followup: ↓ 99 Changed 7 years ago by
 It makes sense to translate everything on {0,...,n1} 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 ; followup: ↓ 100 Changed 7 years ago by
Yo !
 It makes sense to translate everything on {0,...,n1} 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 ; followup: ↓ 101 Changed 7 years ago by
Replying to ncohen:
Yo !
 It makes sense to translate everything on {0,...,n1} 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
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 flagdo_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,...,n1 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
 Commit changed from 9be78f42a2e26008661462f6db66b5646849ee76 to cebb0617ea30551ee1e1562e152d5da1068c6bb1
comment:103 Changed 7 years ago by
 Commit changed from cebb0617ea30551ee1e1562e152d5da1068c6bb1 to 0741a69bb10de397690869ad98140e085ddab994
comment:104 Changed 7 years ago by
 Status changed from needs_work to needs_review
All right,
Now:
._points
are the points._point_index
might beNone
or a correspondence between point and integers._blocks
is a sorted tuple of sorted blocks on {0, ..., v1}
(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
PS: I slightly modified your commit since it broke the documentation.
comment:106 Changed 7 years ago by
....................
And how the hell am I supposed to see the differences ?
Nathann
comment:107 followup: ↓ 108 Changed 7 years ago by
git diff 9be78f42a2e26008661462f6db66b5646849ee76 \ 0741a69bb10de397690869ad98140e085ddab994
comment:108 in reply to: ↑ 107 Changed 7 years ago by
 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
 Commit changed from 0741a69bb10de397690869ad98140e085ddab994 to dffcc4a8118a8bc5d9dfa6c1ab1aabe7aaaaa25a
comment:110 Changed 7 years ago by
 Status changed from needs_work to needs_review
comment:111 Changed 7 years ago by
Thanks
comment:112 Changed 7 years ago by
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
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
Oh, you removed "copy" in the next commit ....
comment:115 Changed 7 years ago by
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
sage: a = Set([1,2]); b = Set([3,4]) sage: IncidenceStructure([a,b],[]) == IncidenceStructure([b,a],[]) False
comment:117 followup: ↓ 118 Changed 7 years ago by
 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
returnmap(len,self._blocks)
or wrap them in aset
?
Too bad that it is not very easy to have everything work with a "copy" argument :/
Nathann
comment:118 in reply to: ↑ 117 ; followup: ↓ 119 Changed 7 years ago by
about 116/97 and nonordered 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
returnmap(len,self._blocks)
or wrap them in aset
?
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...
comment:119 in reply to: ↑ 118 ; followup: ↓ 120 Changed 7 years ago by
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 ; followup: ↓ 121 Changed 7 years ago by
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
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
 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
 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
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
 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
 Commit changed from 7e829da2d0b30ced9cc25e32efa78ffd40f59d01 to d15cc7eb29c85446655ec4f092583db9ec94b455
Branch pushed to git repo; I updated commit sha1. New commits:
d15cc7e  trac #16553: Review

comment:127 followup: ↓ 128 Changed 7 years ago by
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 ; followup: ↓ 129 Changed 7 years ago by
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
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
 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
 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/sitepackages/sage/doctest/forker.py", line 480, in _run self.execute(example, compiled, test.globs) File "/home/release/Sage/local/lib/python2.7/sitepackages/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/sitepackages/sage/doctest/forker.py", line 480, in _run self.execute(example, compiled, test.globs) File "/home/release/Sage/local/lib/python2.7/sitepackages/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
 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
 Status changed from needs_work to needs_review
comment:134 Changed 7 years ago by
 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
All right, final review needed!
Vincent
comment:136 Changed 7 years ago by
Funny. I would have expected .points()
to appear more often in the code :)
Nathann
comment:137 Changed 7 years ago by
 Status changed from needs_review to positive_review
make ptestlong + make docclean + make doc + make docpdf.
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
 Status changed from positive_review to needs_work
There is another .points that was introduced in #16535
comment:139 Changed 7 years ago by
 Commit changed from 3c0dd71a1ecaf61af062ff7ddedf4e95f38d5b22 to 51476ff0e94c0260dd7d13143b8c5f3bd390f95b
comment:140 Changed 7 years ago by
 Status changed from needs_work to needs_review
Needs review!
Vincent
comment:141 Changed 7 years ago by
 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
 Commit changed from 51476ff0e94c0260dd7d13143b8c5f3bd390f95b to 0698433258c4f863cc1585ece2065b5e4e1b41eb
comment:143 Changed 7 years ago by
 Status changed from needs_work to needs_review
comment:144 followup: ↓ 145 Changed 7 years ago by
 Status changed from needs_review to positive_review
For the tenth time ...
comment:145 in reply to: ↑ 144 Changed 7 years ago by
comment:146 Changed 7 years ago by
 Branch changed from public/16553v3 to 0698433258c4f863cc1585ece2065b5e4e1b41eb
 Resolution set to fixed
 Status changed from positive_review to closed
Some more remarks:
blocks <> {0, ..., b1}
to have well defined incidence matrices. It would also help to choose proper labels for the dual incidence structure.IncidenceStructure
would beDesign
... and we also need a class forGroupDivisibleDesign
and for them we need an other bijectiongroups <> {0, ..., g1}
.rank/unrank