# The MADAG Strategy for Fault Location Techniques
## 3 The Proposed MADAG Strategy
### MADAG Strategy
In order to not undermine the sequential numbering in this tree, a group id would be represented as \(G_{2j}\) and \(G_{2j+1}\) from the parent node \(G_{j}\) (\(j\) starts from \(1\)). Even if one of the groups (leaf node) cannot be divided into any subgroups (the number of statements in this group is less than two or it cannot be divided anymore by any test case), we still keep the group number to show which group does not exist. Therefore, the \(k\)th level has \(2^{k-1}\) groups at most in the MADAG tree. On the \(k\)th level, the numbering of group id is \(G_{2^{k-1}}\leq G_{j}<G_{2^{k-1}}\). As an example of \(k=4\), the number of groups is \(2^{3}\), and the numbering ranges from \(G_{8}\) to \(G_{15}\). Figure 2: An example of the group division. The principle in the proposed strategy is that the number of statements of each group can be evenly divided by the selected test case on each level in the MADAG tree. That is, when selecting the next test case, our strategy is the minimum value of the difference between the sum of the node numbers of the two subtrees of the MADAG tree. This test case prioritization strategy is called Minimal Aggregate of the Diversity of All Groups' Elements (MADAG), and the Algorithm 1 is presented as follows:  
```
functionMADAG(\(T\)) define \(G_{j}\) denotes group id, and the group is a set that consists of statements \(\left|G_{j}\right|\) denotes the number of statements of this group set \(\left.\right.\) the selected test case set \(ST=\left\{\ \right\}\) the statements covered by the initial failed test case (\(t_{1^{\mu}}\)) as initial group \(G_{1}\) push \(t_{1^{\mu}}\) into \(ST\) on level 1 (\(k=1\)) such that \(ST=\left\{t_{1^{\mu}}\right\}\)\(T=T-ST\)\(\forall t_{i}\in T\). \(k=2\); loop {  select test cast \(t_{i}\) in \(ST\) by calculating the \(M_{i}\) of each test case at the \(k\) level divide \(G_{j}\) into \(G_{2j}\) and \(G_{2j+1}\) by division operation//Do(1,1), Do(1,0), Do(0,1), and Do(1,0) \(M_{i}(t_{i})=\left\{\sum_{j=2^{(0-1)},1}^{2^{(0-1)},1}\left|G_{2j}\right|- \left|G_{2j+1}\right|\right|\right\}\), \(\forall t_{i}\in T\). find the target test case \(t_{target}\) that has the minimal value of \(M_{i}(t_{i})\) on each level \(ST=ST\cup t_{target}\)\(s.t.\)\(T=T-ST\). \(k=k+1\); if all of the selected test cases have the same \(M_{i}(t_{i})\) value break; return \(ST\)
```  
**Algorithm 1**MADAG  
The algorithm receives a test suite \(T\) composed of test case \(t_{i}\) (\(\forall t_{i}\in T\)) and encounters the initial failed test case. In this algorithm, \(k\) denotes the level in the MADAG tree, \(G_{j}\) denotes the group id, and the group is a set that consists of statements. Moreover, \(\left|G_{j}\right|\) denotes the number of statements of this group. First, we fetch the statements covered by the initial failed test case as the initial group \(G_{1}\) and set the set \(ST\), which exists in the selected test cases. We push the initial failed test case \(t_{1^{\mu}}\) into \(ST\) at level 1 (\(k=1\)) such that \(ST=\left\{t_{1^{\mu}}\right\}\); then, \(T\) excludes set \(SK\) such as \(T=T-ST\). Hereafter, we calculate the \(M_{i}(t_{i})\) value of each test case at each level; here, the \(M_{i}(t_{i})\) value measures the capability of each  
Figure 3: MADAG tree. test case, which can divide the statements of the parent group by division operations (such as \(D_{0(1,1)}\), \(D_{0(1,0)}\), \(D_{0(0,1)}\), and \(D_{0(0,0)}\)). The formula for calculating \(M_{i}(t_{i})\) is as follows:  
\[M_{i}(t_{i})=\left\{\sum_{j=2^{(k-1)-1}}^{2^{(k-1)-1}}\left|\left|G_{2j}\right|- \left|G_{2j+1}\right|\right|\right\},\forall t_{i}\in T. \tag{1}\]  
Here, groups \(\left|G_{2j}\right|\) and \(\left|G_{2j+1}\right|\) are divided from \(G_{j}\) by a division operation. Subsequently, we find the target test case \(t_{target}\), which has the minimal value of \(M_{i}(t_{i})\) at each level. The \(M_{i}(t_{i})\) value is the smaller mean used to divide the statements of a group more evenly.