search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.3k stars 447 forks source link

CoveringArrays #34279

Closed aadwyer closed 11 months ago

aadwyer commented 2 years ago

An implementation of a covering array class for sagemath. This is a work in progress. The initial commit will include the Covering array class with simple methods that give: its size n and k, its parameters t and v, and an ordering based on the lexicographic ordering of each row.

Component: combinatorics

Keywords: Coverin Array, Orthogonal Array, Block Design

Author: Aaron Dwyer, brett stevens

Branch/Commit: u/gh-Aaron-Dwyer/coveringarrays @ 42ba324

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

aadwyer commented 2 years ago

Branch: u/gh-Aaron-Dwyer/coveringarrays

aadwyer commented 2 years ago

Commit: cd1e2b1

aadwyer commented 2 years ago

Description changed:

--- 
+++ 
@@ -1 +1 @@
-
+An implementation of a covering array class for sagemath. This is a work in progress. The initial commit will include the Covering array class with simple methods that give: its size n and k, its parameters t and v, and an ordering based on the lexicographic ordering of each row.
aadwyer commented 2 years ago

Author: Aaron Dwyer, brett stevens

aadwyer commented 2 years ago

Changed keywords from none to Coverin Array, Orthogonal Array, Block Design

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from cd1e2b1 to 5a4d108

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

5a4d108This is the initial commit, the covering array class was created
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 1 year ago

Changed commit from 5a4d108 to aeca574

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 1 year ago

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

07a90daThis is the initial commit, the covering array class was created
da2022eadded comments to covering array file, still to add examples
8e4aec5Created py file for basic CA generation methods, will not be used in first
bb509f2finished the strength 2 construction
8ec7c1dAdded some methods namely pprint and __hash, edited/added doctests some of
514e363Ensured all the doctests are working.
337a825removed covering array file temporarily
2d86a34Merge branch 'u/gh-Aaron-Dwyer/coveringarrays' of trac.sagemath.org:sage into t/34279/coveringarrays
aeca574The covering arrays file is now up to date
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 1 year ago

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

42ba324Fixed the merge of the covering array file
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 1 year ago

Changed commit from aeca574 to 42ba324

brettpim commented 1 year ago

does writing a comment add me to the participant list?

videlec commented 1 year ago

To my mind, the most important thing when adding code to a library is to keep consistency. As I mentioned in #35008, the whole idea of the sage/combinat/design of sage is to provide constructions of various designs. Few objects have a dedicated class and we never felt the need to have one. The only interesting class in the repository is IncidenceStructure (= hypergraph). Unless you have a strong argument for creating CoveringArray rather than implementing is_covering_array, etc I am against the proposal. Furthermore, why would there be a class CoveringArray and not OrthogonalArray, DifferenceMatrix, etc?

brettpim commented 1 year ago

Vincent,

Thank you for thinking about this and reaching out to us. There are hundreds of different constructions for Covering Arrays, some recursive, some direct and some probabilistic. In your proposal, would we make a separate function for each one? How would a user know all the possible constructions that are available that are specific to covering arrays? I will start reviewing all the OA code to better understand how they are handeled.

regards brett

On 3/18/23 17:01, Vincent Delecroix wrote:

To my mind, the most important thing when adding code to a library is to keep consistency. As I mentioned in #35008 https://github.com/sagemath/sage/pull/35008, the whole idea of the |sage/combinat/design| of sage is to provide constructions of various designs. Few objects have a dedicated class and we never felt the need to have one. The only interesting class in the repository is |IncidenceStructure| (= hypergraph). Unless you have a strong argument for creating |CoveringArray| rather than implementing |is_covering_array|, etc I am against the proposal. Furthermore, why would there be a class |CoveringArray| and not |OrthogonalArray|, |DifferenceMatrix|, etc?

— Reply to this email directly, view it on GitHub https://github.com/sagemath/sage/issues/34279#issuecomment-1474992974, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACBVFGTRED6PTWFOQR6LSK3W4YPENANCNFSM6AAAAAAUUJ33KI. You are receiving this because you commented.Message ID: @.***>

[ { @.": "http://schema.org", @.": "EmailMessage", "potentialAction": { @.": "ViewAction", "target": "https://github.com/sagemath/sage/issues/34279#issuecomment-1474992974", "url": "https://github.com/sagemath/sage/issues/34279#issuecomment-1474992974", "name": "View Issue" }, "description": "View this Issue on GitHub", "publisher": { @.": "Organization", "name": "GitHub", "url": "https://github.com" } } ]

-- Brett Stevens Professor School of Mathematics and Statistics Carleton University 1125 Colonel By Dr. Ottawa ON K1S 5B6 Canada (613) 520-2600 x2125 FAX: (613) 520-3536

`[Using]Anarchism' indifferently with `anarchy' ... is a hardly more correct use of words than saying that a Conservative is one who makes jam.'' -- George Orwell

videlec commented 1 year ago

It is great to see some activity around combinatorial design again!

Aren't there also hundreds of different constructions for orthogonal arrays? Just have a look at orthogonal_arrays_build_recursive.py. How are covering arrays different?

The main question is why the implementation of covering arrays should be any different of orthogonal arrays? There might be reason to do so, it is just that I do not see any.

brettpim commented 1 year ago

Vincent,

I have done an initial look over the OA functions and implementations. I notice that the following objects all get their own class:

Transversal Design Group Divisible Design Covering Design

Is there a clear articulation in sagemath of when something should or should not get its own class? I.e. is there a guiding principle?

I think some of the things that I would like to ask of a CA or OA are

Similarly I might like to ask for various combinatorial objects obtainable from a CA or OA.

It is true that we could build external stand alone functions to return these data but in an object oriented programing language isn't this precisely why we create classes?

Aaron and I have only mapped out the first kinds of CA constructions that we want to implement right now. Probably all these could be done without a CA class. But there are some things that might come later that could be easier with a class:

These are some of my initial thoughts. I am open minded about this so willing to be convinced a class is not necessary/useful.

thanks brett

On 3/18/23 20:28, Vincent Delecroix wrote:

It is great to see some activity around combinatorial design again!

Aren't there also hundreds of different constructions for orthogonal arrays? Just have a look at |orthogonal_arrays_build_recursive.py|. How are covering arrays different?

The main question is why the implementation of covering arrays should be any different of orthogonal arrays? There might be reason to do so, it is just that I do not see any.

— Reply to this email directly, view it on GitHub https://github.com/sagemath/sage/issues/34279#issuecomment-1475047035, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACBVFGUXPS22CGUJCYG26A3W4ZHMBANCNFSM6AAAAAAUUJ33KI. You are receiving this because you commented.Message ID: @.***>

[ { @.": "http://schema.org", @.": "EmailMessage", "potentialAction": { @.": "ViewAction", "target": "https://github.com/sagemath/sage/issues/34279#issuecomment-1475047035", "url": "https://github.com/sagemath/sage/issues/34279#issuecomment-1475047035", "name": "View Issue" }, "description": "View this Issue on GitHub", "publisher": { @.": "Organization", "name": "GitHub", "url": "https://github.com" } } ]

-- Brett Stevens Professor School of Mathematics and Statistics Carleton University 1125 Colonel By Dr. Ottawa ON K1S 5B6 Canada (613) 520-2600 x2125 FAX: (613) 520-3536

`[Using]Anarchism' indifferently with `anarchy' ... is a hardly more correct use of words than saying that a Conservative is one who makes jam.'' -- George Orwell

videlec commented 1 year ago

Note the inheritance

class IncidenceStructure():
class GroupDivisibleDesign(IncidenceStructure):
class TransversalDesign(GroupDivisibleDesign):
class PairwiseBalancedDesign(GroupDivisibleDesign):
class BalancedIncompleteBlockDesign(PairwiseBalancedDesign):

class CoveringDesign(SageObject):

class TwoGraph(IncidenceStructure):

In particular, most of them inherit from IncidenceStructure which was designed with some optimization in mind. Big designs are expensive to construct. You do not want to deal with arbitrary Python objects all the time.

Is there a clear articulation in sagemath of when something should or should not get its own class? I.e. is there a guiding principle?

Not really. But I would try to follow: "for any line of code added, the previous code should look more coherent then it used to be". It is by no mean a rule.

The combinatorial design part of sage has been written with the following approach : give me parameters and I will tell you if such construction exists, and if so I can build it for you.

sage: designs.orthogonal_arrays.exists(5, 5)
True
sage: designs.orthogonal_arrays.is_available(5, 5)
True
sage: designs.orthogonal_arrays.build(5, 5)
[[0, 0, 0, 0, 0],
 [0, 1, 2, 3, 4],
 [0, 2, 4, 1, 3],
 [0, 3, 1, 4, 2],
...
 [4, 4, 4, 4, 4]]

And it can even tell you which construction is used in build

sage: designs.orthogonal_arrays.explain_construction(5, 5)
'From a projective plane of order 5'

Many designs are built recursively and it is very convenient to have all these functions uncoupled. For example you can ask for existence without building the design and quickly get the list of parameters for which a construction exists in sage.

It is true that we could build external stand alone functions to return these data but in an object oriented programing language isn't this precisely why we create classes?

You are not forced to write classes for every single mathematical concept. Especially if your object is a list of lists. To my mind, classes come in a second time for two possibly related reasons

brettpim commented 1 year ago

My first concern surrounds the parameters that we know a CA can exists for. If I ask if a CA(N;t=2,k,v) exists, it could be constructed from a CA(N;2,k+s,v) by deleting columns, it could be constructed from a CA(N';2k,v) by adding rows, it could be constructed from a CA(N;2;k-s,v+s) by projection if I know that the CA(N;2,k+s,v-s) has a very particular substructure; from a CA(N';s,k+s-2,v) if N' \leq v^(s-2)N. I am not sure how to in general program a routine that can answer the question if the desired CA(N;2,k,v) exists, even if I know all the constructions I had programmed. I am worried that this kind of question might not be answerable for CAs in the same way that the OA questions can be answered. I had imagined implementing some constructions of CAs recursively from other CAs and also directly from fields, groups, LFSRs, geometry but I am not confident of being able to write anything like the OA "find recursive constructions" meta-functions. It is something I would like to do if it is possible. My focus in starting adding this functionality to SageMAth was focused on having an instance of a CA and doing the things with it that can be done with it (giving new CAs etc), rather than being focused on answering the questions "does a CA with these parameters exist?" I had imagined implementing some constructions of CAs recursively from other CAs and also directly from fields, groups, LFSRs, geometry but I am not confident of being able to write anything like the OA "find recursive constructions" functions

CAs are much more like Covering Designs: we often do not know the optimal; we know that a CA will always exist for a given t,k,v if we let N get big enough. In fact we know the existence of optimal CAs only when v=t=2; when N=v^t (and the CA is an OA) and in 25 other parameter sets. Most of these are for t=2, v<8 and k is also small. The Covering Design class handles this by looking up the best known answer on the La Jolla repository. Charles Colbourn does have a repository of CA existence tables but its methods data is not nearly at the same level as La Jolla. This is something we could do but probably not for the initial pull-request.

We had chosen our initial pull-request to be very modest because when I implemented a bunch of Block Design methods, the reviewer, Nathann Cohen told me I had implemented too much and this was a barrier to approving the patch and I did not want that to happen again. Our idea was to implement the basic things and get them in Sagemath and then do further rounds with more advanced constructions.

One further argument in favour of a class for OAs is that OAs are dual to error correcting codes. Bose's theorem says that the orthogonal complement of a linear error correcting code is an OA . Since codes get their own class, it seems somewhat natural for OAs to get their own class (and this is something Aaron and I contemplated implementing)

brettpim commented 1 year ago

I would hate to invest a lot of time doing without a class now and and then having to re-implement with classes if it becomes clear it is important later