Provide an example of cyclomatic complexity and how it is related to structural testing .

What is Cyclomatic Complexity?

Cyclomatic Complexity (CC) is a metric used to measure the complexity of a program’s control flow. It provides a quantitative assessment of the number of linearly independent paths through the program. Developed by Thomas J. McCabe, this metric is crucial in structural testing as it helps identify the minimum number of test cases required for comprehensive path coverage.

Formula for Cyclomatic Complexity

Cyclomatic Complexity is calculated using the following formula:
[ V(G) = E – N + 2P ]

Where:

• E = Number of edges in the control flow graph (CFG).
• N = Number of nodes in the CFG.
• P = Number of connected components or exit points (usually 1 for a single program).

Alternatively, for a single connected component:
[ V(G) = \text{Number of decision points} + 1 ]

Example of Cyclomatic Complexity

Consider the following code snippet:

def calculate_grade(score):
    if score >= 90:
        return "A"
    elif score >= 80:
        return "B"
    elif score >= 70:
        return "C"
    else:
        return "F"

Step 1: Construct the Control Flow Graph (CFG)

• Each block of code is represented as a node.
• Each decision or condition introduces edges for possible control flow paths.

CFG Nodes and Edges:

1. Node 1: Entry point.
2. Node 2: if score >= 90 (decision point).
3. Node 3: return "A".
4. Node 4: elif score >= 80 (decision point).
5. Node 5: return "B".
6. Node 6: elif score >= 70 (decision point).
7. Node 7: return "C".
8. Node 8: else block leading to return "F".
9. Node 9: Exit point.

Step 2: Compute Cyclomatic Complexity

1. Count Nodes (N): 9.
2. Count Edges (E): 10.
3. Connected Components (P): 1.

Using the formula:
[ V(G) = E – N + 2P ]
[ V(G) = 10 – 9 + 2(1) = 3 ]

Cyclomatic Complexity = 3.

Explanation:

This means there are 3 independent paths in the program, and at least 3 test cases are needed to achieve 100% path coverage.

Cyclomatic Complexity and Structural Testing

Structural Testing, also known as White-box Testing, focuses on the internal structure of the code. Cyclomatic Complexity is directly related to structural testing in the following ways:

1. Determining Test Cases:
   Cyclomatic Complexity provides the minimum number of test cases required for branch coverage or path coverage. In the example above, at least 3 test cases are needed to cover all paths.
2. Evaluating Code Quality:
   Higher cyclomatic complexity indicates higher code complexity, which may be harder to test, maintain, or debug. Ideal CC values range between 1 and 10.
3. Improving Test Coverage:
   By identifying all independent paths, testers can design test cases to achieve better coverage of decision points and control flow paths.

Example Test Cases for the Code Above

1. Path 1: Input score = 95 → Tests if score >= 90.
2. Path 2: Input score = 85 → Tests elif score >= 80.
3. Path 3: Input score = 60 → Tests else block.

These cases ensure all decision points and control paths are tested.

Benefits of Cyclomatic Complexity in Structural Testing

1. Ensures Comprehensive Testing:
   By focusing on independent paths, CC helps testers achieve thorough test coverage.
2. Detects Logical Errors:
   Identifying paths ensures all logical branches are tested, reducing the likelihood of errors in decision-making code.
3. Improves Maintainability:
   Understanding CC helps developers refactor overly complex code into simpler, more testable structures.

Conclusion

Cyclomatic Complexity is a valuable metric for measuring control flow complexity and guiding structural testing. By using CC, testers can systematically design test cases, ensure complete path coverage, and improve the reliability and maintainability of software systems.