| Title: | Fast Companions to the 'CAs' Package for Covering Arrays |
|---|---|
| Description: | Compiled implementations and generalizations of selected functions of the 'CAs' package by Ulrike Groemping for covering arrays. The package provides a C version of the search for the largest set of rows that can be made constant by permuting symbols, the power construction of Colbourn and Torres-Jimenez (2010) <doi:10.1090/conm/523/10309> for any strength, number of columns and number of levels, a counting kernel that tabulates value tuples for every set of t columns, and fast versions of the flexible-value tools and of the randomized post-optimization of Nayeri, Colbourn and Konjevod (2013) <doi:10.1016/j.ejc.2012.07.017>. Each function was tested against its 'CAs' counterpart, and the remaining differences are documented. |
| Authors: | Christopher Smolen [aut, cre] |
| Maintainer: | Christopher Smolen <[email protected]> |
| License: | GPL (>= 3) |
| Version: | 0.1.0 |
| Built: | 2026-10-28 19:31:57 UTC |
| Source: | https://github.com/cran/cafast |
Compiled implementations and generalizations of selected functions of the package CAs by Ulrike Groemping, for working with covering arrays.
maxconstant_c: makes the largest possible number
of rows constant, as CAs::maxconstant does, with the clique
search in C.
powerCT_any, power_plan,
power_build: the power construction of Colbourn and
Torres-Jimenez for any strength, number of columns and number of
levels, where CAs::powerCA covers its catalogued settings.
count_core: tuple counts for every set of
t columns, the counting behind coverage checks.
flexpos_c, markflex_c: flexible
positions and greedy marking of flexible values, as
CAs::flexpos and CAs::markflex.
postopNCK_c: the post-optimization of Nayeri,
Colbourn and Konjevod, as CAs::postopNCK.
Each function was tested against its counterpart in CAs. The help pages list the differences that remain, which concern tie-breaks, missing values and input checks. The test batteries, which download arrays from the NIST covering array tables, are installed in the ‘tests’ folder of the installed package.
Christopher Smolen [email protected]
The package CAs, https://CRAN.R-project.org/package=CAs.
The counting kernel behind coverage checks of covering arrays. For
every set of t columns, in lexicographic order, the function
counts how often each value tuple occurs among the rows. A row with
an NA in a projection contributes nothing to that projection.
count_core(x, t, vs = apply(x, 2, function(col) max(col, na.rm = TRUE) + 1L), rowmult = TRUE)count_core(x, t, vs = apply(x, 2, function(col) max(col, na.rm = TRUE) + 1L), rowmult = TRUE)
x |
an integer matrix (or a matrix or data frame that can be
converted to one) with rows as runs and columns as factors, coded
from 0. |
t |
the number of columns per projection, an integer from 1 to
|
vs |
the number of levels of each column, a vector of length
|
rowmult |
logical. If |
The order of the column sets matches combn and the column
sets reported by CAs::coverage. Tuples are linearized with
the leftmost column varying fastest. The tuple space of one column
set is limited to values, and the rowmult matrix
to cells. The computation is single
threaded and can be interrupted.
A list with elements
tots |
for every set of |
ncovered |
for every set of |
missing |
|
rowmult |
if |
The column sets are taken in lexicographic order, the order of
combn(ncol(x), t). The first three elements are numeric
vectors of length choose(ncol(x), t).
coverage in package CAs.
## the full factorial 2^3 covers every pair, each pair tuple twice x <- as.matrix(expand.grid(0:1, 0:1, 0:1)) r <- count_core(x, 2) r$ncovered r$missing r$rowmult[1:3, ] ## four of the runs form an orthogonal array of strength 2 oa <- x[c(1, 4, 6, 7), ] count_core(oa, 2)$missing ## without its first run, one pair is missing in every two columns count_core(oa[-1, ], 2, vs = c(2, 2, 2))$missing## the full factorial 2^3 covers every pair, each pair tuple twice x <- as.matrix(expand.grid(0:1, 0:1, 0:1)) r <- count_core(x, 2) r$ncovered r$missing r$rowmult[1:3, ] ## four of the runs form an orthogonal array of strength 2 oa <- x[c(1, 4, 6, 7), ] count_core(oa, 2)$missing ## without its first run, one pair is missing in every two columns count_core(oa[-1, ], 2, vs = c(2, 2, 2))$missing
C implementations of flexpos and markflex from the
package CAs. A position of a covering array is flexible when
every t-tuple through it is also covered by another row, so
the position can be changed on its own without loss of coverage.
markflex_c applies the greedy marking of Nayeri, Colbourn and
Konjevod (2013), which turns a set of positions into NA
(“don't care”) values that are flexible together.
flexpos_c(D, t, conv = c("flexpos", "coverage")) markflex_c(D, t, fixrows = 0)flexpos_c(D, t, conv = c("flexpos", "coverage")) markflex_c(D, t, fixrows = 0)
D |
a matrix or data frame with rows as runs and columns as
factors, coded from 0 or from 1 with consecutive symbols in each
column. |
t |
the strength, an integer from 2 to |
conv |
the reading of |
fixrows |
an integer from 0 to |
A position counts as flexible in flexpos_c when, for every
set of t columns through its column, the row's tuple on that
set occurs in at least two rows.
markflex_c sorts the rows by their number of flexible
positions in ascending order (a stable sort, keeping the first
fixrows rows in place, and no sort at all if
fixrows >= nrow(D) - 1), as CAs::markflex does. It
then goes through the column sets in lexicographic order and the
rows from the top. The first row that covers a tuple keeps its
t cells of that set, and a row with an NA in the
projection covers nothing. Cells that are kept by no column set
become NA.
Both functions reproduce CAs::flexpos and
CAs::markflex cell for cell on the test batteries of the
package. The differences are in the input handling. Codes from 1 are
shifted to 0 internally and back on output, codes that are not
consecutive give an informative error, and markflex_c returns
the attributes rowOrder and flexcount, where
CAs::markflex returns rowOrder and flexible.
flexpos_c returns a logical matrix of the dimensions of
D, TRUE at flexible positions. Cells that are
NA in D are TRUE.
markflex_c returns a matrix in the coding of D, with
the rows in their sorted order and the flexible values set to
NA. It has the attributes rowOrder (the indices of the
rows of D in the order returned) and flexcount (the
number of NA cells in each returned row).
Nayeri, P., Colbourn, C.J., Konjevod, G. (2013). Randomized post-optimization of covering arrays. European Journal of Combinatorics 34, 91–103. doi:10.1016/j.ejc.2012.07.017
flexpos and markflex in package CAs,
postopNCK_c.
plan <- rbind(c(2,2,2,2,0,0,1), c(0,0,2,2,2,2,2), c(1,1,2,1,2,0,1), c(0,1,2,0,1,1,0), c(2,2,1,0,2,0,2), c(2,1,0,2,1,2,2), c(1,2,0,0,0,2,0), c(0,2,1,1,1,2,1), c(1,0,1,2,1,0,0), c(2,0,0,1,2,1,0), c(0,0,0,0,0,0,1), c(1,1,1,1,0,1,2), c(2,2,2,2,2,2,2), c(2,2,2,2,0,1,1)) ## positions not involved in any pair that only one row covers flexpos_c(plan, 2) ## a set of positions that can be flexible together ## the last two rows are entirely flexible and can be dropped (m <- markflex_c(plan, 2)) attr(m, "flexcount")plan <- rbind(c(2,2,2,2,0,0,1), c(0,0,2,2,2,2,2), c(1,1,2,1,2,0,1), c(0,1,2,0,1,1,0), c(2,2,1,0,2,0,2), c(2,1,0,2,1,2,2), c(1,2,0,0,0,2,0), c(0,2,1,1,1,2,1), c(1,0,1,2,1,0,0), c(2,0,0,1,2,1,0), c(0,0,0,0,0,0,1), c(1,1,1,1,0,1,2), c(2,2,2,2,2,2,2), c(2,2,2,2,0,1,1)) ## positions not involved in any pair that only one row covers flexpos_c(plan, 2) ## a set of positions that can be flexible together ## the last two rows are entirely flexible and can be dropped (m <- markflex_c(plan, 2)) attr(m, "flexcount")
A C implementation of maxconstant from the package CAs
by Ulrike Groemping. A set of rows can be made constant by permuting
symbols within columns exactly when every two of its rows differ in
every column. The function finds a largest such set (a largest
clique in the graph whose vertices are the rows and whose edges join
rows that differ in every column), moves it to the front and relabels
the symbols of each column so that these rows become constant.
maxconstant_c(D, verbose = 0, remove = FALSE, one_is_enough = FALSE, dupcheck = FALSE, ...)maxconstant_c(D, verbose = 0, remove = FALSE, one_is_enough = FALSE, dupcheck = FALSE, ...)
D |
a numeric matrix, a uniform array with rows as runs and
columns as factors. It should have no duplicated rows unless
|
verbose |
one of 0, 1, 2 or 12, as in |
remove |
logical. If |
one_is_enough |
logical. If |
dupcheck |
logical. If |
... |
currently not used. |
The graph is built and searched in C. The clique search is a
branch and bound that stops as soon as it holds rows, the
number of levels, since no more rows can be constant. Existing
constant rows are tried first as a forced start of the clique. If an
unconstrained clique is strictly larger it is used, otherwise the
clique containing the existing constant rows is kept, which is the
preference of CAs::maxconstant. If the array already has
constant rows, or no larger clique exists, the existing
constant rows are moved to the front and nothing else changes.
Differences from CAs::maxconstant (version 0.24-4). When
several largest cliques exist, CAs::maxconstant takes the last
one returned by igraph::largest_cliques and this function
takes the first one found in row order. The number of constant rows
is the same. The arrays then differ by a row order and a symbol
permutation, and on arrays with duplicated rows the number of rows
outside the clique that happen to be constant as well can differ.
The levels are taken from the whole array, whereas
CAs::maxconstant takes them from the first column and stops
unless every column has the same number of levels.
Missing values are treated as in CAs::maxconstant. A row
with an NA cell is not an existing constant row. Two rows are
adjacent when they differ in every column in which both are
non-missing, so an NA cell matches no symbol. After the
clique rows are moved to the front, the NA cells among them
are filled column by column, from the top, with the levels that do
not occur among the clique rows in that column, in ascending order.
The symbols are then permuted, and NA cells outside the clique
rows stay NA. With one_is_enough = TRUE and no
existing constant row, NA cells in the first row are left as
they are, as in CAs::maxconstant.
Two cases with NA cells give different results. First, the
clique search here stops at rows, while
igraph::largest_cliques can return a clique of more than
rows when NA cells make extra rows compatible. No
filling makes more than rows constant, and
CAs::maxconstant then returns fewer constant rows (often
none), while this function returns . Second, when only one
row can be made constant, none is constant yet and the first row has
an NA cell, CAs::maxconstant stops with an error and
this function fills the cell. The fill uses the array's own levels,
where CAs::maxconstant uses 0:(v-1), which is the same
for arrays coded from 0.
A matrix equivalent to D (rows reordered, symbols permuted
within columns) whose first rows are constant, with the levels of
D in ascending order: the first constant row holds the
smallest level, the second the next one, and so on. With
remove = TRUE these rows are dropped instead. For
verbose 2 or 12 the result carries the attribute
constant_rows, a list with elements design_name (the
deparsed argument) and row_set_list (the indices, in
D after any dupcheck, of the rows that became the
constant rows).
Torres-Jimenez, J., Acevedo-Juarez, B., Avila-George, H. (2021). Covering array EXtender. Applied Mathematics and Computation 402, 126122. doi:10.1016/j.amc.2021.126122
maxconstant in package CAs, powerCT_any,
which uses this function on its ingredient.
## a 3-level array: one row is constant and one more can be made constant plan <- rbind(c(2,2,2,2,0,0,1), c(0,0,2,2,2,2,2), c(1,1,2,1,2,0,1), c(0,1,2,0,1,1,0), c(2,2,1,0,2,0,2), c(2,1,0,2,1,2,2), c(1,2,0,0,0,2,0), c(0,2,1,1,1,2,1), c(1,0,1,2,1,0,0), c(2,0,0,1,2,1,0), c(0,0,0,0,0,0,1), c(1,1,1,1,0,1,2), c(2,2,2,2,2,2,2), c(2,2,2,2,0,1,1)) maxconstant_c(plan, verbose = 1) ## an orthogonal array OA(64, 4, 4, 3) with three NA cells, one of ## them in row 22, which becomes the second constant row D <- as.matrix(expand.grid(0:3, 0:3, 0:3)) D <- unname(cbind(D, (D[, 1] + D[, 2] + D[, 3]) %% 4)) D[c(2, 22, 30), 4] <- NA head(maxconstant_c(D, verbose = 1))## a 3-level array: one row is constant and one more can be made constant plan <- rbind(c(2,2,2,2,0,0,1), c(0,0,2,2,2,2,2), c(1,1,2,1,2,0,1), c(0,1,2,0,1,1,0), c(2,2,1,0,2,0,2), c(2,1,0,2,1,2,2), c(1,2,0,0,0,2,0), c(0,2,1,1,1,2,1), c(1,0,1,2,1,0,0), c(2,0,0,1,2,1,0), c(0,0,0,0,0,0,1), c(1,1,1,1,0,1,2), c(2,2,2,2,2,2,2), c(2,2,2,2,0,1,1)) maxconstant_c(plan, verbose = 1) ## an orthogonal array OA(64, 4, 4, 3) with three NA cells, one of ## them in row 22, which becomes the second constant row D <- as.matrix(expand.grid(0:3, 0:3, 0:3)) D <- unname(cbind(D, (D[, 1] + D[, 2] + D[, 3]) %% 4)) D[c(2, 22, 30), 4] <- NA head(maxconstant_c(D, verbose = 1))
The post-optimization of Nayeri, Colbourn and Konjevod (2013) as
implemented in postopNCK of the package CAs, with the
marking steps in C (flexpos_c,
markflex_c). Rows whose cells can all be made flexible
are removed. The other flexible values are filled at random and the
array is marked again, repeatedly, so that more rows become
removable.
postopNCK_c(D, t, fixrows = 0, outerRetry = 50, outerMaxnochange = 10, innerRetry = 10, innerMaxnochange = 25, seed = NULL, timeBudget = Inf, restarts = 0, verbose = 0)postopNCK_c(D, t, fixrows = 0, outerRetry = 50, outerMaxnochange = 10, innerRetry = 10, innerMaxnochange = 25, seed = NULL, timeBudget = Inf, restarts = 0, verbose = 0)
D |
a covering array of strength |
t |
the strength, an integer from 2 to |
fixrows |
an integer from 0 to |
outerRetry |
the largest number of outer rounds. |
outerMaxnochange |
the number of consecutive outer rounds that
remove no row after which the search stops (or restarts, see
|
innerRetry |
the number of inner retries in one outer round. Each retry works on a different last row. |
innerMaxnochange |
the number of inner iterations without an increase in the number of flexible values of the last row after which the next inner retry starts. |
seed |
|
timeBudget |
a time limit in seconds (default |
restarts |
the number of restarts allowed after the stopping
rule of |
verbose |
0 (the default) prints nothing. With 1 or more, the number of rows is printed in every outer round, and with 2 or more every inner retry is printed as well. |
A row with fewer than t non-flexible cells covers nothing and
is removed. The inner loop moves a row with the most flexible values
to the bottom, fills the flexible values (in a column where the
bottom row has a symbol, with that symbol, elsewhere at random),
marks the array again and repeats. Inner retries and outer rounds
follow CAs::postopNCK.
The function was calibrated against CAs::postopNCK by the
distribution of the achieved number of rows over many seeds, not by
trajectory. The same seed gives different runs in the two functions.
The deliberate differences, agreed with the author of CAs, are
these. Random fills use the array's own coding. Exhausted rows are
kept in an explicit vector at the top of the array, and exactly
these rows are frozen between inner retries (CAs::postopNCK
freezes up to the last exhausted index, which in practice freezes
the rows with flexible values as well). An inner pass that removes
nothing hands its perturbed array to the next pass instead of
returning its input. The function is silent by default. The time
budget and the restarts are additions taken from the paper. An
interrupt returns the best array found so far.
The array with the fewest rows found, of class "ca" added to
the matrix classes, in the coding of D, with its remaining
flexible values as NA. It has the attribute seed, the
attribute flexible (list(value = NA)) if it contains
NA cells, and timeout = TRUE or interrupt = TRUE
if the search was stopped by timeBudget or by a user
interrupt. If nrow(D) already equals the product of the
t largest numbers of levels, D is returned unchanged.
Nayeri, P., Colbourn, C.J., Konjevod, G. (2013). Randomized post-optimization of covering arrays. European Journal of Combinatorics 34, 91–103. doi:10.1016/j.ejc.2012.07.017
postopNCK in package CAs, markflex_c.
plan <- rbind(c(2,2,2,2,0,0,1), c(0,0,2,2,2,2,2), c(1,1,2,1,2,0,1), c(0,1,2,0,1,1,0), c(2,2,1,0,2,0,2), c(2,1,0,2,1,2,2), c(1,2,0,0,0,2,0), c(0,2,1,1,1,2,1), c(1,0,1,2,1,0,0), c(2,0,0,1,2,1,0), c(0,0,0,0,0,0,1), c(1,1,1,1,0,1,2), c(2,2,2,2,2,2,2), c(2,2,2,2,0,1,1)) A <- postopNCK_c(plan, 2, seed = 1) dim(A) ## still covering: no pair is missing in any two columns sum(count_core(A, 2, vs = rep(3, 7), rowmult = FALSE)$missing)plan <- rbind(c(2,2,2,2,0,0,1), c(0,0,2,2,2,2,2), c(1,1,2,1,2,0,1), c(0,1,2,0,1,1,0), c(2,2,1,0,2,0,2), c(2,1,0,2,1,2,2), c(1,2,0,0,0,2,0), c(0,2,1,1,1,2,1), c(1,0,1,2,1,0,0), c(2,0,0,1,2,1,0), c(0,0,0,0,0,0,1), c(1,1,1,1,0,1,2), c(2,2,2,2,2,2,2), c(2,2,2,2,0,1,1)) A <- postopNCK_c(plan, 2, seed = 1) dim(A) ## still covering: no pair is missing in any two columns sum(count_core(A, 2, vs = rep(3, 7), rowmult = FALSE)$missing)
The power construction of Colbourn and Torres-Jimenez (2010) for any
strength , number of columns and number of levels
, in the homogeneous case with one ingredient. The function
powerCA of the package CAs builds the 132 settings of
its catalogue, and these functions extend the same construction to
other settings.
powerCT_any(t, k, v, emax = 4, qextra = 1, ingredient = NULL, verbose = TRUE, ...) power_plan(t, k, v, emax = 4, qextra = 1, ingredient = NULL, maxq = 400, verbose = TRUE, ...) power_build(t, k, v, q, e, ingredient = NULL, ...)powerCT_any(t, k, v, emax = 4, qextra = 1, ingredient = NULL, verbose = TRUE, ...) power_plan(t, k, v, emax = 4, qextra = 1, ingredient = NULL, maxq = 400, verbose = TRUE, ...) power_build(t, k, v, q, e, ingredient = NULL, ...)
t |
the strength. |
k |
the number of columns. |
v |
the number of levels. |
emax |
the largest exponent |
qextra |
for each exponent, the number of admissible prime
powers |
ingredient |
|
maxq |
the largest prime power |
verbose |
logical. If |
q |
a prime power, the number of levels of the orthogonal array and the number of columns of the ingredient. |
e |
the strength of the orthogonal array, at least 2. |
... |
passed to the ingredient function or to
|
The columns of a Bush orthogonal array OA(, ,
, ) (from CAs::SCA_Busht), transposed, give a
distributing hash family with columns. Its first
rows are used, where is the
Turan number, so is needed, and .
An ingredient CA(, , ) with rows,
of them constant after maxconstant_c, is
placed in every row of the hash family, shifted by
modulo in row . Then
constant rows are added back,
which gives rows. The assembly
follows CAs::DHHF2CA.
power_plan enumerates the admissible , builds
each ingredient once and reports . power_build builds
the array for one . powerCT_any plans and builds
the smallest. The constructions with several ingredients or with
T-reductions in the catalogue of CAs::powerCA are not
covered, and the result is often larger than the best known array.
power_plan returns a data frame with one row per admissible
, sorted by the number of rows N, with columns
t, k, v, e, q, M (rows of
the hash family), N1 (rows of the ingredient), rho
(its constant rows), chi (constant rows added back),
N and kmax (, the largest number of columns
of this ). The attribute ingredients is a list of
the ingredient arrays by . If no is admissible,
the result is NULL.
power_build returns an integer matrix with k columns,
levels 0:(v-1) and no duplicated rows, with the attributes
t, q, e, M, N1 and origin.
powerCT_any returns the array of power_build for the
first row of the plan, with the plan as the further attribute
plan. It gives a warning if the number of rows differs from
the plan.
Colbourn, C.J., Torres-Jimenez, J. (2010). Heterogeneous hash families and covering arrays. In Bruen, A.A., Wehlau, D.L. (eds.), Contemporary Mathematics 523, 3–15. American Mathematical Society, Providence, Rhode Island. doi:10.1090/conm/523/10309
powerCA, bestCA and DHHF2CA in package
CAs.
## a strength 2 binary ingredient that needs no download ing <- function(t, q, v) CAs::KSK(k = q) power_plan(2, 100, 2, ingredient = ing) A <- powerCT_any(2, 100, 2, ingredient = ing, verbose = FALSE) dim(A) sum(count_core(A, 2, vs = rep(2, 100), rowmult = FALSE)$missing) B <- power_build(2, 100, 2, q = 11, e = 2, ingredient = CAs::KSK(k = 11)) dim(B)## a strength 2 binary ingredient that needs no download ing <- function(t, q, v) CAs::KSK(k = q) power_plan(2, 100, 2, ingredient = ing) A <- powerCT_any(2, 100, 2, ingredient = ing, verbose = FALSE) dim(A) sum(count_core(A, 2, vs = rep(2, 100), rowmult = FALSE)$missing) B <- power_build(2, 100, 2, q = 11, e = 2, ingredient = CAs::KSK(k = 11)) dim(B)