Cyklomatická složitost

Cyklomatická složitost (nebo také podmínková složitost) je číslo vyjadřující složitost programu. Udává minimální počet lineárně nezávislých cest skrz zdrojový kód.

Na daném programu se cyklomatická složitost počítá pomocí grafu toku řízení toho programu: uzly grafu odpovídají neoddělitelným skupinám v programu (například tělu cyklu, podmínky). Orientované hrany odpovídají tomu, v jakém pořadí se skupiny příkazů budou provádět. Cyklomatickou složitost lze aplikovat individuálně na dané funkce, moduly, metody nebo třídy.

Jedna strategie pro měření se nazývá testování hlavní cesty. Testují se všechny možné cesty v programu; v tom případě je počet testů roven cyklomatickému číslu programu.

Popis

Graf toku řízení tohoto jednoduchého programu začíná na červeném uzlu, poté vstoupí do smyčky (to je ta skupina tří uzlů, které jsou hned pod červeným). Pro výstup z cyklu musí být splněna podmínka. Dále se nachází IF podmínka, která rozděluje tok na dvě cesty, která se zpět zkříží do jedné a program končí modrým uzlem. Pro tento graf E = 9, N = 8 a P = 1, takže cyklomatická složitost podle rovnice
M = E – N + 2P je pro tento program 3.

Tato funkce je podobná jako výše, ale je vyjádřena jako silně souvislý graf. Pro tento graf máme alternativní metodu pro výpočet složitosti. E = 10, N = 8 a P = 1, takže cyklomatická složitost podle rovnice
M = E – N + P je pro tento program 3.

Cyklomatické číslo pro určitý úsek kódu je počet nezávislých cest skrz ten úsek. Například pokud neobsahuje žádnou IF podmínku nebo jakýkoliv cyklus (kód lze projít jednou cestou), tak je složitost 1. Například když bude kód obsahovat jednu IF podmínku, tak budou dvě možné cesty – jedna když podmínka dopadne jako TRUE a druhá když dopadne jako FALSE.

Pro strukturovaný program se odkazujeme na orientovaný graf, který představuje graf toku řízení pro daný kód. Složitost zjistíme:
M = E – N + 2P
M = cyklomatická složitost
E = počet hran v grafu
N = počet uzlů v grafu
P = počet připojených komponent

Cyklomatická složitost se jinak počítá pro programy s více možnými ukončeními; v tomto případě je rovna:
π – s + 2
Kde π je počet rozhodovacích bodů v programu a s je počet ukončovacích bodů.

Jiné vyjádření se používá, když je ukončovací bod (exit point) spojen zpět na vstupní bod (entry point). V tomto případě tomu grafu říkáme silně souvislý a cyklomatická složitost programu je rovna cyklomatickému číslu grafu. Pak je složitost definována jako
M = E – N + P (stejně jako cyklomatické číslo v teorii grafů) je podrobněji popsána níže.

Cyklomatické číslo v teorii grafů

Cyklomatické číslo grafu je minimální počet hran takový, že po jejich odstranění nebude v grafu žádný cyklus.

Reference

V tomto článku byl použit překlad textu z článku Cyclomatic complexity na anglické Wikipedii.

Související články

• Komplexita
• Počítačový program
• Programování
• Softwarové inženýrství
• Testování softwaru
• Řídící struktura