# Automatic Test Data Generation Using the Activity Diagram and Search-Based Technique
## 3 AutoTDGen Approach
### Automatic Data Flow Analysis and Test Data Generation
#### 3.3.1 Data Flow Analysis  
This subsection presents how the flow of data among activities in an AD is analyzed automatically. Algorithm 1 describes the generation of def-use pairs from an AD represented as an ET.  
```
Input: An AD model \(M\), a current given node \(c\), an initial node \(a_{i}\), an object variable \(v\) and a list of path \(P\): Outputs: \(L\): A list of all def - use pair paths
1: Begin
2:\(L\ \leftarrow\ \emptyset\)
3:\(P\ \leftarrow\ P\ +\ [c]\) #add current node to a path \(P\)
4:if\(c\ ==\ a_{i}\) return \(P\)
5:fornode \(c\) incoming edges, \(e\ =\ (m,n)\ \text{s.t}\ n\ \in\ E\)do
6:if\(c\) in \(M\) and node \(c\) has not been visited then
7: record edge \(e\) as the discovery edge for node \(c\)
8:#get previous node \(p\)
9:for\(v_{i}\) in \(c\) do: #Check the occurance of \(v\) in \(c\)
10: check the type of node \(c\):
11: append \(c\) to \(P\) as \(def_{a_{n}}^{v_{i}}\ Vpu_{d_{n}}^{v_{i}}\ Vcu_{a_{n}}^{v_{i}}\)
12: check the subsumption relationship
13:if\(P\) is subsumed by another \(P\) in \(L\)then
14:\(L\ \leftarrow\ P\ \land\ P\ \leftarrow\ Y\) #Set the prefix \(PF\) to yes
15:else
16:\(L\ \leftarrow\ P\ \land\ P\ \leftarrow\ N\) #Set the prefix \(PF\) to no
17:endfor
18:#set the previous node \(n\) as start node \(s\)
19:\(s\gets n\)
20: Recursively call \(ExtractDuPairs\ (M,s,a_{i},v,P)\)
21:endif
22:endfor
23: return \(L\)
24:endif
25:End
```  
**Algorithm 1**_ExtractDuPairs (\(M\), \(c\), \(a_{i}\), \(v\), \(P\)[]: The algorithm for automatically generating the def--use pair paths.  
The algorithm takes a model \(M\) of an AD in the form of an ET; a given node \(c\), which is the current node from which the tester wants to initiate the search; an initial node \(a_{i}\); an object variable \(v\); and a path \(P\). Starting from the given node \(c\) in \(M\) (and ensuring that \(c\) is not in \(P\)), the algorithm checks the properties for the corresponding node \(c\). If \(v\) is not in \(def\), the algorithm appends \(c\) to \(P\), sets the incoming node as the current node, and makes a recursive call. The iteration continues until it finds a node in which \(v\) is in \(def\) and returns the discovered def-use pair path \(P\). The algorithm also checks whether the path \(P\) is subsumed by another path or not via comparing the currently discovered \(P\) with the one previous appended to the list \(L\). The subsumed relationship indicates the reachability of a path concerning individual test data. As depicted in Table 1, if the path \(P\) is subsumed, its prefix is set to Y which means that the path \(P\) is subsumed and appends the discovered path \(P\) to the list \(L\). Otherwise, its prefix is set to \(N\), meaning that the path P is not subsumed and appends the discovered \(P\) to \(L\). Simply put, the algorithm finds the \(def\) of \(v_{i}\) used in a given node anywhere in the model by searching backward or forward based on the tester's preference.  
An example of generated def-use pair paths is depicted in Table 1. To save space, the textual element names are denoted as numerical values except for the decision element that includes guard conditions used to guide the search. The prefix \"Y\" signifies that the def-use pair is subsumed by another path, and the prefix \"N\" means that the def-use pair is not subsumed by any other path or paths. The corresponding AD for Table 1 is provided in Figure A1, the appendix section (Appendix A).