Interface for LMC normal forms

This file contains definitions and functions to perform minimal form tests and reductions.

Author: Pieter Eendebak pieter.eendebak@gmail.com

Copyright: See LICENSE file that comes with this distribution

Defines

ORDER_J5_SMALLER

ORDER_J5_GREATER

ORDER_J45_SMALLER

ORDER_J45_GREATER

stringify(name)

SDSMART

Typedefs

typedef unsigned int rowsort_value_t

typedef rowindex_t rowsortlight_t

typedef larray<rowindex_t> rowpermtypelight

typedef larray<colindex_t> colpermtypelight

typedef std::vector<int> colpermtype

typedef std::vector<colpermtype> colpermset

typedef std::shared_ptr<symmdata> symmdataPointer

typedef double jj45_t: Value representing the ordered combination of J5 and the 5 J4-values in the J54 ordering.

Enums

enum lmc_t

Possible results for the LMC check

Values:

enumerator LMC_LESS: Found a permutation which leads to a lexicographically smaller array.

enumerator LMC_EQUAL: Found a permutation which leads to a lexicographically equal array.

enumerator LMC_MORE: Found a permutation which leads to a lexicographically larger array.

enumerator LMC_NONSENSE: No valid result.

enum algorithm_t

different algorithms for minimal form check

Values:

enumerator MODE_LMC: LMC minimal form.

enumerator MODE_J4: LMC minimal form with J4 method.

enumerator MODE_J5ORDER: J5 minimal form.

enumerator MODE_J5ORDERX: J5 minimal form.

enumerator MODE_INVALID

enumerator MODE_AUTOSELECT: Automatically select the algorithm.

enumerator MODE_LMC_SYMMETRY: debugging method

enumerator MODE_LMC_2LEVEL: LMC minimal form, specialized for 2-level arrays.

enumerator MODE_LMC_DEBUG: debugging method

enumerator MODE_J5ORDER_2LEVEL: J5 minimal form for 2-level arrays.

enum initcolumn_t

method used for initialization of columns

Values:

enumerator INITCOLUMN_ZERO: Initialize column with zeros.

enumerator INITCOLUMN_PREVIOUS: Initialize column with values of previous column.

enumerator INITCOLUMN_J5: Initialize column with values based on J5 value.

enum j5structure_t

variations of the J45 structures

Values:

enumerator J5_ORIGINAL: Ordering based in J5 in succesive columns.

enumerator J5_45: Ordering based on J5 and the 5-tuple of J4 values. Also called the L5 ordering.

enum REDUCTION_STATE

variable indicating the state of the reduction process

Values:

enumerator REDUCTION_INITIAL: the reduction is equal to the initial

enumerator REDUCTION_CHANGED: the reduction was changed

enum OA_MODE

main mode for the LMC routine: test, reduce or reduce with initialization

Values:

enumerator OA_TEST: test for minimal form

enumerator OA_REDUCE: reduce to minimal form

enumerator OA_REDUCE_PARTIAL: reduce to partial minimal form

enum INIT_STATE

initial state for reduction algorithm

Values:

enumerator INIT_STATE_INVALID

enumerator COPY: copy from array argument

enumerator INIT: initialized by user

enumerator SETROOT: set initial state to root array

Functions

inline std::string algorithm_t_list(): Return string representation of available algorithm modes.

std::string algnames(algorithm_t m): return name of the algorithm

static inline bool operator<(const rowsort_t &a, const rowsort_t &b): Comparision operator for the rowsort_t structure.

static inline bool operator>(const rowsort_t &a, const rowsort_t &b): Comparision operator for the rowsort_t structure.

void apply_hadamard(array_link &al, colindex_t hcolumn): Apply Hadamard transformation to orthogonal array.

LMCreduction_helper_t *acquire_LMCreduction_object(): return static structure from dynamic global pool, return with releaseGlobalStatic

void release_LMCreduction_object(LMCreduction_helper_t *p)

void clear_LMCreduction_pool(): release all objects in the pool

bool valid_ptr(const symmdataPointer &sd): Return true if the (smart) symmdataPointer pointer is allocated

template<class Type> void insert_if_not_at_end_of_vector(std::vector<Type> &cp, const Type &value): Append element to vector if the element the element is not at the end of vector.

bool is_root_form(const array_link &array, int strength)

Return True if the array is in root form

Parameters:

array – Array to check
strength – Strength to use

Returns:

True if the array is in root form for the specified strength

lmc_t LMCreduction_train(const array_link &al, const arraydata_t *ad, LMCreduction_t *reduction, const OAextend &oaextend): helper function for LMC reduction

lmc_t LMCcheck(const array_t *array, const arraydata_t &ad, const OAextend &oaextend, LMCreduction_t &reduction): Perform LMC check or reduction on an array.

lmc_t LMCcheck(const array_link &array, const arraydata_t &ad, const OAextend &oaextend, LMCreduction_t &reduction): Perform LMC check or reduction on an array.

lmc_t LMCcheck(const array_link &array)

Perform LMC check on an orthogonal array

Parameters:: array – Array to be checked for LMC minimal form
Returns:: Result of the LMC check

lmc_t LMCcheckOriginal(const array_link &array)

Perform LMC check on a 2-level orthogonal array

The algorithm used is the original algorithm from “Complete enumeration of pure-level and mixed-level orthogonal arrays”, Schoen et al, 2009

Parameters:: array – Array to be checked for LMC minimal form
Returns:: Result of the LMC check

void reduceArraysGWLP(const arraylist_t &input_arrays, arraylist_t &reduced_arrays, int verbose, int dopruning = 1, int strength = 2, int dolmc = 1): reduce arrays to canonical form using delete-1-factor ordering

array_transformation_t reductionDOP(const array_link &array, int verbose = 0)

Caculate the transformation reducing an array to delete-on-factor normal

The normal form is described in “A canonical form for non-regular arrays based on generalized wordlength pattern values of delete-one-factor projections”, Eendebak, 2014

Parameters:

array – Orthogonal array
verbose – Verbosity level

Returns:

The transformation that reduces the array to normal form

array_link reduceDOPform(const array_link &array, int verbose = 0)

Reduce an array to canonical form using delete-1-factor ordering

The normal form is described in “A canonical form for non-regular arrays based on generalized wordlength pattern values of delete-one-factor projections”, Eendebak, 2014

Parameters:

array – Orthogonal array
verbose – Verbosity level

Returns:

The array transformed to normal form

void selectUniqueArrays(arraylist_t &input_arrays, arraylist_t &output_arrays, int verbose = 1): select the unique arrays in a list, the original list is sorted in place. the unique arrays are append to the output list

std::vector<GWLPvalue> projectionDOFvalues(const array_link &array, int verbose = 0): Calculate projection values for delete-of-factor algorithm

array_link reduceLMCform(const array_link &array): reduce an array to canonical form using LMC ordering

std::vector<int> LMCcheckLex(arraylist_t const &list, arraydata_t const &ad, int verbose = 0): Apply LMC check (original mode) to a list of arrays

lmc_t LMCcheckLex(array_link const &array, arraydata_t const &arrayclass): Perform minimal form check with LMC ordering.

lmc_t LMCcheckj4(array_link const &array, arraydata_t const &arrayclass, LMCreduction_t &reduction, const OAextend &oaextend, int jj = 4): Perform minimal form check with J4 ordering.

lmc_t LMCcheckj5(array_link const &array, arraydata_t const &arrayclass, LMCreduction_t &reduction, const OAextend &oaextend): Perform minimal form check for J5 ordering (in the paper this is called the L5 ordering)

void print_rowsort(rowsort_t *rowsort, int N)

Print the contents of a rowsort structure.

Parameters:

rowsort – Pointer to rowsort structure
N – Number of elements

void print_column_rowsort(const array_t *arraycol, rowsort_t *rowsort, int N)

Variables

const algorithm_t MODE_ORIGINAL = MODE_LMC 

struct LMCreduction_helper_t

#include <lmc.h>

Contains structures used by the LMC reduction or LMC check.

Part of the allocations is for structures that are constant and are re-used each time an LMC calculation is performed. Some other structures are temporary buffers that are written to all the time.

Public Functions

LMCreduction_helper_t()

~LMCreduction_helper_t()

inline void show(int verbose = 1) const

void init(const arraydata_t *adp)

void freeall()

int update(const arraydata_t *adp): update structure with new design specification

int needUpdate(const arraydata_t *adp) const

void init_root_stage(levelperm_t *&lperm_p, colperm_t *&colperm_p, const arraydata_t *adp)

void init_nonroot_stage(levelperm_t *&lperm_p, colperm_t *&colperm_p, colperm_t *&localcolperm_p, dyndata_t **&dynd_p, int &dynd_p_nelem, array_t *&colbuffer, const arraydata_t *adp) const

inline void init_rootrowperms(int &totalperms, rowperm_t *&rootrowperms, levelperm_t *&lperm_p): Static initialization of root row permutations.

inline void init_rootrowperms_full(int &totalperms, rowperm_t *&rootrowperms, levelperm_t *&lperm_p): Static initialization of root row permutations (full group)

Public Members

int LMC_non_root_init

int LMC_root_init

int LMC_reduce_root_rowperms_init

arraydata_t *ad

int LMC_root_rowperms_init

int nrootrowperms: number of root row permutations

rowperm_t *rootrowperms: pointer to row permutations that leave the root unchanged

int LMC_root_rowperms_init_full

int nrootrowperms_full

rowperm_t *rootrowperms_full

array_t *colbuffer

dyndata_t **dyndata_p: buffer for a single column

colindex_t **colperm_p: dynamic data; row permutations

colindex_t **localcolperm_p: column permutations

array_transformation_t *current_trans: local column permutation

struct LMCreduction_t

#include <lmc.h>

Class to describe an LMC reduction.

The most important variable is the transformation itself, contained in transformation. The state contains information about how the reduction was performed.

Public Functions

LMCreduction_t(const LMCreduction_t &at)

LMCreduction_t(const arraydata_t *arrayclass): copy constructor

~LMCreduction_t()

LMCreduction_t &operator=(const LMCreduction_t &at)

inline array_link getArray() const: Assignment operator.

inline void setArray(const array_link al)

inline void setArray(const array_t *array, int nrows, int ncols)

inline void updateSDpointer(const array_link al, bool cache = false): update the pointer to the symmetry data based on the specified array

inline void releaseStatic(): release internal LMCreduction_helper_t object

inline void initStatic(): acquire a reference to a LMCreduction_helper_t object

inline LMCreduction_helper_t &getReferenceReductionHelper(): return a reference to a object with LMC reduction data

void reset(): reset the reduction: clears the symmetries and sets the transformation to zero

void show(int verbose = 2) const

std::string __repr__() const

void updateFromLoop(const arraydata_t &ad, const dyndata_t &dynd, levelperm_t *lperms, const array_t *original): called whenever we find a reduction

void updateTransformation(const arraydata_t &ad, const dyndata_t &dynd, levelperm_t *lperms, const array_t *original)

inline void updateLastCol(int col)

Public Members

array_t *array

array_transformation_t *transformation: pointer to transformation_t structure

OA_MODE mode

REDUCTION_STATE state

INIT_STATE init_state

int maxdepth: maximum depth for search tree

int lastcol: last column visited in algorithm

long nred: counter for number of reductions made

int targetcol

int mincol

int nrows

int ncols

LMCreduction_helper_t *staticdata

symmdataPointer sd

Private Functions

void free()

class rowsorter_t

#include <lmc.h>

Structure to sort rows of arrays.

Public Functions

rowsorter_t(int number_of_rows)

~rowsorter_t()

Public Members

int number_of_rows

rowsort_t *rowsort

Private Functions

void reset_rowsort()

struct dyndata_t

#include <lmc.h>

Contains dynamic data of an array.

The dynamic data are used in the inner loops of the LMC algorithm. In particular they keep track of the current row ordering and column permutation. By not applying these transformations to the array we can save calculation time.

We try to prevent copying the object, so it is re-used at different levels in the algorithm.

N: static
- col: changes at each column level
rowsort: changes at each column level, used mainly in non-root stage
colperm: changes at all levels

See also

arraydata_t

Public Functions

dyndata_t(int N, int col = 0)

dyndata_t(const dyndata_t *dd)

dyndata_t(const dyndata_t&)

~dyndata_t()

dyndata_t &operator=(const dyndata_t&)

void show() const

void reset()

inline void setColperm(const colperm_t perm, int n)

inline void setColperm(const larray<colindex_t> &perm)

inline void setColperm(const std::vector<colindex_t> &perm)

void getRowperm(rowpermtypelight &rp) const: get lightweight row permutation

void getRowperm(rowperm_t &rperm) const: get row permutation

rowpermtypelight getRowperm() const: return lightweight row permutation

colpermtypelight getColperm() const: return column permutation

void getColperm(colpermtypelight &cp) const: set column permutation

inline void allocate_rowsortl(): allocate lightweight rowsort structure

inline void deleterowsortl()

inline void initrowsortl(): initialize rowsortl from rowsort

inline void rowsortl2rowsort(): copy rowsortl variable to rowsrt

void copydata(const dyndata_t &dd)

Public Members

colindex_t col: active column

rowindex_t N: number of rows

rowsort_t *rowsort: ordering of rows

rowsortlight_t *rowsortl

colperm_t colperm: current column permutation

Private Functions

void initdata(const dyndata_t &dd)