Exercise 3: Cyclomatic Complexity

Cyclomatic Complexity in Software Testing

Cyclomatic Complexity [^1] is a metric to measure the complexity of a software by measuring the independent paths in the source code. Cyclomatic complexity can be calculated by using control flow graphs or with respect to functions, modules, methods or classes within a software program. Some of basic flow graph notation are shown below.

[^1]: Arthur H. Watson and Thomas J. McCabe (1996). "Structured Testing: A Testing Methodology Using the Cyclomatic Complexity Metric"

Sequence

Represent basic flow of a program. It can be a computation process after the initialization are completed. It might be a next step of the computation process after the preceding step(s) is completed.

Branch Statement

If there is decision-making that is based on the previous operation or computation, the flow will have a branch. The most basic example of this flow is an if-else statement which creates two branches. A more complex example includes a nested if statement, which creates branches inside a branch, or an if statement with several else-if conditions that create multiple branches from the preceding node.

Loop

A loop happens when the program stays in a part to do some operations until the loop condition is completed. For example, it can be an iteration through a group of items or a computation process based on an algorithm. A control flow graph (CFG) with a loop can be easily identified by nodes with edges that point to each other (see the picture below).

Calculating the Cyclomatic Complexity

From the CFG of the program, the cyclomatic complexity (V(G)) can be calculated using the formula: V(G) = E - N + 2, where E is the number of edges and N is the number of nodes in the graph G. There is also another formula variation: V (G) = P + 1 where P is the number of predicate nodes, i.e. the node that has branches.

Let us use the program below as an example:

@Service
public class MusicService {

    @Autowired;
    private SongQueue songQueue;

    @Autowired
    private SongManager manager;

    public String removeSong(int position) {
        if (position < 0 || position > songQueue.size()-1) {
            throw new SongIndexOutOfBound(String.format("The index you entered: %d is out of bound", position));
        }

        Song removedSong = songQueue.getSong(position);

        if (position == songQueue.getCurrentSongIndex()) {
            manager.skip();
        } else {
            songQueue.remove(position);
        }
        return removedSong;
    }
}

removeSong is a method to remove a song from a queue playlist. The flow of this method consists of three branches (from one if statement and one if-else statement). See the flow graph of this method below.

Computing mathematically based on the flow graph above will yield the cyclomatic complexity of 2. The graph have one condition node (node 1); therefore, it has the following value:

V(G) = P +1
V(G) = 1 + 1
V(G) = 2

This implementation will have two independent paths: either throw an exception or return the removed song in the end. It matches the mathematical calculation performed above.

Let us modify the implementation of removeSong a bit. See the program below. The return statements are inside the second if-statement and outside as the final statement of the program. It will modify the flow graph a bit.

@Service
public class MusicService {

    @Autowired;
    private SongQueue songQueue;

    @Autowired
    private SongManager manager;

    public String removeSong(int position) {
        if (position < 0 || position > songQueue.size()-1) {
            throw new SongIndexOutOfBound(String.format("The index you entered: %d is out of bound", position));
        }

        Song removedSong = songQueue.getSong(position);

        if (position != songQueue.getCurrentSongIndex()) {
            return songQueue.remove(position);
        }
        manager.skip();
        return removedSong;
    }
}

The cyclomatic complexity of this modified version of removeSong is 3. The possible outcome is either throw an exception, return statement from inside the if statement, or return from the last statement of the method. This graph has two conditions node (node 1 and node 3) which yield the following results:

V (G) = P +1
V (G) = 2 + 1
V (G) = 3

How this metric is useful for software testing?

Basis path testing is one of white box technique and it guarantees to execute at least one statement during testing. It checks each linearly independent path through the program, which means number test cases, will be equivalent to the cyclomatic complexity of the program.

Using the cyclomatic complexity of the previous example (the second version), the number of test cases needed is three because there are three different paths. The three test cases will also help to achieve branch coverage. This will ensure every possible path of the program is covered by the test cases.

The cyclomatic complexity value has an implication. It determines the complexity of the program. Based on the cyclomatic complexity value, a conclusion can be made to determine whether function testability is good enough.

• 1-4: low complexity – easy to test
• 5-7: moderate complexity – tolerable
• 8-10: high complexity – refactoring should be considered to ease testing
• 11+: very high complexity – very difficult to test

Tasks

You are asked to compute the cyclomatic complexity of a feature from your group project individually. Create a new branch based on the previous exercise's branch. The chosen function must be a different function from the last exercise and it should be involved in implementing a business process of the system (e.g. invoking service methods).

At the end of the exercise, do not forget to schedule an one-on-one meeting with a teaching assistant to demonstrate your work.

The due date of this exercise is: 1 December 2021, 21:00 UTC+7. Please ensure any updates to the fork repository related to this exercise were made and pushed before the due date.

Checklist

1. Choose one complex function from your group project. The complexity of your chosen function will affect the final grade of this exercise. You can choose a function that is implemented by your workmate, but do note that plagiarism rule still applies. Choose a different function from the previous exercise.
2. Create the CFG of the chosen function. Draw the picture of the graph using any tools (e.g. your favourite image editor, Graph Coverage Web App) and export the result as an image file. Put the image file in the exercise-assets folder in the root of your fork repository.
3. Compute the cyclomatic complexity of the chosen function based on the CFG you have drawn in the previous step. Document the process by describing the step-by-step calculation in a Markdown-formatted text file (exercise3.md) or a PDF file (exercise3.pdf). Put the file in the docs folder in your fork.
4. Use a library or plugin to compute the cyclomatic complexity of the chosen function. Compare the result with the one you have calculated manually. Is there any difference? Write your conclusion in exercise3.md or exercise3.pdf. You can use JaCoCo or PMD to compute the cyclomatic complexity.
5. Based on the result of the cyclomatic complexity, write a conclusion about the complexity of the program that you test. Write the answer in exercise3.md or exercise3.pdf.
6. Code coverage measurement tools such as JaCoCo (Java) and Coverage.py (Python) can compute coverage metrics such as line/statement coverage and branch coverage. Does line/statement coverage equivalent to a test requirement that derived using node coverage criteria? Explain your reasoning in the answer file i.e. exercise3.md or exercise3.pdf.
7. Similar to problem number 6, does branch coverage equivalent to a test requirement that derived using edge coverage criteria? Explain your reasoning in the answer file, i.e. exercise3.md or exercise3.pdf.
8. Based on the result of the cyclomatic complexity calculation, add more test cases into your fork until you can achieve 100% branch coverage of the chosen function.
9. (Optional) Based on the cyclomatic complexity that you have computed, is there any relationship between cyclomatic complexity and the number of tests from a test requirement that derived from a coverage criteria mentioned in the text book? Explain your reasoning in the answer file.

Appendix

JaCoCo

JaCoCo provides information of the program you test such as line coverage, branch coverage, etc. It also gives cyclomatic complexity and how many branch missed during the test. See the picture below:

IndonesianWordDescriptionHelper has the cyclomatic complexity of 5 (Cxty column). There is no branch missed during the test. Similarly, IndonesianSynonymAntonymResponseCreator has cyclomatic complexity of 4, but have one missed branch. You can also click on one of these classes to see the report of the individual methods.

Please compare the information provided by JaCoCo with the one you calculate manually.

PDF

You can also submit the exercise3.md as exercise3.pdf.

Tips: If you write using Markdown and want to export the document as PDF file, you can use pandoc to export text file written in Markdown into a PDF. You can also use an NPM package md-to-pdf if you prefer a more simple way to export the markdown to PDF (assuming you have npm/yarn installed)

---

Last update: 2021-12-01 13:24:49
Created: 2021-11-24 14:28:10