什么是圈复杂度？

1. Introduction

In this tutorial, we’ll explain how to calculate the cyclomatic complexity of a software module.

According to the rational asset analyzer software documentation, cyclomatic complexity is a measurement of the stability and confidence of a software module. The higher the cyclomatic complexity of a software module, the more defects it has. Therefore, it is recommended that a complex software module is split into smaller modules.

2. Problem Description

Let be a software module. The cyclomatic complexity of is the number of linearly independent paths through .

For example, let’s say we have the following module (in pseudocode):

algorithm CheckTheInteger(x):
    // INPUT
    //    x = an integer
    // OUTPUT
    //    No output

    if x < 100:
        print x "is less than 100"
    else:
        print x "is greater than or equal to 100"

There are two linearly independent paths.

The higher the cyclomatic complexity of a software module, the more complex it is. A use case for this is in software development. Software developers are always designing modules, and it’s important for them to know whether the module is complex.

3. Cyclomatic Complexity

Cyclomatic complexity was developed by Thomas J. McCabe in 1976.

A control flow graph (CFG) is an abstract representation of a software module. Each node (in the CFG) represents a single block of code, with statements without any jumps. Each directed edge (in the CFG) represents a jump between nodes. A linearly independent path of a software module is a path from the entry to the exit node of the module’s CFG:

The number of linearly independent paths in the CFG above is three.

There are two known methods for calculating the cyclomatic complexity of a software module.

3.1. Method 1

Given an input module , we compute its corresponding CFG . Then we count the number of nodes , the number of edges , and the number of connected components in . The cyclomatic complexity value is equal to – + 2.

3.2. Method 2

McCabe showed that the cyclomatic complexity of a software module is equal to one plus the number of decision statements in the software module. According to McCabe, decision statements can be:

• Loop statements (i.e., D0, DO-WHILE)
• The CASE alternatives in a SWITCH statement (the default/ the else case is excluded)
• Each logical operator in an IF statement

In a CFG, a decision node corresponds to a decision statement.

Given an input module , we compute its corresponding CFG . Then we count the number of decision nodes in and add one to the value.

The number of nodes in the CFG of a software module with no decision statements is one. Hence, the cyclomatic complexity is zero.

4. Example

Let’s work out an example from a lecture on cyclomatic complexity:

algorithm CheckTheInteger(x):
    // INPUT
    //    x = an integer
    // OUTPUT
    //    No output

    while x < 10:
        if x > 5:
            print x
        else:
            print x "is less than 6"
        
        x <- x + 1

First, we compute its corresponding CFG:

4.1. Method 1

We count the number of edges, the number of nodes, and the number of connected components in the CFG.

Finally, we compute the cyclomatic complexity, which is 7 – 6 + 2(1) = 3. This means that there are three linearly independent paths in the module. These are highlighted in blue in the figure below:

4.2. Method 2

We count the number of decision nodes (or decision statements in the corresponding software module). The and nodes are decision nodes. Therefore, the number of decision nodes in the CFG is two. The cyclomatic complexity is equal to the number of decision nodes plus one, which is three.

5. Complexity

The depth-first search (DFS) algorithm traverses the given CFG to count the number of nodes (or decision nodes), edges, and connected components.

Let be the number of nodes and be the number of edges (in the given CFG).  If the CFG is represented by an adjacency list, then the DFS algorithm will take time.

6. Conclusion

In this article, we showed how to calculate the cyclomatic complexity of a software module using two different methods. The two cyclomatic complexity methods depend on the CFG of the given software module.