McCabe metric

from Wikipedia, the free encyclopedia

The cyclomatic complexity (also cyclomatic complexity - Cyclomatic complexity ) is a software metric with which the complexity of a software module can be measured (function, procedure, or in general a piece of source code). Cyclomatic complexity was introduced in 1976 by Thomas J. McCabe .

The idea behind McCabe's software metrics is that, above a certain level of complexity, the module can no longer be understood by humans. The cyclomatic complexity is defined as the number of linearly independent paths on the control flow graph of a module. This means that the number is an upper bound for the minimum number of test cases that are necessary to achieve a complete branch coverage of the control flow graph.

calculation

There are two approaches how one can calculate the cyclomatic complexity according to McCabe - i.e. the linearly independent paths in a control flow - depending on the number of binary branches or depending on the number of nodes and edges in control flow graphs.

Calculation by number of binary branches

The McCabe complexity measure is equal to the number of binary branches plus 1. When considering several control flow graphs (ie ) where

b: Number of binary branches, i.e. conditional statements with exactly two branches, e.g. B. IFInstructions and
p: Number of individual control flow graphs (one graph per function / procedure).

Branches with more than two branches can be broken down to binary branches. The following applies with

z: number of branches.

Calculation by number of nodes and edges

Alternatively, the complexity measure can be calculated from the number of nodes and edges in the control flow graph. In this case the McCabe number is defined as where

e: number of edges in the graph,
n: number of nodes in the graph and
p: number of connected components of the graph.

Interpretation of the metric

According to McCabe, the cyclomatic number of a self-contained sub-program should not be higher than 10, as otherwise the program would be too complex and difficult to test. However, this rule is controversial because the cyclomatic number only increases when branching instructions such as are IFinserted, but not when other instructions are inserted (for example, a screen output). It is therefore only possible to make a statement about the test effort (number of independent program paths to be tested).

criticism

Complexity switchmeasures can sometimes not be grasped intuitively for people; instructions in particular are often viewed as less complex than their complexity number suggests. In the following example, there can be no question of a lack of clarity for people, but with a complexity number of 8 it achieves a very high value. 

const String wochentagsname(const int nummer)
{
  switch (nummer)
  {
    case 1: return "Montag";
    case 2: return "Dienstag";
    case 3: return "Mittwoch";
    case 4: return "Donnerstag";
    case 5: return "Freitag";
    case 6: return "Samstag";
    case 7: return "Sonntag";
  }
  return "(unbekannter Wochentag)";
}

In practice, the switchconstruction is often used for this type of lookup. The "weekday name" function comprises eight control flow paths and eight exit points, has a correspondingly high complexity number of 8 and is nevertheless easy to oversee for humans. Nevertheless, the construction harbors dangers, namely the possibility of incorporating side effects into individual case instructions .

The following implementation of the same example is considerably less complex because no side effects can be programmed for the eight cases, each of which has its own return instruction and which are also not separated from one another: 

const String wochentagsname(const int nummer)
{
  string[] tage = new string[]
  {
    "Montag",
    "Dienstag",
    "Mittwoch",
    "Donnerstag",
    "Freitag",
    "Samstag",
    "Sonntag"
  };

  char ergebnis[] = "(unbekannter Wochentag)";
  if ((nummer >= 1) && (nummer <= sizeof (tage)))
  {
    ergebnis = tage[nummer - 1];
  }
  return ergebnis;
}

However, the restructured code contains more error-prone places (use of the sizeof operator , range checking for data field days and explicit calculation of the index).

literature

  • Thomas J. McCabe: A Complexity Measure. In: IEEE Transactions on Software Engineering , Volume SE-2, 1976, pp. 308-320.
  • Helmut Balzert : textbook of software technology; Software management, software quality assurance, business modeling . Pp. 481-482.

Web links