Zyklomatische Komplexität

Die McCabe-Metrik (auch zyklomatische Komplexität - cyclomatic complexity) ist eine Software-Metrik, mit der die Komplexität eines Software-Moduls gemessen werden kann. Die zyklomatische Komplexität wurde bereits 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. Er definiert seine cyclomatic complexity auf dem Kontrollflussgraphen eines Moduls. Einfach ausgedrückt ist das Komplexitätsmaß nach McCabe gleich der Anzahl der binären Verzweigungen plus 1.

Die so ermittelte McCabe-Zahl ist ein Maß für die Komplexität des Kontrollflusses eines Programms (Funktion, Prozedur oder Stück Code). Betrachtet man den Kontrollflussgraphen, wobei die Anweisungen als Knoten und der Kontrollfluss zwischen den Anweisungen als Kanten dargestellt sind, dann ist die McCabe-Zahl M definiert als M = e − n + 2p

e: Anzahl Kanten im Graphen

n: Anzahl Knoten im Graphen

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

Bei Betrachtung eines einzelnen Kontrollflussgraphen (also p=1) gilt M = b + 1 mit

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

M ist eine untere Schranke für die Anzahl der möglichen Wege durch ein Programm.

M ist außerdem eine obere Schranke für die Anzahl der Testfälle, die nötig sind, um eine vollständige Kantenabdeckung des Kontrollflussgraphen zu erreichen.

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, so kann im folgenden Beispiel von Unübersichtlichkeit für Menschen keine Rede sein, jedoch wird als Komplexitätsmaß ein recht hoher Wert angegeben, zum Beispiel von dem Werkzeug CodeAnalyzer.

const char* 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 Lookup-Aufgaben dieser Art eingesetzt, die man in Sprachen wie Java zum Beispiel mit Maps lösen würde.

Literatur

• T. J. McCabe: A Complexity Measure. in: IEEE Transactions on Software Engineering, Band SE-2, 308-320. 1976.
• Helmut Balzert: Lehrbuch der Software-Technik ; Software-Management, Software-Qualitätssicherung, Unternehmensmodellierung, Seiten 481-482.

Weblinks

• A Complexity Measure - Thomas J. McCabe, 1976