What are common examiner traps in Cyclomatic Complexity?

Adding cyclomatic complexities directly during sequential composition (V(X) + V(Y) instead of V(X) + V(Y) - 1). Forgetting the external/unbounded region when using the region-counting method V(G) = R. Treating compound logical conditions (e.g., `(A && B)`) incorrectly without decomposing them into atomic predicate nodes when analyzing detailed flow graphs. Off-by-one errors in node vs edge counting on directed cyclic graphs (loops).

Cyclomatic Complexity

1 Qs · 2015 · 2 marks · 0.3 marks/paperStandard yield

Take topic test

In GATE CS, Control Flow and Cyclomatic Complexity questions evaluate the student's ability to compute McCabe's Cyclomatic Complexity across multiple representations (C code snippe… Guide

Type

GATE CSE 2015 Set 3Q55MCQ2 marksMediumDiagramConsider three software items: Program- $X$ , Control Flow Diagram of Program- $Y$ and Control Flow Diagram of Program- $Z$ as shown below The values of McCabe's Cyclomatic complexity of Program- $X$ , Program- $Y$ , and Program- $Z$ respectively are

Topic guide

What does GATE test in Cyclomatic Complexity?

In GATE CS, Control Flow and Cyclomatic Complexity questions evaluate the student's ability to compute McCabe's Cyclomatic Complexity across multiple representations (C code snippets, explicit Control Flow Graphs, and composite/sequential modules). The core focus is on applying graph-theoretic and predicate-based definitions of cyclomatic complexity to measure code complexity.

Core concepts

McCabe's Cyclomatic Complexity metric
Control Flow Graph (CFG) construction (Nodes, Edges, Decision/Predicate nodes)
Planar regions in Control Flow Graphs
Sequential composition of Control Flow Diagrams (SESE structures)
Mapping conditional statements (if-else, while loops, compound conditions) to CFG nodes and edges

Recurring question patterns

Multi-Representation Cyclomatic Complexity Calculation
rare · MCQ · 2 marks · 2015
Given a mix of code snippets, a control flow graph diagram, and a composite module connected sequentially, determine the respective cyclomatic complexities.

Formulas GATE uses

McCabe's Cyclomatic Complexity (Graph formula)

V(G) = E - N + 2P

Used when the number of edges $E$ , nodes $N$ , and connected components $P$ (usually $P=1$ for a single program) of a Control Flow Graph are known.

McCabe's Cyclomatic Complexity (Predicate formula)

V(G) = P + 1

Used directly on source code where $P$ is the count of simple predicate/decision nodes (e.g., if, while, for).

McCabe's Cyclomatic Complexity (Planar Region formula)

V(G) = R

Used when counting bounded enclosed regions plus one unbounded (external) region in a planar control flow graph.

Sequential Composition of Single-Entry Single-Exit (SESE) Modules

V(Z) = V(X) + V(Y) - 1

Used when two independent modules $X$ and $Y$ are concatenated sequentially with a single transition edge from exit of $X$ to entry of $Y$ .

Examiner traps in Cyclomatic Complexity

Adding cyclomatic complexities directly during sequential composition (V(X) + V(Y) instead of V(X) + V(Y) - 1).
Forgetting the external/unbounded region when using the region-counting method V(G) = R.
Treating compound logical conditions (e.g., `(A && B)`) incorrectly without decomposing them into atomic predicate nodes when analyzing detailed flow graphs.
Off-by-one errors in node vs edge counting on directed cyclic graphs (loops).

How questions are asked

Multi-part matching or tuple-selection of cyclomatic complexity for given code snippets and CFG diagrams
NAT calculating cyclomatic complexity for a given function or graph structure

Paper trends

Appears as a 2-mark comprehensive question testing cyclomatic complexity across code, graph representation, and serial composition of modules.
2015

Difficulty notes

Medium difficulty arises from combining multiple steps: deriving $V(G)$ from textual source code, reading a visual graph diagram to count $E$ and $N$ , and applying composition rules for connected modules without making arithmetic or boundary errors.