Software Engineering - McCabe's Cyclomatic metric

McCabe's Cyclomatic metric, V(G) of a graph "G" with "n" vertices and "e" edges is given by the following formula

V(G) = e – n + 2

Let us take an example of a program; wherein we associate it with a directed graph that has unique entry and exit nodes. Each node in the graph, G, corresponds to a block of statements in the program where flow is sequential and the arcs correspond to branches taken in the program. This graph is known as a "Flow Graph".

The Cyclomatic Complexity, V(G) provides us two things

1) To find the number of independent paths through the program.

2) To provide an upper bound for the number of test cases that must be executed in order to test the program thoroughly. The complexity measure is defined in terms of independent paths. It is defined as any path through the program that introduces at least one new set of processing statements or a new condition.

The following steps are usually followed

Step – 1: Construction of flow graph from the source code or flow charts.

Step – 2: Identification of independent paths.

Step – 3: Computation of Cyclomatic Complexity.

Step – 4: Test cases are designed.

Using the flow graph, an independent path can be defined as a path in the flow graph that has at least one edge that has not been traversed before in other paths. A set of independent paths that cover all the edges is a basic set. Once the basis set is formed, test cases should be written to execute all the paths in the basis set.

Properties of Cyclomatic Complexity

The following are the properties of Cyclomatic Complexity represented as V(G)

1) V(G) >= 1.

2) V(G) is the maximum number of independent paths in graph, G.

3) Inserting and deleting functional statements to G does not affect V(G).

4) G has only one path if and only if V(G) = 1.

5) Inserting a new row in G, increases V(G) by unity.

Let us see the meaning of V(G)
For small programs Cyclomatic Complexity can be calculated manually, but automated tools are essential as several thousands of lines of code are possible in each program in a project. It will be very difficult to manually create flow graphs for large programs.

There are several tools that are available in the market, which can compute Cyclomatic Complexity. Note that calculating the complexity of a module after it has been built and tested may be too late. It may not be possible to redesign a complex module after it has been tested. Thus, some basic complexity checks must be performed on the modules before embarking upon the testing (or even coding) phase. Based on the complexity number that emerges from using the tool, one can conclude what actions need to be taken for complexity measure using the table given below

Complexity No.	Corresponding Meaning of V(G)
1-10	1) Well-written code, 2) Testability is high, 3) Cost / effort to maintain is low
10-20	1) Moderately complex code, 2) Testability is medium, 3) Cost / effort to maintain is medium.
20-40	1) Very complex code, 2) Testability is low, 3) Cost / effort to maintain is high.
> 40	1) Not testable, 2) Any amount of money / effort to maintain may not be enough