Which one of the following is used to compute cyclomatic complexity ?
2014
Which one of the following is used to compute cyclomatic complexity ?
- A.
The number of regions – 1
- B.
E – N + 1, where E is the number of flow graph edges and N is the number of flow graph nodes.
- C.
P – 1, where P is the number of predicate nodes in the flow graph G.
- D.
P + 1, where P is the number of predicate nodes in the flow graph G.
Attempted by 92 students.
Show answer & explanation
Correct answer: D
Answer: Cyclomatic complexity V(G) = P + 1, where P is the number of predicate (decision) nodes in the flow graph.
Equivalent formulas for a connected flow graph:
V(G) = E - N + 2, where E is the number of edges and N is the number of nodes.
V(G) = number of regions (faces) in the planar drawing of the flow graph.
Brief justification:
Using Euler's formula for a connected planar graph, regions = E - N + 2. Cyclomatic complexity equals the number of independent paths, which matches the number of regions.
Counting predicate (decision) nodes: with zero predicates there is one path; each predicate adds one independent path, giving V(G) = P + 1.
Therefore, the option stating P + 1 is the correct and commonly used way to compute cyclomatic complexity.