Coursify

SOFTWARE ENGINEERING

Cyclomatic Complexity and Control Flow Graphs

This section examines complexity measurement through control flow graphs and cyclomatic complexity, with emphasis on understanding program structure, testability, and risk.

Learning Goals

  • Construct a control flow graph for a given program segment by identifying nodes, edges, and decision points.
  • Calculate cyclomatic complexity from a control flow graph using standard formulas and verify the result across methods.
  • Interpret cyclomatic complexity values to assess code understandability, test effort, and structural risk.
  • Identify independent execution paths in a program based on its cyclomatic complexity.
  • Recommend refactoring actions to reduce excessive control complexity and improve testability.

Understanding program structure, testability, and software risk is essential for building reliable code. Code complexity is a leading indicator of bugs, maintenance overhead, and test effort. To measure and control this complexity, software engineers use two major structural tools: the Control Flow Graph (CFG) and Cyclomatic Complexity .

A control flow graph represents the logical paths of execution in a program. It consists of:

  • Nodes (Vertices): Represent a Basic Block—a sequence of instructions that executes sequentially without branches.
  • Edges: Directed arrows representing the transfer of control from one basic block to another.
  • Decision Points / Predicate Nodes: A Predicate Node is a block that contains a conditional statement (e.g., if, while, for), splitting the control flow into multiple alternative edges.

Consider the following program segment which calculates a ticket fee based on age and student status:

1function calculateFee(age, isStudent) {
2    let fee = 10;
3    if (age < 18) {
4        fee = 5;
5    } else if (isStudent) {
6        fee = 7;
7    }
8    return fee;
9}

Below is the corresponding Control Flow Graph representing this logical flow. Each block has been isolated into nodes, demonstrating how branch conditions split the execution:

Footnotes

  1. McCabe, T. J. (1976). A Complexity Measure. IEEE Transactions on Software Engineering, SE-2(4), 308-320. - The seminal research paper defining control flow complexity and introducing cyclomatic metrics. ↩

Cyclomatic Complexity Explained

Quick Formula Verification

When analyzing standard procedural functions, the easiest way to double-check your cyclomatic complexity calculation is the predicate formula: M=π+1M = \pi + 1. Simply count the decision statements (if, while, for, case) and add 11. Make sure to split compound operators like && or || since they represent additional predicate nodes!

Computing Cyclomatic Complexity (MM)

Developed by Thomas McCabe in 1976, Cyclomatic Complexity provides a quantitative measure of the logical complexity of a program . This value defines the size of the set of Independent Paths (called the basis set) that must be tested to guarantee full structural coverage .

There are three equivalent mathematical methods used to calculate McCabe's Cyclomatic Complexity (MM) for a single program subroutine:

  1. Edge-Node Formula: M=E−V+2PM = E - V + 2P Where:

    • EE is the number of edges in the control flow graph.
    • VV is the number of nodes (vertices).
    • PP is the number of connected components. For a single, isolated method or function, P=1P = 1, reducing the formula to: M=E−V+2M = E - V + 2

  2. Predicate Node Formula: M=pi+1M = \\pi + 1 Where:

    • pi\\pi is the number of predicate nodes (decision points with two outcomes, like standard conditional checks).

  3. Planar Regions Formula: M=RM = R Where:

    • RR is the number of closed, bounded regions in a planar representation of the graph, plus 11 for the infinite open space surrounding the graph.

By applying these three methods, developers can verify their complexity calculations across different representations to guarantee accuracy.

Footnotes

  1. McCabe, T. J. (1976). A Complexity Measure. IEEE Transactions on Software Engineering, SE-2(4), 308-320. - The seminal research paper defining control flow complexity and introducing cyclomatic metrics. ↩

  2. Cal Poly Computer Science Department. (1997). Basis Path Testing and Complexity Analysis. Cal Poly Educational Material. - Standard tutorial detailing the mechanics of basis path derivation and white-box test coverage. ↩

Walkthrough: Analyzing Code to Construct a CFG and Calculate Complexity

  1. 1
    Step 1

    Analyze the target code and identify 'leaders'—the entry statements, targets of branches, or statements immediately following branch statements. Group sequential code between leaders into single Basic Blocks. For our fee calculation code, we get: Node 1 (Entry & Initialization), Node 2 (First conditional age < 18), Node 3 (Branch A fee = 5), Node 4 (Second conditional isStudent), Node 5 (Branch B fee = 7), Node 6 (Junction / Merge point), and Node 7 (Exit / Return).

  2. 2
    Step 2

    Represent each basic block as a circle or node. Connect the nodes with directed arrows (edges) representing valid execution pathways. Draw edges for conditional checks: Node 2 splits to Node 3 (True) and Node 4 (False). Node 4 splits to Node 5 (True) and Node 6 (False). Merge all branch exits (Node 3, Node 5, Node 4's False path) into the junction Node 6, which leads directly to Exit Node 7.

  3. 3
    Step 3

    Examine your completed Control Flow Graph to count the elements. In our example: Vertices (VV) = 7, and Edges (EE) = 8. (Edges are: 1->2, 2->3, 2->4, 3->6, 4->5, 4->6, 5->6, 6->7).

  4. 4
    Step 4

    Calculate the complexity using the three methods to verify: (1) M=E−V+2  ⟹  M=8−7+2=3M = E - V + 2 \implies M = 8 - 7 + 2 = 3. (2) Count the predicate nodes: Node 2 (age < 18) and Node 4 (isStudent) are the only decision points, so π=2\pi = 2. Applying M=π+1  ⟹  M=2+1=3M = \pi + 1 \implies M = 2 + 1 = 3. (3) Look at the planar graph: Region 1 is bounded by 2-3-6-4-2. Region 2 is bounded by 4-5-6-4. Region 3 is the outer infinite region. M=R  ⟹  M=3M = R \implies M = 3. All three methods match!

  5. 5
    Step 5

    Use the computed complexity M=3M = 3 to extract the exact basis set of independent execution paths. These paths will form the target for Basis Path Testing: Path 1 (Underage): 1->2->3->6->7 (Inputs: age=15, isStudent=false); Path 2 (Adult, Student): 1->2->4->5->6->7 (Inputs: age=20, isStudent=true); Path 3 (Adult, Non-student): 1->2->4->6->7 (Inputs: age=20, isStudent=false). Testing these three scenarios ensures 100% statement and branch coverage.

1function getAlertPriority(status) {
2  let priority;
3  if (status === "CRITICAL") {
4    priority = "HIGH";
5  } else if (status === "WARNING") {
6    priority = "MEDIUM";
7  } else if (status === "INFO") {
8    priority = "LOW";
9  } else if (status === "DEBUG") {
10    priority = "NONE";
11  } else {
12    priority = "UNKNOWN";
13  }
14  return priority;
15}

The Trap of Deceptive Refactoring

Splitting a high-complexity method into multiple smaller sub-methods reduces the complexity per method, but the overall structural complexity of the system remains. Use Refactoring techniques wisely: instead of just cutting-and-pasting code, aim to eliminate branch points entirely using architectural patterns .

Footnotes

  1. Fowler, M. (2018). Refactoring: Improving the Design of Existing Code (2nd ed.). Addison-Wesley Professional. - Comprehensive reference on refactoring patterns, including guard clauses and map dispatch methods. ↩

McCabe Complexity Risk & Testing Correlation

How cyclomatic complexity thresholds affect maintenance risk and recommended testing effort

Deep Dive & Advanced Concepts

Knowledge Check

Question 1 of 4
Q1Single choice

A Control Flow Graph has 12 edges, 9 nodes, and represents a single program method (P=1P = 1). What is its cyclomatic complexity using McCabe's standard formula?

References

Previous

Next