According to the SEI, “Cyclomatic complexity is the most widely used member of a class of static software metrics. Cyclomatic complexity may be considered a broad measure of soundness and confidence for a program. Introduced by Thomas McCabe in 1976, it measures the number of linearly-independent paths through a program module.”
Technically, cyclomatic complexity is calculated by the number of edges, less the number of nodes plus the number of connected components of a control flow graph of the program being measured. (Aren’t you glad you asked!)
Ok, that’s fine, but how does that relate to testing?
Interestingly, the complexity measure of a method is also the exact number of tests that is needed to achieve 100% path coverage through an application. The measure of complexity also is a great indicator of the testability, or “de-testability” of a particular method. The SEI present the following table as a basis for common complexity threshold values.
| Cyclomatic Complexity | Risk |
| 1-10 | A simple, low risk program |
| 11-20 | moderate complexity, risk complexity |
| 21-50 | Complex, high risk |
| Greater than 50 | high risk, detestable program |
Structured basis testing is a testing approach based on cyclomatic complexity. Simplistically, to build tests based on complexity, you should start at the first line of a method, and count the straight through path as 1, that is your first test. Then, manually calculate the complexity for the method and as you go, add a corresponding test each time you add to the complexity count.
An example
In The art of software testing, Glenford Myers uses a simple self assessment test, for the reader to work out how many test cases you need for a simple program. The program in his example accepts three integers, one for each side of a triangle, and determines whether the triange is scalene, isosceles or equilateral.
string CheckTriangle (int SideA, int SideB, int SideC)
In case you were wondering, A scalene triangle is one where no two sides are equal, an equilateral triangle is one where all the sides are equal and an isosceles triangle has two equal sides.
My implementation of the CheckTriangle method, results in a simple, yet quite complex piece of code, which has a cyclomatic complexity of 12.
1 public static string CheckTriangle (int a, int b, int c)
2 {
3 if (a <= 0 || b <= 0 || c <= 0)
4 {
5 return "Illegal Triangle";
6 }
7
8 if ((a > b + c || b > a + c || c > a + b))
9 {
10 return "Illegal Triangle";
11 }
12
13 if (a == b && b == c)
14 {
15 return "Equilateral Triangle";
16 }
17
18 if (a == b || b == c || a == c)
19 {
20 return "Isosceles Triangle";
21 }
22
23 return "Scalene Triangle";
24 }So how did I calculate the complexity?
There are several free tools on the market for .net developers to calculate the cyclomatic complexity of a given piece of code, including Sourcemonitor, Reflector with the Codemetrics add-in developed by Jonathan De Halleux, and CodeRush with the metrics add-in.
Manually calculating the complexity, and writing tests as we go.
You can also calculate complexity manually quite easily, for example:
| Code | Complexity |
| Straight through path | 1 |
| if (a <= 0 || b <= 0 || c <= 0) | 3 |
| if ((a > b + c || b > a + c || c > a + b)) | 3 |
| if (a == b && b == c) | 2 |
| if (a == b || b == c || a == c) | 3 |
| Total Complexity | 12 |
Ok so I know the complexity, how many tests do I need?
To achieve 100% statement coverage, we need the following test cases:
| Test # | Description | Test Data |
| 1 | A valid scalene triangle. | a = 2, b = 3, c = 4 |
| 2 | An illegal triangle with a zero length side. | a = 0, b = 1, c = 1 |
| 3 | An illegal triangle with one short side. | a = 1, b = 4, c = 2 |
| 4 | A valid equilateral triangle. | a = 1, b = 1, c = 1 |
| 5 | A valid isosceles triangle. | a = 1, b = 2, c = 2 |
That’s where most developers would stop, highlighting again why developers should never test their own code. We need some additional cases to ensure that we cover all the conditionals, so let’s add to and the following tests.
| Test # | Description | Test Data |
| 6 | An illegal triangle where side b is zero length. | a = 1, b = 0, c = 1 |
| 7 | An illegal triangle where side c is zero length. | a = 1, b = 1, c = 0 |
| 8 | An illegal triangle where side b is too short. | a = 2, b = 1, c = 4 |
| 9 | An illegal triangle where side c is too short. | a = 4, b = 2, c = 1 |
| 10 | An isosceles triangle where the short side is b. | a = 2, b = 1, c = 2 |
| 11 | An isosceles triangle where the short side is c. | a = 2, b = 2, c = 1 |
| 12 | An equilateral triangle to test the right side of the && in line 13, i.e. b == c | a = 1, b = 1, c = 1 |
Ok so we now have 12 tests that cover all possible paths through the application, however we do have some duplication, like test 12, and some of the descriptions are a bit messy, so let’s refactor.
| Test # | Description | Test Data |
| 1 | A valid scalene triangle. | a = 2, b = 3, c = 4 |
| 2 | An illegal triangle where side a is zero length. | a = 0, b = 1, c = 1 |
| 3 | An illegal triangle where side b is zero length. | a = 1, b = 0, c = 1 |
| 4 | An illegal triangle where side c is zero length. | a = 1, b = 1, c = 0 |
| 5 | An illegal triangle where side a is too short. | a = 1, b = 2, c = 4 |
| 6 | An illegal triangle where side b is too short. | a = 2, b = 1, c = 4 |
| 7 | An illegal triangle where side c is too short. | a = 4, b = 2, c = 1 |
| 9 | A valid equilateral triangle. | a = 1, b = 1, c = 1 |
| 9 | An isosceles triangle where the short side is a. | a = 1, b = 2, c = 2 |
| 10 | An isosceles triangle where the short side is b. | a = 2, b = 1, c = 2 |
| 11 | An isosceles triangle where the short side is c. | a = 2, b = 2, c = 1 |
We now have a set of tests that has 100% path coverage, but are we done? Well the tester in me still can think of a couple of tests to add to cover the boundary conditions on line 3.
| Test # | Description | Test Data |
| 12 | An illegal triangle where side a is negative. | a = -1, b = 2, c = 2 |
| 13 | An illegal triangle where side b is negative. | a = 2, b = -1, c = 2 |
| 14 | An illegal triangle where side c is negative. | a = 2, b = 2, c = -1 |
Like most testing techniques using cyclomatic complexity is not a testing silver bullet that writes your test for you. It is however a useful technique for white box testing to guide you as to which tests need to be written for a specific function or method that has already been written. Now if only Visual Studio 2005 could programatically create these test cases for you when you generate the tests for an existing method.
