McCabe-Metrik

Die McCabe-Metrik (auch zyklomatische Komplexität – cyclomatic complexity) ist eine Softwaremetrik, mit der die Komplexität eines Software-Moduls (Funktion, Prozedur oder allgemein ein Stück Sourcecode) gemessen werden kann. Die zyklomatische Komplexität wurde 1976 durch Thomas J. McCabe eingeführt.

Hinter der Software-Metrik von McCabe steckt der Gedanke, dass ab einer bestimmten Komplexität das Modul für den Menschen nicht mehr begreifbar ist. Die cyclomatic complexity ist definiert als Anzahl linear unabhängiger Pfade auf dem Kontrollflussgraphen eines Moduls. Damit ist die Zahl eine obere Schranke für die minimale Anzahl der Testfälle, die nötig sind, um eine vollständige Zweigüberdeckung des Kontrollflussgraphen zu erreichen.

Berechnung

Es gibt zwei Ansätze, wie man die zyklomatische Komplexität nach McCabe – also die linear unabhängigen Pfade in einem Kontrollfluss – berechnen kann, abhängig von der Anzahl der Binärverzweigungen oder abhängig von der Anzahl der Knoten und Kanten in Kontrollflussgraphen.

Berechnung durch Anzahl Binärverzweigungen

Das Komplexitätsmaß nach McCabe $M$ ist gleich der Anzahl der binären Verzweigungen $b$ plus 1. Bei Betrachtung mehrerer Kontrollflussgraphen (also $p>1$) gilt $M=b+p$ wobei

b: Anzahl Binärverzweigungen, also bedingte Anweisungen mit genau zwei Zweigen, z. B. IF-Anweisungen und

p: Anzahl der einzelnen Kontrollflussgraphen (ein Graph pro Funktion/Prozedur).

Verzweigungen mit mehr als zwei Zweigen können auf Binärverzweigungen heruntergebrochen werden. Dabei gilt $b=z-1$ mit

z: Anzahl Zweige.

Berechnung durch Anzahl Knoten und Kanten

Alternativ kann man das Komplexitätsmaß noch durch die Anzahl der Knoten und Kanten im Kontrollflussgraph berechnen. In diesem Fall ist die McCabe-Zahl definiert als $M=e-n+2p$ wobei

e: Anzahl Kanten im Graphen,

n: Anzahl Knoten im Graphen und

p: Anzahl der Zusammenhangskomponenten des Graphen.

Interpretation der Metrik

Laut McCabe sollte die zyklomatische Zahl eines in sich abgeschlossenen Teilprogramms nicht höher als 10 sein, da sonst das Programm zu komplex und zu schwer zu testen ist. Diese Regel ist allerdings umstritten, da sich die zyklomatische Zahl nur dann erhöht, wenn verzweigende Anweisungen wie IF eingefügt werden, aber nicht beim Einfügen sonstiger Anweisungen (zum Beispiel einer Bildschirmausgabe). Es kann also lediglich eine Aussage über den Testaufwand (Anzahl der zu testenden unabhängigen Programmpfade) getroffen werden.

Kritik

Komplexitätsmaße sind für Menschen mitunter nicht intuitiv zu erfassen, insbesondere switch-Anweisungen werden häufig als weniger komplex angesehen, als ihre Komplexitätszahl vermuten lässt. So kann im folgenden Beispiel von Unübersichtlichkeit für Menschen keine Rede sein, jedoch erreicht es mit einer Komplexitätszahl von 8 einen recht hohen Wert.

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 der Praxis wird die switch-Konstruktion häufig für Nachschlageaufgaben dieser Art eingesetzt. Die Funktion "wochentagsname" umfasst acht Kontrollflusspfade und acht Ausstiegspunkte, hat entsprechend eine hohe Komplexitätszahl von 8 und ist trotzdem vom Menschen leicht zu überblicken. Dennoch birgt die Konstruktion Gefahren, nämlich die Möglichkeit in einzelne Case-Anweisungen Nebenwirkungen einzubauen.

Die folgende Implementierung des gleichen Beispiels hat eine erheblich niedrigere Komplexität, weil keine Nebenwirkungen für die acht Fälle programmiert werden können, die jeweils eine eigene Rückgabeanweisung haben und die zudem untereinander nicht getrennt sind:

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

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

Allerdings enthält der umstrukturierte Code mehr fehlerträchtige Stellen (Nutzen des Operators sizeof, Bereichsprüfung für Datenfeld tage und explizite Berechnung des Indexes).

Literatur

• Thomas J. McCabe: A Complexity Measure. In: IEEE Transactions on Software Engineering, Band SE-2, 1976, S. 308–320.
• Helmut Balzert: Lehrbuch der Software-Technik; Software-Management, Software-Qualitätssicherung, Unternehmensmodellierung. S. 481–482.
• Christof Ebert, James Cain: Cyclomatic Complexity. In: IEEE Software, 33(6), 2016, S. 27–29.

Siehe auch

• Kontrollflussorientierte Testverfahren
• Softwaremetrik
• Softwarequalität

Weblinks

• Thomas J. McCabe A Complexity Measure. (PDF; 1,68 MB) 1976
• Berechnung der McCabe-Metrik (Beispielprojekt) (PDF; 0,74 MB)
• Messung von McCabe-Metriken
• McCabe’s Cyclomatic Complexity and Why We Don’t Use It.