CYCLOMATIC COMPLEXITY - SOLVED PROBLEMS

Cyclomatic complexity is a software metric. It provides a quantitative measure of the logical complexity of a program.Cyclomatic complexity provides us with an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at least once.

Cyclomatic complexity has a foundation in graph theory and is computed in one of three ways.
1. The number of regions correspond to the cyclomatic complexity.
2. Cyclomatic complexity V(G) for a flow graph G, is defined as,
V(G)=E-N+2
where E=Number of flow graph edges
N=Number of flow graph nodes
3.Cyclomatic complexity,V(G) for a flow graph G, is defined as,
V(G)=P+1
where P=Number of predicate nodes contained in flow graph G.

The above three formulas are very important and there are a lot of NET questions based on this topic. I am solving a few of them here.
DECEMBER 2013 - PAPER III Q.NO 4
4. Given a flow graph with 10 nodes, 13 edges and one connected components, the number of regions and the number of predicate(decision) nodes in the flow graph will be
A)4,5
B)5,4
C)3,1
D)13,8
Ans:-B
Explanation:-
N=10,E=13
V(G)=E-N+2
V(G)=13-10+2
=3+2=5
Therefore, No of regions = 5. (According to rule 1.)
According to rule 3, V(G)=P+1
V(G) refers to the cyclomatic complexity which is equal to the no of regions.
5=P+1
P=5-1=4
So, the number of predicate nodes in the flow graph is 4.
So, the number of regions and the number of predicate nodes in the flow graph will be 5,4
Therefore, the correct answer is B.

JUNE 2013 - PAPER II Q.No 5
5. Cyclomatic complexity of a flow graph G with n vertices and e edges is
A)V(G)=e+n-2
B)V(G)=e-n+2
C)V(G)=e+n+2
D)V(G)=e-n-2
Ans:-B
Explanation:-
According to rule 2, the formula for Cyclomatic Complexity V(G)=e-n+2 where e is no of edges, n is no of vertices.

JUNE 2012 - PAPER III Q.No 33
33. Which one of the following statements is incorrect ?
(A) The number of regions corresponds to the cyclomatic complexity.
(B) Cyclometric complexity for a flow graph G is V(G) = N – E + 2, where E is the number of edges and N is the number of nodes in the flow graph.
(C) Cyclometric complexity for a flow graph G is V(G) = E – N + 2, where E is the number of edges & N is the number of nodes in the flow graph.
(D) Cyclometric complexity for a flow graph G is V(G) = P + 1, where P is the number of predicate nodes contained in the flow graph G.
Ans:- B
Explanation:-
According to the formulas given in (1),(2) and (3), option B is incorrect, because V(G)=E-N+2 and not N-E+2.

DECEMBER 2011 - PAPER II Q.No 15
15. McCabe's cyclomatic metric V(G) of a graph with n vertices, e edges and p connected component is
A)e
B)n
C)e-n+p
D)e-n+2p
Ans:-C
Explanation:-
According to McCabe's cyclomatic metric of a graph V(G)=E-N+P where P refers to connected components.

JUNE 2006 - PAPER II Q.No 42
42. In Software Metrics, McCABE􏰂's cyclomatic number is given by following formula :
(A) c=e-n+2p
(B) c=e-n-2p
(C) c=e+n+2p
(D) c=e-n*2p
Ans:-A

I hope all of you can solve problems based on cyclomatic complexity of a graph, with confidence and ease, after going through the above article.

REFER TO MY OTHER POSTS ON SOFTWARE ENGINEERING

SOFTWARE ENGINEERING

SOFTWARE ENGINEERING - SOLVED PROBLEMS