Cyclomatic Complexity is a software metric developed by Thomas J. McCabe, Sr. in 1976. To understand Cyclomatic complexity let’s first understand what is Software Metric.
What is Software Metric?
Software metric is defined as a quantitative measure of an attribute a software system possesses with respect to Cost, Quality, Size and Schedule.
Measure- No of errors
Metric-No of errors per person
Software metrics are classified into 2 types.
- Linguistic Metrics
- Structural Metrics
It is based on measuring properties of program text without interpreting what the text means. That means when you have a program you just go through the program without interpreting it.
E.g.:- Lines of Code
It is based on structural relations between the objects in a program.
That means when you have a program you basically understand the logic of the program which is being written and then calculate or determine the value of the attribute.
e.g.:- Number of nodes and links in a control flow graph
What is Cyclomatic Complexity?
Cyclomatic Complexity is an example for structural metrics. That means you need to understand the logic of the program in order to calculate the Cyclomatic Complexity of the program.
Cyclomatic Complexity is a source code complexity measurement that is being correlated to a number of coding errors.
This metric measures independent paths through program source code.
Independent path is defined as a path that has at least one edge which has not been traversed before in any other paths.
Cyclomatic complexity can be calculated with respect to functions, modules, methods or classes within a program. Thomas J. McCabe developed this software metric based on a control flow representation of the program. Control flow depicts a program as a graph which consists of Nodes and Edges.
In the graph, nodes represent processing tasks while edges represent control flow between the nodes.
Cyclomatic Complexity is language independent. I.e. whether you write your program in C or java, you have to identify the flow of your program and then represent the program in terms of a flow graph.
Cyclomatic Complexity can be calculated manually.
Now let’s see the steps required in order to compute the Cyclomatic Complexity and test cases design.
- 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.
Flow diagrams for statements like if-else, While, until and normal sequencof flow are shown below.
Mathematical Representation of Cyclomatic Complexity
Mathematically, it is set of independent paths through the graph diagram. There are two formulas for calculating Cyclomatic Complexity.
1. V(G) = E – N + 2
E=Number of Edges
N=Number of Nodes
2. V(G) = D+1
D=Number of decision nodes or predicate nodes
Let’s see a simple example.
- You can combine one or more lines which has same flow to form a single node.
E.g. Line No 1 and 2 are combined and represent as node 1
- Each condition has to be represented as a separate node.
E.g. Node 2, 3 & 4 in the above example.
Flow graph for the above example is as follow;
Computing Cyclomatic Complexity V (G)
1. V(G) = E – N + 2
No. of Edges E=9
No. of Nodes N=7
V (G) = 9-7+2
2. V(G) = D+1
No. of Decision boxes D=3
V (G) = D+1
Interpretation of Cyclomatic Complexity
|Complexity No.||Corresponding Meaning of V (G)|
|1-10||Structured and well written code
Cost and Effort to maintain is less
Cost and Effort to maintain is Medium
|20-40||Very Complex Code
Cost and Effort to maintain is high
|>40||Not at all testable
Very high risk
Very high Cost and Effort to maintain
According to the above example, the Cyclomatic Complexity value is 4. So we can say that;
- The program is structured and well written
- Have high Testability
- Low risk
- Cost and Effort to maintain is less