# Minimum Number of Test Paths for Prime Path and Other Structural Coverage Criteria

Anurag Dwarakanath, Aruna Jankiti

► To cite this version:

Anurag Dwarakanath, Aruna Jankiti. Minimum Number of Test Paths for Prime Path and Other Structural Coverage Criteria. 26th IFIP International Conference on Testing Software and Systems (ICTSS), Sep 2014, Madrid, Spain. pp.63-79, 10.1007/978-3-662-44857-1_5 . hal-01405275

HAL Id: hal-01405275

https://inria.hal.science/hal-01405275

Submitted on 29 Nov 2016

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Minimum Number of Test Paths for Prime Path and other Structural Coverage Criteria

Anurag Dwarakanath and Aruna Jankiti

Accenture Technology Labs, Bangalore, India

anurag.dwarakanath@accenture.com, jankiti.aruna@accenture.com

**Abstract.** The software system under test can be modeled as a graph comprising of a set of vertices, *V* and a set of edges, *E*. Test Cases are Test Paths over the graph meeting a particular test criterion. In this paper, we present a method to achieve the minimum number of Test Paths needed to cover different structural coverage criteria. Our method can accommodate Prime Path, Edge-Pair, Simple & Complete Round Trip, Edge and Node coverage criteria. Our method obtains the optimal solution by transforming the graph into a flow graph and solving the minimum flow problem. We present an algorithm for the minimum flow problem that matches the best known solution complexity of $O(|V||E|)$. Our method is evaluated through two sets of tests. In the first, we test against graphs representing actual software. In the second test, we create random graphs of varying complexity. In each test we measure the number of Test Paths, the length of Test Paths, the lower bound on minimum number of Test Paths and the execution time.

**Keywords:** Model Based Testing, Minimum Number of Test Paths, Prime Path Coverage, Minimum Flow

## 1 Introduction

In model based testing, the software artifact describing the system under test (SUT) is abstracted through a model [2]. The model can be created from requirements, design or code [2]. Models are typically represented in the form of a graph, comprising of vertices and edges. Two special vertices are marked, the source vertex, *s*, and the sink vertex, *t*. The graph is then used to generate Test Cases. A Test Case consists of a Test Path, Test Data, and Expected Results. The Test Path is a path in the graph from *s* to *t*. The number of Test Paths needed to test the SUT is determined by the coverage criterion. For example, Node Coverage implies that the set of Test Paths should collectively visit all vertices in the graph. Similarly, Edge Coverage requires the Test Paths to visit all edges in the graph and Prime Path coverage requires the Test Paths to tour a particular set of paths. Prime Path coverage provides a better quality of coverage as it subsumes Node Coverage and Edge Coverage [2].

Given a particular coverage criterion, it is important to determine a small set of Test Paths which satisfy the criterion. The number and the overall length
of Test Paths directly impacts the amount of time needed to manually execute the test cases. Finding the minimum number of Test Paths needed to satisfy a particular criterion is non-trivial even for the simplest case of node coverage. Using better coverage criterion like Prime Path complicates the problem further since even a small graph can have a large number of Prime Paths [6].

In this paper, we present a method to obtain the optimal solution for the minimum number of Test Paths for different structural coverage criteria. The contribution of our work includes a) a generic method for obtaining the minimal number of Test Paths for different structural coverage criteria; b) identification of a lower bound on the minimum number which the experimental results show to perform very well; c) a new method for computation of minimum number of Test Paths which matches the best known solution complexity.

The identification of the minimum number of Test Paths, although possible in polynomial time, requires a number of graph transformations. We thus test the applicability of our solution against a simple algorithm for Test Path generation. The tests compare the number and length of Test Paths identified and the algorithm execution time. These metrics are compared on a set of manually created graphs representing actual code and a set of randomly generated graphs.

The paper is structured as follows. We present the related work in Section 2. The method of generating the minimum Test Paths is presented in Section 3. We present the experimental results in Section 4 and conclude in Section 5.

## 2 Related Work

The input for the identification of minimum Test Paths is a directed graph $G_1 = (V_1, E_1)$, where $V_1$ represents the vertex set and $E_1$ represents the edge set. $G_1$ is typically a control flow graph of the SUT. $G_1$ may contain cycles. $V_1$ contains the source vertex, $s$, and the sink vertex, $t$. $s$ conceptually depicts the point where the execution of a Test Case begins and $t$ denotes the point where the execution ends. The in-degree of $s$ is 0, and the out-degree of $t$ is 0. We focus on the case where $|s| = |t| = 1$. There is no loss in generality since a graph with more than one $s$ or $t$ can be converted to a graph with a single $s$ and a single $t$, by adding two new vertices, $s'$, $t'$ with edges between $s'$ and every source, and edges between every sink and $t'$.

A path is a sequence of vertices $v_0, \dots, v_r$ with a sequence of edges $e_0, \dots, e_{r-1}$, where $e_i = (v_i, v_{i+1})$, $v_i \in V_1$, $e_i \in E_1 \forall i$. An $s-t$ path is a path where $v_0 = s$ and $v_r = t$. All Test Paths are thus $s-t$ paths. A path, $p$ is said to visit vertex $k$ (or edge $e$) if $k$ (or $e$) is in $p$. A path $p$ is said to tour (or cover) a path $q$, if $q$ is a sub-path of $p$. A path is simple if no vertex is visited more than once with the exception that the first and last nodes may be identical [2]. A Prime Path is a simple path that is not a sub-path of any other simple path [2].

A test requirement is a specific aspect that a Test Path satisfies. $TR$ denotes the set of test requirements. For example, for Prime Path coverage, $TR$ = set of Prime Paths. For Edge Coverage, $TR$ = the set of edges, etc.
A simple solution approach for the generation of Test Paths that cover all Prime Paths has been presented in [2]. The solution ‘extends’ every Prime Path to visit *s* and *t* thus forming a Test Path. The algorithm does not attempt to minimize the number of Test Paths but is extremely fast in execution.

The problem of minimizing Test Paths for Prime Path coverage has been recently studied in [7]. The authors formulate the problem as a variant of the shortest superstring problem, which is NP-complete [7]. The authors then use known approximation algorithms to solve the problem. In our work, we formulate the problem such that the optimal solution is obtained in polynomial time.

While the work in [7] specifically deals with Prime Paths, the problem of minimum Test Path to cover a given set of paths (not necessarily Prime Paths) has been studied earlier in [8]. Here, the given graph, $G_1$, is transformed into a flow network such that the minimum flow gives the minimum number of Test Paths. The authors use a generic algorithm for minimum flow. One such simple algorithm for minimum flow is the Decreasing Path algorithm [4] which leads to the solution in $O(|V|^2|E|)$. However, the methodology in [8] has an inaccuracy which can lead to incorrect results. Consider the graphs in Fig. 1. The Prime Paths of Fig. 1(a) are {1, 2, 3} and {2, 2}. The technique in [8] makes the graph acyclic by introducing a new vertex $2'$ in place of the strongly connected component of 2 - 2. The minimum flow analysis is then performed on the acyclic graph Fig. 1(b). This results in a minimum number of Test Paths as 1 the path being 1, $2'$, 3. Replacing $2'$, we get the path as 1, 2, 2, 3 to correspond to Fig. 1(a). However, the minimum number of paths to cover the Prime Paths is 2 - {1, 2, 3} and {1, 2, 2, 3}. Our method overcomes this inaccuracy by appropriately handling strongly connected components. Further, our solution of minimum Test Paths is computed in $O(|V||E|)$.

<figure><img src="image_2.png" /><figcaption>Fig. 1. (a) Graph with a cycle (b) reduced to an acyclic graph.</figcaption></figure>

The authors of [1] tailor a minimum flow algorithm specifically for minimum Test Paths for node coverage leading to the currently best known solution complexity of $O(|V|^2|E|)$. Our algorithm in this paper also achieves this complexity. However, our technique is different and is based on the concept of Decreasing Paths [4]. The concept is similar to that of the Augmenting Path in the Ford-Fulkerson algorithm [5] to find the maximum flow. The Augmenting Path concept is well studied and numerous explanatory material is available. This allows our algorithm based on the Decreasing Path to be easily understood and conceptually simple. Further, our method is generic and handles different coverage criteria including node coverage.

Table 1 summarizes the distinction of our method against related work.
<table><caption>**Table 1.** Comparison of our solution against related work</caption><thead><tr><th>Solution</th><th>Coverage Criteria</th><th>Comments</th></tr></thead><tbody><tr><td>[2]</td><td>Prime Path</td><td>Does not attempt to minimize</td></tr><tr><td>[1]</td><td>Node Coverage</td><td>Minimization in O(|V||E|)</td></tr><tr><td>[8]</td><td>Different structural coverage criteria</td><td>In-accuracy in solution.<br>Minimization in O(|V|<sup>2</sup>|E|)</td></tr><tr><td>[7]</td><td>Different structural coverage criteria</td><td>Heuristic solution (non-optimal)</td></tr><tr><td>Our Work</td><td>Different structural coverage criteria</td><td>Minimization in O(|V||E|)</td></tr></tbody></table>

Our method to obtain the minimum number of Test Paths is presented below.

## 3 Generating the minimum number of Test Paths

Given a graph $G_1 = (V_1, E_1)$, we need to find the minimum number of Test Paths that cover the set of test requirements $TR$. We focus for the case of $TR$ = set of Prime Paths of $G_1$ and cover other coverage criteria in section 3.6. The minimum Test Paths are identified through a series of steps as shown below.

1. First, the set of Prime Paths, $P$ of $G_1$ is computed. We present a method to obtain the lower bound on the minimum number of Test Paths.

2. $G_1$ is converted into a transform graph $G_2 = (V_2, E_2)$, where $V_2$ is the set of Prime Paths, $P = \{p_1, p_2, \dots, p_n\}$ and $(p_1, p_2) \in E_2$ if a path exists from $p_1$ to $p_2$ on $G_1$ such that the path does not include any other Prime Paths (i.e. other than $p_1$ and $p_2$).

3. The transform graph $G_2$ is made into an acyclic graph, $G_3$. The work in [8] removed cycles from the original graph, $G_1$, instead of the transform graph, $G_2$. This inaccuracy in [8] can lead to incorrect results (refer Fig. 1).

4. $G_3$ is converted into a flow graph, $G_4$, with new vertices and edges introduced. Every edge is annotated with lower bounds and capacities of flows. The minimum flow on $G_4$ is computed through a two-step process. First, $G_4$ is initialized with a feasible flow. We present a novel initialization algorithm in this paper. Second, the generic Decreasing Path algorithm [4] is used to find the minimum flow. Our initialization algorithm ensures the Decreasing Path algorithm can compute with a complexity of $O(|V||E|)$.

5. The minimum flow in $G_4$ is now interpreted as Test Paths in $G_1$.

We detail each step of the process below. We will also use Fig. 2 as a running example to help explain the algorithms used.

### 3.1 Generating the set of Prime Paths

Algorithm 1 generates the set of test requirements $TR$ (Prime Paths in this case). We use known methods ([2] and [3]) to compute the set of Prime Paths.

For the example graph in Fig. 2, there are 10 Prime Paths: $P = \{p_0 = \{s, 1, 3, 4, 5\}, p_1 = \{3, 4, 1, 2, t\}, p_2 = \{5, 4, 1, 2, t\}, p_3 = \{1, 3, 4, 1\}, p_4 = \{s, 1, 2, t\}, p_5 = \{3, 4, 1, 3\}, p_6 = \{5, 4, 1, 3\}, p_7 = \{4, 1, 3, 4\}, p_8 = \{5, 4, 5\}, p_9 = \{4, 5, 4\}\}$.
<caption>**Algorithm 1:** Generating the set of Prime Paths</caption>

**Input:** $G_1 = (V_1, E_1)$, with $\{s, t\} \in V_1$
**Output:** Set of Prime Paths, $P = \{p_1, p_2, \dots, p_n\}$
1. initialize $P' = \{p_1, p_2, \dots, p_n\} = \{e_1, e_2, \dots, e_n\}, \forall e_i \in E_1$;
2. while $p_i \in P' \ \forall i$ is not explored do
3. &nbsp;&nbsp;&nbsp;&nbsp;if $p_i$ is not a cycle then
4. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if $p_i$ can be extended by edge $e \in E_1$ then
5. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if $e$ does not visit a vertex in $p_i$ then
6. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$p_i += e$;
7. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end
8. &nbsp;&nbsp;&nbsp;&nbsp;end
9. &nbsp;&nbsp;&nbsp;&nbsp;end
10. end
11. sort $P'$ in ascending order of size;
12. for $i = (|P'|)$ to 1 do
13. &nbsp;&nbsp;&nbsp;&nbsp;if $p_i$ is not a sub-path of any other path in $P$ then
14. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;add $p_i$ into $P$;
15. &nbsp;&nbsp;&nbsp;&nbsp;end
16. end
17. output $P$;

We define four categories of Prime Paths. *Type S* are those Prime Paths that visit the vertex *s*. *Type T* are those that visit the vertex *t*. *Type C* are those Prime Paths that are cycles, and *Type P* are those that are simple paths and do not visit either *s* or *t*. In the given example, we have the following cardinality - $|Type S| = 2$, $|Type T| = 3$, $|Type C| = 5$, $|Type P| = 1$. These categories hold for other test requirements (i.e. Nodes, Edges, Edge-pair, etc) as well.

**Lemma 1.** $\max(|Type S|, |Type T|)$ is a lower bound on the minimum number of Test Paths for Prime Path coverage.

*Proof.* Consider $P_T = \{p_1, p_2, \dots, p_n\}$ to be a set of *Type T* Prime Paths. Since each of these Prime Paths visits vertex *t*, the last node of every Prime Path $p_i \in P_T$ is the vertex *t*. Now, consider an *s* – *t* path that tours $p_1$. This *s* – *t* path cannot tour any other Prime Path of $P_T$ after touring $p_1$ since the vertex *t* has an out-degree of 0. Thus, there cannot be any path in the graph where more than 1 Prime Paths of $P_T$ can be toured simultaneously. Therefore, there would be at-least *Type T* *s* – *t* paths to cover all *Type T* Prime Paths. Similarly, there would be atleast *Type S* *s* – *t* paths to cover all *Type S* Prime Paths. Thus the number of s-t paths that will cover all Prime Paths will be atleast as much as $\max(|Type S|, |Type T|)$. □

The categorization of the Prime Paths can be achieved by checking the first and last vertex of every Prime Path. This can be done in $O(|P|)$. For the example graph of Fig. 2, the lower bound for the minimum number of Test Paths for Prime Path coverage = $|Type T| = 3$.
<figure><img src="image_3.png" /><figcaption>Fig. 2. Example Input Graph, $G_1$.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 3. Transform Graph, $G_2$ of $G_1$.</figcaption></figure>

## 3.2 Generating the Transform Graph

The Prime Paths are represented as vertices in a new graph, $G_2$. Edges are placed between two vertices in $G_2$ if a path in $G_1$ can tour the two Prime Paths represented by the vertices. The problem of Prime Path coverage is thus transformed into a problem of node coverage (i.e. we want to identify $s-t$ paths such that all vertices of $G_2$ are covered). The algorithm for generation of the transform graph is provided below.

**Algorithm 2: Generation of the Transform Graph**

**Input:** $G_1, P$
**Output:** Transform Graph $G_2 = (V_2, E_2)$
1. create new vertex $s, t$ in $V_2$; create new vertex $v_i$ in $V_2, \forall i \in P$;
2. **foreach** $p_i \in (P + \{s\})$ **do**
3. &nbsp;&nbsp;&nbsp;&nbsp;**foreach** $p_j \in (P - p_i + \{t\})$ **do**
4. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Path$_{ij}$ = $p_i \cup p_j$;
5. &nbsp;&nbsp;&nbsp;&nbsp;**if** Path$_{ij}$ contains only the prime paths $p_i$ and $p_j$ **then**
6. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;add edge $(p_i, p_j)$ into $E_2$;
7. &nbsp;&nbsp;&nbsp;&nbsp;**end**
8. **end**
9. **end**
10. output $G_2 = (V_2, E_2)$;

The Operator $\cup$ in Step 4 works as follows. Consider the case of $p_i = \{4, 5, 4\}$ and $p_j = \{5, 4, 5\}$, then $p_i \cup p_j = \{4, 5, 4, 5\}$ by observing that the paths $p_i$ and $p_j$ have overlapping vertices. In case of no overlap, $p_i \cup p_j = \{p_i + \text{shortest path from the last node of } p_i \text{ to the first node of } p_j\} + p_j$. Checking for the shortest path in $G_1$ can be done using breadth first search with a complexity of $O(E_1)$. Checking for the presence of a Prime Path in $Path_{ij}$ (step 5) can be done in $O(|P|)$. Thus, the transform graph can be computed in $O(|P|^2 * \max(|P|, |E_1|))$. The transform graph of Fig. 2 is shown in Fig. 3.

An incomparable vertex set, $I$, is one where for every pair of vertices $v_i, v_j \in I$; $v_i$ does not reach $v_j$. From Fig. 3, it can be visually seen that the three Type T Prime Paths, $p_1, p_2, p_4$, form an incomparable vertex set, i.e. $I = \{p_1, p_2, p_4\}$. The maximum incomparable vertex set, $I_{max}$ equals the minimum number of Test
Paths through Dilworth's theorem for acyclic directed graphs and the proof in
[8] for general graphs. From Lemma 1, $|I_{max}| \geq |I|$.

### 3.3 Removing Cycles

The transform graph, $G_2$, may have cycles. The minimum flow algorithm works over a directed acyclic graph and thus the cycles need to be removed. We achieve this by replacing a cycle with a new vertex. All incoming edges of any node in the cycle become incoming edges of the new vertex. Similarly, any outgoing edge of any vertex in the cycle become outgoing edges of the new vertex. Algorithm 3 presents the generation of the acyclic transform graph.

<table><caption>**Algorithm 3:** Reduction of Cycles in Transform Graph</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>Input:</td><td>$G_2$</td></tr><tr><td>Output:</td><td>Acyclic Transform Graph $G_3 = (V_3, E_3)$</td></tr><tr><td>1</td><td>initialize $V_3 = V_2, E_3 = E_2, G_3 = (V_3, E_3)$;</td></tr><tr><td>2</td><td>while $G_3$ contains a cycle do</td></tr><tr><td>3</td><td>let $p_c = \{v_1, v_2, \dots, v_n, v_1\}$ be a cycle;</td></tr><tr><td>4</td><td>record vertices $v_i \in V_3$ which have an edge in $E_3$ with vertices in $p_c$;</td></tr><tr><td>5</td><td>remove vertices $\{v_1, v_2, \dots, v_n\}$ from $V_3$; create new vertex $v_{new}$ in $V_3$;</td></tr><tr><td>6</td><td>foreach vertex $v_i \in p_c$ do</td></tr><tr><td>7</td><td>if $v_i$ has an edge from vertex $v_k$ in $G_2$ where $v_k \in V_3 - p_c$ then</td></tr><tr><td>8</td><td>remove edge $(v_k, v_i)$ from $E_3$ & create edge $(v_k, v_{new})$ in $E_3$;</td></tr><tr><td>9</td><td>end</td></tr><tr><td>10</td><td>if $v_i$ has an edge to vertex $v_k$ in $G_2$ where $v_k \in V_3 - p_c$ then</td></tr><tr><td>11</td><td>remove edge $(v_i, v_k)$ from $E_3$ & create edge $(v_{new}, v_k)$ in $E_3$;</td></tr><tr><td>12</td><td>end</td></tr><tr><td>13</td><td>end</td></tr><tr><td>14</td><td>end</td></tr><tr><td>15</td><td>output $G_3 = (V_3, E_3)$;</td></tr></tbody></table>

Algorithm 3 works as follows. For the given transform graph, the cycles are computed using a trivial variant of Algorithm 1. If the graph contains a cycle, any cycle is chosen and reduced to a new vertex. On the resulting graph, the cycles are identified again and the procedure is repeated. The complexity of steps 6-13 is $O(|V_2|)$ by assuming that the chosen cycle visits every vertex. Since, $V_2$ represents the Prime Paths, this complexity can be written as $O(|P|)$. If we assume every Prime Path is of Type C and reducing one cycle does not impact other Prime Paths, then the complexity of the entire algorithm can be said to be $O(|P| * \max(|P|, P_c))$, where $P_c$ is the complexity of finding a cycle. After removing all the cycles, the acyclic transform graph is shown in Fig. 4.

### 3.4 Generating the Minimum Flow

The transform graph, $G_3$, at this stage is a directed acyclic graph. We convert this graph into a flow graph. Each vertex $v_i \in V_3 - \{s, t\}$ is split into two vertices
$v_i^+, v_i^{++}$. Let this new vertex set be represented as $V_4$. New edges $(v_i^+, v_i^{++})$ are also added. All incoming edges of $v_i$ are made incoming edges of $v_i^+$ and all outgoing edges of $v_i$ are made outgoing edges of $v_i^{++}$. Let this new edge set be represented as $E_4$. Every edge $(i, j) \in E_4 \& i, j \in V_4$ is associated with a lower bound $(l_{ij})$ for a flow and an edge capacity $(c_{ij})$ as follows:

$$l_{ij} = \begin{cases} 1 & \text{if } (i, j) = (v_i^+, v_i^{++}) \\ 0 & \text{otherwise} \end{cases}$$ $$c_{ij} = \frac{|V_4|}{2} - 1$$

Let the resulting graph be represented as $G_4 = (V_4, E_4, L, C)$, where L is the set of lower bounds and C is the set of capacities. The introduction of new vertices, new edges and the flow requirements are pictorially depicted in Fig.5.

A feasible flow in the flow network is an assignment of a non-negative value, $f_{ij}$ for every edge such that the following conditions hold.

$$f_{ij} \ge l_{ij} \ \& \ f_{ij} \le c_{ij}, \forall (i, j) \in E_4 \ \& \ i, j \in V_4 \quad (1)$$

$$\sum_{i} f_{ij} = \sum_{j} f_{ji}, \forall (i, j) \in E_4 \ \& \ i, j \in V_4 - \{s, t\} \quad (2)$$

The flow of the network, $f$, is defined as:

$$f = \sum_{j} f_{sj} = \sum_{i} f_{it}, \forall (i, j) \in E_4 \ \& \ i, j \in V_4 \quad (3)$$

The minimum flow, $f_{min}$, is the least amount of feasible flow possible.

A flow in the network $G_4$ can be mapped to an $s-t$ path in $G_1$. The flow conditions placed in $G_4$ ensures the edge $(v_i^+, v_i^{++})$ is chosen in at-least one flow. Since this corresponds to every vertex $v_i \in V_3 - \{s, t\}$, the minimum flow will ensure every vertex of $G_3$ is covered. By expanding vertexes placed in lieu of cycles in $G_3$, every vertex of $G_2$ is covered. This ensures that every Prime Path of $G_1$ is toured.

Every edge in $G_4$ is also annotated with a capacity, $c_{ij}$, which represents the maximum flow that may be carried on the edge. The capacity is not directly interpretable from the Test Path perspective; however, the minimum flow algorithm requires the specification of a capacity. In the general case of computing the minimum flow in a network, the capacity determines if a feasible flow exists. In our case, we set the capacity in such a way that it guarantees a feasible flow.

**Theorem 1.** The capacity on an edge in $G_4$ can be set as $\frac{|V_4|}{2} - 1$.

*Proof.* Consider the graph $G_3$. The maximum number of $s-t$ paths possible on $G_3$ will be $(|V_3| - 2)$. This is because, the maximum will occur when every vertex of $G_3 - \{s, t\}$ leads to a new $s-t$ path. Now, new vertices have been added in $G_4$, but none of the new vertices will contribute to a new path over and above those that are possible in $G_3$. Thus, the maximum capacity of every edge in $G_4$ can be set as $(|V_3| - 2)$. But since $|V_4| = 2 * |V_3| - 2 \Rightarrow (|V_3| - 2) = \frac{|V_4|}{2} - 1$. □
<figure><img src="image_5.png" /><figcaption>**Fig. 4.** Creating an acyclic directed graph, **Fig. 5.** Vertex Splitting and flow requirements represented as lower bound; capacity $G_3$ from $G_2$.</figcaption></figure>

Once the flow graph has been created, we determine the minimum flow through the technique similar to [4].

The minimum flow algorithm works in two steps, a) an initial flow is placed on the flow graph such that all flow requirements (1 & 2) are met; and b) the minimum flow is computed using the decreasing path algorithm. Using the algorithms for a) and b) as detailed in [4] over the network $G_4$ provides a method with a complexity of $O(|V_4||E_4|c_{max})$, where $c_{max}$ represents the maximum value of the capacity, C. From Theorem 1, $c_{max} = O(|V_4|)$. Therefore, the complexity of the method in [4] becomes $O(|V_4|^2|E_4|)$. This complexity can be generalized as $O(|V|^2|E|)$. Our work in this paper introduces a novel initialization algorithm (i.e. aspect a)) such that the complexity of computing the minimum flow using the standard decreasing path algorithm becomes $O(|V_4||E_4|)$. This complexity can be generalized to $O(|V||E|)$.

**Initialization with a feasible flow** Given the graph $G_4 = (V_4, E_4, L, C)$, Algorithm 4 places an initial flow such that the flow requirements 1 & 2 are met.

<table><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>Algorithm 4: Initialization with a feasible flow</td><td></td></tr><tr><td>Input: $G_4 = (V_4, E_4, L, C)$</td><td></td></tr><tr><td>Output: feasible flow $f_{ij}, \forall (i, j) \in E_4 \& i, j \in V_4$</td><td></td></tr><tr><td>1 initialize $f_{ij} = 0, \forall (i, j) \in E_4 \& i, j \in V_4$;</td><td></td></tr><tr><td>2 <b>foreach</b> vertex $i \in V_4 - \{s, t\}$ <b>do</b></td><td></td></tr><tr><td>3 find path, $p_s$, from $s$ to $i$ using breadth-first-search;</td><td></td></tr><tr><td>4 find path, $p_t$, from $i$ to $t$ using breadth-first-search;</td><td></td></tr><tr><td>5 path, $p = p_s + p_t$;</td><td></td></tr><tr><td>6 $k = \min \{(f_{mn} - l_{mn}), \forall (m, n) \in p\}$;</td><td></td></tr><tr><td>7 <b>if</b> $k < 0$ <b>then</b></td><td></td></tr><tr><td>8 <b>foreach</b> edge $(m, n) \in p$ <b>do</b></td><td></td></tr><tr><td>9 $f_{mn} = 1$;</td><td></td></tr><tr><td>10 <b>end</b></td><td></td></tr><tr><td>11 <b>end</b></td><td></td></tr><tr><td>12 <b>end</b></td><td></td></tr></tbody></table>
**Theorem 2.** *Algorithm 4 ensures flow requirements are met.*

*Proof.* Consider a vertex, $i$, in $G_3$. This vertex will now be represented by $i^+$ and $i^{++}$ in $G_4$. A path from $s$ to $i^{++}$ will cover the edge $(i^+, i^{++})$ since $i^{++}$ is reachable only through $i^+$. Thus, incrementing the flow along the path from $s$ to $i^{++}$ will ensure that the flow condition of $l_{ij} = 1$ for $(i, j) = (i^+, i^{++})$ is met. By checking $\forall i \in V_4$, ensures flow requirement (1) for all edges is met. The increments of the flow is done for every edge of a path from $s$ to $t$. Consider the vertex $i^+$ in $G_4$. Let it have $m$ incoming edges. Since $i^+$ is created by splitting vertex $i$, $i^+$ will have 1 outgoing edge. Let vertex $i^+$ be part of an $s-t$ path $n$ number of times where $1 \le n \le \frac{|V_4|}{2} - 1$. The $m$ incoming edges will be visited $n$ times with each visit incrementing the flow by 1. Thus the sum of flows on the incoming edges will be $n$. Similarly, the outgoing edge will be visited $n$ times and will also have a flow of $n$. Thus, by incrementing the flow of every edge of an $s-t$ path ensures flow requirement (2) is met. $\square$

Breadth first search has a complexity of $O(|E|)$. Therefore Algorithm 4 has a complexity of $O(|E_4||V_4|)$.

Once an initial flow is placed on the flow graph, the minimum flow is computed using the decreasing path algorithm.

**Decreasing Path algorithm to find the minimum flow** We use the generic Decreasing Path algorithm as detailed in [4]. The algorithm is based on the Augmenting Path concept of the Ford-Fulkerson algorithm [5]. The Decreasing Path concept can be stated as follows. Every edge in $G_4$ is termed as a forward edge. Let this set be called $E_4^f$. For every forward edge, a new backward edge is introduced; i.e. a forward edge of the form $(i, j)$, will have a backward edge of the form $(j, i)$. Let this set of backward edges be called $E_4^b$. For each backward edge, the lower bound, $l_{ij}$, is set to 0 and the capacity, $c_{ij}$ is set to $\frac{|V_4|}{2} - 1$. The residual capacity of an edge, $r_{ij}$, $\forall (i, j) \in E_4^f \cup E_4^b$, is defined as follows:

$$r_{ij} = \begin{cases} f_{ij} - l_{ij} & \text{if } (i, j) \in E_4^f \\ c_{ij} - f_{ij} & \text{if } (i, j) \in E_4^b \end{cases}$$

A decreasing path is a path from $s$ to $t$ where the residual capacity of every edge is greater than 0. If a decreasing path visits a forward edge, then the flow on the edge can be reduced. If on the other hand, the decreasing path visits a backward edge, then the flow on the corresponding forward edge has to be increased. The flow in the graph will be minimum when no more decreasing paths can be found. The minimum flow is the optimal solution as proved in [4].

The algorithm to compute the minimum flow is presented as Algorithm 5.

The complexity of the Decreasing Path algorithm can be determined using the technique in [4]. Each reduction of the flow in the network will need $O(|E_4|)$ because of the path found through breadth first search. Since the maximum flow that may be initialized is $\frac{|V_4|}{2} - 1$ (from Theorem 1), the minimum flow will be found in $O(|V_4||E_4|)$. This can be generalized to $O(|V||E|)$.
<caption>**Algorithm 5:** Decreasing Path Algorithm</caption>

**Input:** $G_4 = (V_4, E_4, L, C)$, with initial flow
**Output:** minimum flow $f$ and flows on $G_4$
1 **foreach** edge $(i, j) \in E_4$ **do**
2 &nbsp;&nbsp;&nbsp;&nbsp;put $(i, j)$ in $E_4^f$;
3 &nbsp;&nbsp;&nbsp;&nbsp;put $(j, i)$ in $E_4^b$; $l_{ji} = 0$; $c_{ji} = \frac{|V_4|}{2} - 1$;
4 **end**
5 **while** path $p$, $p$ exists from $s$ to $t$ using breadth-first-search such that
$r_{mn} > 0, \forall (m, n) \in p$ **do**
6 &nbsp;&nbsp;&nbsp;&nbsp;$r_{min} = \min\{r_{mn}, \forall (m, n) \in p\}$;
7 &nbsp;&nbsp;&nbsp;&nbsp;**foreach** edge $(m, n) \in p$ **do**
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $(m, n) \in E_4^f$ **then**
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$f_{mn} = r_{min}$;
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else**
11 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$f_{mn} = r_{min}$;
12 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end**
13 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$f_{nm} = f_{mn}$;
14 &nbsp;&nbsp;&nbsp;&nbsp;**end**
15 **end**
16 output $f = \sum_j f_{sj}, G_4$;

The overall complexity of the minimum flow algorithm is the maximum of the complexity between the initialization and the decreasing path algorithm.

max (initialization algorithm, decreasing path algorithm) =

$$ \max (O(|V||E|), O(|V||E|)) = O(|V||E|) \quad (4) $$

Thus, the complexity of our method of $O(|V||E|)$ improves upon the complexity of the generic minimum flow algorithm of $O(|V|^2|E|)$.

For the running example, the minimum flow is computed as 3 which can be quite clearly observed from Fig. 4. The minimum flow incidentally equals the lower bound for the example.

## 3.5 Generating the Minimum Test Paths from the Minimum Flow

The minimum number of $s-t$ paths to cover all the Prime Paths is the flow, $f$, in $G_4$. The $s-t$ paths in $G_4$ and the corresponding paths in $G_1$ are identified using Algorithm 6.

Steps 3 to 7 identify the paths corresponding to the minimum flow in $G_3$. For the running example, the path$^{G3} = \{s, p_4, t\}, \{s, v_3, p_1, t\}$ and $\{s, p_0, v_3, p_2, t\}$.

Vertices in path$^{G3}$ which represent cycles in $G_2$ are replaced. In the running example, there are no cycles to be introduced in the first path $\{s, p_4, t\}$. Replacing $v_3$ in the second path gives $\{s, p_3, p_5, v_2, p_3, p_1, t\}$. Note that although $v_3$ represents the cycle $\{v_2, p_3, p_5, v_2\}$, it is replaced as $\{p_3, p_5, v_2, p_3\}$ such that an
edge exists between $s$ and $p_3$. Step 10 performs this operation. Replacing $v_2$ gives $\{s, p_3, p_5, p_7, v_1, p_6, p_7, p_3, p_1, t\}$. Replacing $v_1$ gives the path $\{s, p_3, p_5, p_7, p_9, p_8, p_9, p_6, p_7, p_3, p_1, t\}$. Similarly, after replacing the cycles in the third path, we get $\{s, p_0, p_9, p_8, p_9, p_6, p_7, p_9, p_8, p_9, p_6, p_7, p_2, t\}$.

<caption>**Algorithm 6:** Identifying minimum Test Paths from minimum flow</caption>

**Input:** $G_4 = (V_4, E_4, L, C)$, with flow on each edge & minimum flow $f$
**Output:** All s-t paths, $path^{G_1}$, on $G_1$ corresponding to the minimum flow
1 &nbsp; Remove all backward edges of $G_4$. Merge vertices of the form $\{v^+, v^{++}\}$ into $v$. Incoming edges of $v$ = incoming edges of $v^+$. Outgoing edges of $v$ = outgoing edges of $v^{++}$. Let the resulting graph be $G_3$;
2 &nbsp; **for** $i = 0$ **to** $f$ **do**
3 &nbsp;&nbsp;&nbsp;&nbsp; remove all edges from $G_3$ which have flow of 0;
4 &nbsp;&nbsp;&nbsp;&nbsp; find path, $path^{G_3}$, from $s$ to $t$ using breadth-first-search;
5 &nbsp;&nbsp;&nbsp;&nbsp; **foreach** $edge(m, n) \in path^{G_3}$ **do**
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $f_{mn} = 1$;
7 &nbsp;&nbsp;&nbsp;&nbsp; **end**
8 &nbsp;&nbsp;&nbsp;&nbsp; **while** $path^{G_3}$ contains a vertex, $v_c^{G_3}$, reduced from a cycle, $c$ **do**
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Let the cycle be represented as $c = \{v_1^{G_2}, v_2^{G_2}, \dots, v_1^{G_2}\}$;
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; replace $v_c^{G_3}$ with $c = \{v_j^{G_2}, v_{j+1}^{G_2}, \dots, v_j^{G_2}\}$ where $v_{c-1}^{G_3}$ is connected to $v_j^{G_2}$ through the information recorded in Algorithm 3 Step 4;
11 &nbsp;&nbsp;&nbsp;&nbsp; **end**
12 &nbsp;&nbsp;&nbsp;&nbsp; $path^{G_2} = path^{G_3}$;
13 &nbsp;&nbsp;&nbsp;&nbsp; ensure an edge exists between every vertex of $path^{G_2}$ in $G_2$;
14 &nbsp; **end**
15 &nbsp; **foreach** $path^{G_2}$ **do**
16 &nbsp;&nbsp;&nbsp;&nbsp; **foreach** cycle, $c'$ in $path^{G_2}$ **do**
17 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **if** number of occurrences of $c'$ in all paths $path^{G_2} > 1$ **then**
18 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; except the first instance, replace all other instances of $c'$ in $path^{G_2}$ with the first vertex of $c'$;
19 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **end**
20 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; let $path_{sub} = c'$-first & last vertices of $c'$;
21 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **if** number of occurrences of $path_{sub}$ in all paths $path^{G_2} > 1$ **then**
22 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; replace $c'$ in $path^{G_2}$ with the first vertex of $c'$;
23 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **end**
24 &nbsp; **end**
25 &nbsp; initialize $path^{G_1} = s$;
26 &nbsp; **foreach** vertex, $v_i^{G_2} \in path^{G_2}$ **do**
27 &nbsp;&nbsp;&nbsp;&nbsp; $path^{G_1} = path^{G_1} \cup \text{prime path represented by } v_i^{G_2}$;
28 &nbsp; **end**
29 &nbsp; $path^{G_1} = path^{G_1} \cup t$;
30 &nbsp; **Output** $path^{G_1}$;
31 &nbsp; **end**
Note that the vertices $p_9$ and $p_3$ in the sub-path {$p_9, p_3$} of the third Test Path are not directly connected in $G_2$. Similarly, the vertices $p_7$ and $p_2$ are not directly connected. This aspect of connectedness is taken care in step 13.

As can be seen from the paths, redundancy exists. For example, the cycle {$p_9, p_8, p_9$} is present 3 times in the third path. We remove this redundancy by replacing such cycles with the first node of the cycle ($p_9$ in this case) for all occurrences except the first (step 18). Also note that for the cycle {$p_7, p_9, p_6, p_7$} the sub-path {$p_9, p_6$} is occurring more than once. This implies the cycle can be again reduced to the first node of the cycle (step 22). Thus, the set of paths after removing redundancy is {$s, p_4, t$}, {$s, p_3, p_5, p_7, p_9, p_8, p_9, p_6, p_7, p_3, p_1, t$}, {$s, p_0, p_9, p_2, t$}.

The last step of the algorithm is to merge the Prime Paths to obtain the $s-t$ paths on $G_1$. This operation is performed by the operator $\cup$ and is as explained in Section 3.2.

Thus, the minimum $s-t$ paths for the running example needed to cover all Prime Paths are {$s, 1, 2, t$}, {$s, 1, 3, 4, 1, 3, 4, 5, 4, 5, 4, 1, 3, 4, 1, 2, t$} and {$s, 1, 3, 4, 5, 4, 1, 2, t$}. Observe that the Test Paths are long in length. The length of the Test Paths are the number of edges and equals 27 in this example.

## 3.6 Other Coverage Criteria

Our method of identifying the minimum number of Test Paths is generic and can cater to all of the structural coverage criteria of [2] as shown below.

**Edge-Pair Coverage Criterion** For the Edge-Pair coverage criterion, the test requirement set, $TR$, is the set of all paths of length at-most 2. An edge-pair can be represented as a path {$v_i, v_j, v_k$}, where $(v_i, v_j) \& (v_j, v_k) \in E$. The minimum number of Test Paths such that $TR$ is covered can be obtained directly from our method. Algorithm 1 will have to be modified to generate the set of edge-pairs. Other algorithms can be used exactly as presented. Further, Lemma 1 and the Theorems hold. From Lemma 1, the lower bound on the minimum number of Test Paths would be $\max(|TypeS|, |TypeT|)$, where $TypeS$ and $TypeT$ are those test requirements that contain the vertex $s$ and $t$ respectively.

**Simple and Complete Round Trip Coverage Criterion** A Round Trip path is a Prime Path of Type C. The test requirement of the Simple Round Trip coverage criterion contains at least one Type C Prime Path which begins and ends for a given vertex. The test requirement for Complete Round Trip coverage criterion contains all Type C Prime Paths for a given vertex. Therefore, the Round Trip coverage criteria focuses on a subset of the set of Prime Paths for a given graph. In our formulation, algorithm 1 can be suitably modified to choose the set of Prime Paths needed for the set $TR$. The minimum number of Test Paths needed for this set of $TR$ is directly obtained by the other algorithms. However, in this case of Round Trip coverage, Lemma 1 will provide a value of 0 as the lower bound since there are no Type S or Type T test requirements.
**Edge Coverage Criterion** To handle Edge Coverage, there would be no need for algorithm 1 as the test requirements are directly available as *E*. The other algorithms can be used exactly as presented. Algorithm 2 represents every edge as a vertex in the flow network. Algorithm 3 reduces the graph to an acyclic one. The minimum flow computation using algorithms 4 and 5 with algorithm 6 will give the minimum number of Test Paths needed to cover every edge. Lemma 1 will equal the maximum of number of test requirements that contain *s* or *t* which in this case is the maximum of the out-degree of *s* and the in-degree of *t*.

**Node Coverage Criterion** Node Coverage can be handled by using a sub-set of the algorithms in our method. We directly use algorithms 3 to 6 to obtain the minimum number of Test Paths for node coverage. Lemma 1 will equal the maximum of the number of test requirements that contain *s* or *t* which in this case will equal 1.

# 4 Experimental Results

We have evaluated our method through two sets of tests. In the first test we use 18 graphs representing actual open-source software <fnref n="1" /> as test inputs. Since these graphs were also used as test inputs in [7], our results can be directly compared with that of [7]. Tables 2 & 3 provides the results of the first test.

The results show a significant reduction in the number of Test Paths generated over the methods of [2] and [7]. Averaging over the 18 graphs, the number of Test Paths were reduced by 72.9% over the solution of [2]. The reduction varied from a minimum of 16.3% to a maximum of 89.9%. Comparing with [7], the number of Test Paths from our solution reduced by 59.6% on average and varied from a minimum benefit of 0% to a maximum benefit of 91.4%.

Although our solution does not explicitly attempt to minimize the length of the Test Paths, the results show that in many cases, the Test Path length is reduced as well. The average reduction in the Test Path length on the 18 graphs was -9.4% over [2] (i.e. on average, the test path length increased) and 38.5% over [7]. Note that in some cases, the minimization of the number of Test Paths has actually increased the length of the Test Paths.

The identification of the lower bound (Lemma 1) has performed exceedingly well and on average over the 18 graphs, was only 8.2% outside the true value.

The execution time of our method is significant with Algorithm 2 being the most costly. On average, the execution time of our method was 338 times that of [2]. In absolute terms, the average execution time was 3.6 minutes, but varied from a minimum of 5 ms to a maximum of 27.6 minutes.

In the second test, we created 4391 random graphs of varying complexity as test inputs. The Prime Paths of these graphs varied from 7 to 150. The number of Test Paths, the length of Test Paths and the execution time were recorded averaging over graphs of a particular Prime Path. The execution times were the

<footnote n="1">¹ We thank Nan Li of [7] for sharing the manually created graphs.</footnote>
<table><caption>**Table 2.** Test Paths & Execution Time (in ms) over graphs representing actual software</caption><thead><tr><th>Num. of Prime Paths</th><th>9</th><th>11</th><th>27</th><th>27</th><th>35</th><th>38</th><th>46</th><th>63</th><th>69</th><th>78<sup>a</sup></th><th>93<sup>b</sup></th></tr></thead><tbody><tr><td>Num. of Test Paths from Solution in [2]</td><td>7</td><td>9</td><td>14</td><td>19</td><td>26</td><td>22</td><td>36</td><td>34</td><td>49</td><td>37</td><td>69</td></tr><tr><td>Test Paths' Length from Solution in [2]</td><td>46</td><td>56</td><td>200</td><td>181</td><td>230</td><td>210</td><td>426</td><td>506</td><td>544</td><td>675</td><td>771</td></tr><tr><td>Num. of Test Paths from our Solution</td><td>5</td><td>7</td><td>11</td><td>14</td><td>20</td><td>12</td><td>17</td><td>11</td><td>41</td><td>18</td><td>54</td></tr><tr><td>Lower Bound on Num. of Test Paths</td><td>5</td><td>7</td><td>11</td><td>14</td><td>20</td><td>12</td><td>8</td><td>11</td><td>35</td><td>18</td><td>54</td></tr><tr><td>Test Paths' Length from our Solution</td><td>33</td><td>42</td><td>159</td><td>133</td><td>223</td><td>154</td><td>294</td><td>385</td><td>527</td><td>764</td><td>1043</td></tr><tr><td>Execution Time of Solution in [2]</td><td>2</td><td>2</td><td>10</td><td>2</td><td>7</td><td>2</td><td>5</td><td>14</td><td>11</td><td>6</td><td>15</td></tr><tr><td>Execution Time of Algorithm 1</td><td>1</td><td>1</td><td>9</td><td>1</td><td>6</td><td>1</td><td>2</td><td>12</td><td>6</td><td>5</td><td>12</td></tr><tr><td>Execution Time of Algorithm 2</td><td>1</td><td>1</td><td>21</td><td>7</td><td>36</td><td>13</td><td>50</td><td>153</td><td>63</td><td>170</td><td>150</td></tr><tr><td>Execution Time of Algorithm 3</td><td>1</td><td>1</td><td>3</td><td>2</td><td>5</td><td>1</td><td>8</td><td>19</td><td>4</td><td>13</td><td>22</td></tr><tr><td>Execution Time of Algorithm 4 & 5</td><td>1</td><td>1</td><td>2</td><td>1</td><td>6</td><td>1</td><td>2</td><td>5</td><td>6</td><td>1</td><td>4</td></tr><tr><td>Execution Time of Algorithm 6</td><td>1</td><td>1</td><td>11</td><td>4</td><td>26</td><td>7</td><td>21</td><td>48</td><td>23</td><td>38</td><td>40</td></tr><tr><td>Total Execution Time of our Solution</td><td>5</td><td>5</td><td>46</td><td>15</td><td>79</td><td>23</td><td>83</td><td>237</td><td>102</td><td>227</td><td>228</td></tr></tbody></table>

average of 5 runs over the same graph. The results are shown in Fig. 6. Similar to the first test, we see a significant improvement in terms of number of Test Paths. On average, our method reduced the number of Test Paths by 70.9%. The length of Test Paths were reduced by 2.7% on average. The lower bound was away from the true value by only 0.6% on average. On average, our method took 0.39 seconds to execute which was 105 times the execution time of [2].

Overall, our method of minimizing the number of Test Paths provides good results. To mitigate the concern of the increase in execution time, the quality of the lower bound can be exploited (for example attempting the minimization only when the solution from [2] is over 5 times the lower bound).

<table><caption>**Table 3.** Test Paths & Execution Time (in ms) over graphs representing actual software</caption><thead><tr><th>Num. of Prime Paths</th><th>98</th><th>101</th><th>122</th><th>170</th><th>1074<sup>a</sup></th><th>1141</th><th>1844</th></tr></thead><tbody><tr><td>Num. of Test Paths from method in [2]</td><td>67</td><td>60</td><td>80</td><td>102</td><td>933</td><td>954</td><td>885</td></tr><tr><td>Test Paths' length from method in [2]</td><td>1096</td><td>872</td><td>1577</td><td>1986</td><td>27457</td><td>37245</td><td>19828</td></tr><tr><td>Num. of Test Paths from our Method</td><td>41</td><td>47</td><td>20</td><td>42</td><td>362</td><td>96</td><td>102</td></tr><tr><td>Lower Bound on Num. of Test Paths</td><td>31</td><td>47</td><td>20</td><td>28</td><td>362</td><td>65</td><td>102</td></tr><tr><td>Test Paths' Length from our Method</td><td>967</td><td>1152</td><td>1541</td><td>1789</td><td>34733</td><td>37358</td><td>21482</td></tr><tr><td>Execution Time of Solution in [2]</td><td>11</td><td>11</td><td>14</td><td>48</td><td>3548</td><td>5884</td><td>1997</td></tr><tr><td>Execution Time of Algorithm 1</td><td>9</td><td>9</td><td>11</td><td>26</td><td>2376</td><td>4454</td><td>748</td></tr><tr><td>Execution Time of Algorithm 2</td><td>306</td><td>253</td><td>1057</td><td>1386</td><td>634719</td><td>1240553</td><td>1315738</td></tr><tr><td>Execution Time of Algorithm 3</td><td>42</td><td>13</td><td>79</td><td>222</td><td>72520</td><td>167950</td><td>95775</td></tr><tr><td>Execution Time of Algorithm 4 & 5</td><td>6</td><td>4</td><td>1</td><td>12</td><td>137</td><td>19</td><td>87</td></tr><tr><td>Execution Time of Algorithm 6</td><td>58</td><td>71</td><td>230</td><td>179</td><td>42628</td><td>106613</td><td>242745</td></tr><tr><td>Total Execution Time for our Method</td><td>421</td><td>350</td><td>1378</td><td>1825</td><td>752380</td><td>1519589</td><td>1655093</td></tr></tbody></table>

<footnote>a maps to 71 in results (Table II) of [7] as our solution uses a single source and sink.</footnote>

<footnote>b similarly maps to 84 in results (Table II) of [7].</footnote>

<footnote>a similarly maps to 1024 in results (Table II) of [7].</footnote>
<figure><img src="image_6.png" /><figcaption>Fig. 6. Test Paths & Execution Time (in ms) over randomly created graphs</figcaption></figure>

## 5 Conclusion

In this paper, we present a method to achieve the minimum number of Test Paths for Prime Path and other structural coverage criteria. The Prime Path criterion improves the quality of the Test Cases. However, even a small graph can have many Prime Paths and having a less number of Test Paths directly results in time saving over the Test Case execution. Our solution obtains an optimal solution with a time complexity of $O(|V||E|)$. This matches the best known time complexity till date. We have also presented a lower bound for the minimum number of Test Paths. Experimental results on graphs representing actual software and random graphs shows the superior performance of our method in terms of the number of Test Paths and the quality of the lower bound.

## References

1. Aho, A.V., Lee, D.: Efficient algorithms for constructing testing sets, covering paths, and minimum flows. AT&T Bell Laboratories Tech. Memo. CSTR159 (1987)

2. Ammann, P., Offutt, J.: Introduction to software testing. Cambridge University Press (2008)

3. Ammann, P., Offutt, J., W., X., Li, N.: Coverage computation web applications. http://cs.gmu.edu:8080/offutt/coverage/ (2008), [Online; accessed 26-April-2014]

4. Ciurea, E., Ciupalâ, L.: Sequential and parallel algorithms for minimum flows. Journal of Applied Mathematics and Computing 15(1-2), 53–75 (2004)

5. Ford, L., Fulkerson, D.R.: Flows in networks. Princeton University Press (1962)

6. Kaminski, G.K., Praphamontripong, U., Ammann, P., Offutt, J.: An evaluation of the minimal-mumcut logic criterion and prime path coverage. In: Software Engineering Research and Practice. pp. 205–211 (2010)

7. Li, N., Li, F., Offutt, J.: Better algorithms to minimize the cost of test paths. In: Software Testing, Verification and Validation (ICST), 2012 IEEE Fifth International Conference on. pp. 280–289. IEEE (2012)

8. Ntafos, S.C., Hakimi, S.L.: On path cover problems in digraphs and applications to program testing. Software Engineering, IEEE Transactions on (5), 520–529 (1979)