Cyclomatic Number - Software Testing

The cyclomatic number of a graph G is given by V(G) = e – n + p

7/1/2009Print This PageTell - A - FriendAdd to Wish ListReport Error

Another property of graphs has deep implications for testing: cyclomatic complexity.

Definition:

The cyclomatic number of a graph G is given by V(G) = e – n + p. where

e is the number of edges in G
n is the number of nodes in G
p is the number of components in G

V(G) is the number of distinct regions in a graph. Recall our discussion of vector spaces and the notion of a basis set. One formulation of structural testing postulates the notion of basis paths in a program and shows that the cyclomatic number of the program is the number of these basis elements.

The cyclomatic number of our example graph is V(G) = 5 – 7 + 2 = 0. When we use cyclomatic complexity in testing. We will (usually) have strongly connected graphs, which will generate graphs with large cyclomatic complexity.

7/1/2009Print This PageTell - A - FriendAdd to Wish ListReport Error

Related Words:

Graph Theory, Linear Graph, Degree of a Node, Incidence Matrices, Adjacency Matrices, Paths, Connectedness, Condensation Graph, Cyclomatic Number, Directed Graph, Software Testing Notes, Online Software Testing Papers, Graph Theory Testing Papers, Software Testing Classnotes