header
Set Cover

Tag:
Edit edit   Starstar

Program Information

Name: Set Cover
Domain: Optimization algorithms
Functionality: Solving the so-called set cover problem,which is also named key-lock problem.
Input: M:An $p \times q$ matrix ,where an element $m_{i,j}$ of M is either 0 or 1, and $m_{i,j} = 1$ denotes that the ith key can open the jth lock(Type: Matrix)
Output: C: An integer(Type: Integer) $K(k_{1},k_{2},\cdots,k_C)$: An array, where K contains C keys that can open all keys(Type: Array)

Reference

 How Effectively Does Metamorphic Testing Alleviate the Oracle Problem?http://dx.doi.org/10.1109/TSE.2013.46

MR Information

MR1------

Description:
Property:
Source input: $M_s$
Source output: $C_s,K_s$
Follow-up input: $M_f$
Follow-up output: $C_f,K_f$
Input relation: $M_f$ = Adding a column of “1” at the left of $M_s$, which means a lock that can be opened by all keys.
Output relation: $C_f = C_s$ $K_f = K_s$
Pattern:

MR2------

Description:
Property:
Source input: $M_s$
Source output: $C_s,K_s$
Follow-up input: $M_f$
Follow-up output: $C_f,K_f$
Input relation: $M_f$ = Changing the row order of $M_s$ between any pair of adjacent selected keys.
Output relation: $C_f = C_s$ $K_f = K_s$
Pattern:

MR3------

Description:
Property:
Source input: $M_s$
Source output: $C_s,K_s$
Follow-up input: $M_f$
Follow-up output: $C_f,K_f$
Input relation: The element $m^f_{i,j}$ of $M_f$ = 1 - the element $m^s_{(p-i+1),j}$of $M_s$
Output relation: $K_f = (k^f_{1},k^f_{2}, \cdots ,k^f_{C_f})$ $K_s = (k^s_{1},k^s_{2}, \cdots ,k^s_{C_s})$ $k^f_{1} \ne p - k_{1} + 1$
Pattern:

MR4------

Description:
Property:
Source input: $M_s$
Source output: $C_s,K$
Follow-up input: $M_f$
Follow-up output: $C_f,K$
Input relation: $M_f$ = The first $C_s$ rows are the same as the $k_{1}th$,$k_{2}th$, \cdots ,$k_{C_s}th$ rows of $M_s$, and the remaining $p-C_s$ rows stores the data corresponding to unselected keys.
Output relation: $C_f = C_s$ $K = (1,2,\cdots ,C_s)$
Pattern:

MR5------

Description:
Property:
Source input: $M_s$
Source output: $C_s,K_s$
Follow-up input: $M_f$
Follow-up output: $C_f,K_f$
Input relation: $M_f$ = Deleting one useless row of $M_s$, which means unselected keys.
Output relation: $C_f = C_s$ $K_f = K_s$
Pattern:

MR6------

Description:
Property:
Source input: $M_s$
Source output: $C_s,K_s$
Follow-up input: $M_f$
Follow-up output: $C_f,K_f$
Input relation: $M_f$ = Adding a row of “0” at the bottom of $M_s$, which means a key that cannot open any lock.
Output relation: $C_f = C_s$ $K_f = K_s$
Pattern:

MR7------

Description:
Property:
Source input: $M_s$
Source output: $C_s,K_s$
Follow-up input: $M_f$
Follow-up output: $C_f,K_f$
Input relation: $M_f$ = Adding a row that is the subset of one existing row at the bottom of $M_s$, which means a key whose opened locks are the subset of those of one existing key.
Output relation: $C_f = C_s$ $K_f = K_s$
Pattern:

MR8------

Description:
Property:
Source input: $M_s$
Source output: $C_s,K_s$
Follow-up input: $M_f$
Follow-up output: $C_f,K_f$
Input relation: $M_f$ = Deleting the jth column whose $m_{i_{1},j} = 0$ from $M_s$, which means a lock that cannot be opened by the first selected key.
Output relation: $C_f = C_s$ $K_f = K_s$
Pattern:

MR9------

Description:
Property:
Source input: $M_s$
Source output: $C_s,K_s$
Follow-up input: $M_f$
Follow-up output: $C_f,K_f$
Input relation: $M_f$ = Adding a row that is the same as one existing row at the bottom of $M_s$,which means a key that is the same as one existing key.
Output relation: $C_f = C_s$ $K_f = K_s$
Pattern:

MR10------

Description:
Property:
Source input: $M_s$
Source output: $C_s,K_s$
Follow-up input: $M_f$
Follow-up output: $C_f,K_f$
Input relation: $M_f$ = Deleting the first row and all columns whose first element value is “1” of $M_s$, which means deleting the first key and all the locks that it can open.
Output relation: $C_f = C_s -1$ $K_f = ( k^f_{1},k^f_{2},\cdots,k^f_{C_f})$, where $k^f_l = k^s_{l+1}$ if $k^s_{l+1}<k^s_{1}$ or $k^f_l = k^s_{l+1} -1$ if $k^s_{l+1}>k^s_{1}$.
Pattern:

MR11------

Description:
Property:
Source input: $M_s$
Source output: $C_s,K_s$
Follow-up input: $M_f$
Follow-up output: $C_f,K_f$
Input relation: $M_f$ = Adding some columns whose first element value is “1” and the other values are all “0”, which means adding some locks that can only be opened by the first key.
Output relation: $C_f = C_s$ $K_f = K_s$
Pattern:

MR12------

Description:
Property:
Source input: $M_s$
Source output: $C_s,K_s$
Follow-up input: $M_f$
Follow-up output: $C_f,K_f$
Input relation: $M^f_{2p \times q}$, where $m^f_{i,j} = m^s_{i,j}$and $m^f_{(p+i),j}= m^s_{i,j}$
Output relation: $C_f = C_s$ $K_f = K_s$
Pattern:

MR13------

Description:
Property:
Source input: $M_s$
Source output: $C_s,K_s$
Follow-up input: $M_f$
Follow-up output: $C_f,K_f$
Input relation: $M_f$ = Changing the order of columns of $M_s$.
Output relation: $C_f = C_s$ $K_f = K_s$
Pattern:

MR14------

Description:
Property:
Source input: $M_s$
Source output: $C_s,K_s$
Follow-up input: $M_f$
Follow-up output: $C_f,K_f$
Input relation: $M_f$ is a new $(p+a) \times q$ (a is a positive integer) matrix, whose first p rows are identical to $M_s$.
Output relation: The number of locks that can be opened by $k^f_{1}$ is larger or equal to that of $k^s_{1}$.
Pattern:

MR15------

Description:
Property:
Source input: $M_s$
Source output: $C_s,K_s$
Follow-up input: $M_f$
Follow-up output: $C_f,K_f$
Input relation: $M_f$ is a new $(p+a) \times (q+a)$ (a is a positive integer) matrix , the top-left $p \times q$ part is identical to $M_s$, the right-bottom $a \times a$ part is identical to a $a \times a$ unit matrix,and all the element in other parts are zero.
Output relation: $C_f = C_s + a$ $K_f = {k^s_{1},k^s_{2},\cdots,k^s_{C_s},p+1,p+2,\cdots,p+a}$
Pattern:
Insert title here