Control Flow Graph
Below is a bubble sort program that sorts the elements in an array.
static void bubbleSort(int[] arr) {
int n = arr.length;
int temp = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j < (n - i); j++) {
if (arr[j - 1] > arr[j]) {
temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
}
1. Based on the program above, please draw a control flow graph for it. Hint: Annotating some statements or conditions on nodes/edges will be very helpful.
2. In your control flow graph, what are the test requirements for edge coverage?
3. List test path(s) that achieves the edge coverage.
4. Provide test cases for each test path you list in the previous question. If it is not possible to find the test input for certain test path, describe the reason.
Hint: Not providing expected outputs will get 2 points deduction. Not matching test paths with their corresponding input/output will get 3 points deduction.
5. In your control flow graph, what are the test requirements for edge-pair coverage?
6. List test paths that achieve the edge-pair coverage.
7. Provide test cases for each test path you list in the previous question. If it is not possible to find the test input for certain test path, describe the reason.
Control Flow Graph:
┌─► (int i = 0)
│
│ ┌─► (int j = 1)
│ │
│ │ ┌─► (arr[j - 1] > arr[j])
│ │ │
◄───┼───┤
│ │ ┌─► temp = arr[j - 1]
│ │ │
└───┼───┼───► arr[j - 1] = arr[j]
│ │
└───┼───► arr[j] = temp
│
◄──► (j < (n - i))
│
◄──► (i < n)
Test Requirements for Edge Coverage:
Every edge in the control flow graph should be covered at least once.
Test Path(s) for Edge Coverage:
Path 1: (i = 0, j = 1, arr[j - 1] > arr[j], temp = arr[j - 1], arr[j - 1] = arr[j], arr[j] = temp, j < (n - i), i < n)
Test Cases for Edge Coverage:
Test Case 1: arr = [4, 2, 1, 3]
Test Case 2: arr = [5, 1, 3, 2, 4]
Test Requirements for Edge-Pair Coverage:
Every pair of edges that share a common node should be covered at least once.
Test Paths for Edge-Pair Coverage:
Path 1: (i = 0, j = 1, arr[j - 1] > arr[j], temp = arr[j - 1], arr[j - 1] = arr[j], arr[j] = temp, j < (n - i), i < n)
Path 2: (i = 0, j = 1, arr[j - 1] <= arr[j], j < (n - i), i < n)
Path 3: (i = 0, j < (n - i), i < n)
Path 4: (i = 0, j >= (n - i), i < n)
Path 5: (i >= n)
Test Cases for Edge-Pair Coverage:
Test Case 1: arr = [4, 2, 1, 3]
Test Case 2: arr = [5, 1, 3, 2, 4]
Test Case 3: arr = [2, 4, 6]
Test Case 4: arr = [1]
Test Case 5: arr = [] (empty array)
Note: It is not possible to find a test input that covers the path where i >= n because it would mean that the outer loop has already terminated and the function has completed its execution.