Цикломатична складність

Цикломати́чна скла́дність — метрика програмного забезпечення, розроблена Томасом Мак Кабе. Використовується для оцінки складності програм. Обчислює кількість лінійно незалежних шляхів в алгоритмі роботи програми на основі її вихідних текстів.

Концепція метрики, але не метод, в дечому схожа на концепцію метрики загальної складності текстів Флеша-Кінкейда.

Цикломатична складність обчислюється на основі графу, що відображає цикл роботи програми. Вершинам графа зіставляють команди програми. Ребро сполучає дві вершини якщо друга команда може бути виконана одразу після першої.

Визначення

Граф потоку керування простої програми. Програма починає виконання в червоній вершині, тоді входить в цикл (група з трьох вершин безпосередньо за червоною). По виході з циклу знаходиться умовний оператор (група наступна за циклом), і насамкінець програма завершується в блакитній вершині. Для цього графа E = 9, N = 8 і P = 1, тобто цикломатична складність цієї програми 3.

Цикломатична складність відтинку сирцевого коду — кількість лінійно незалежних шляхів в сирцевому коді. Наприклад, якщо сирцевий код не містить місць прийняття рішень таких як IF тверджень або FOR циклів, складність дорівнює 1, через наявність лиш одного шляху в сирцевому коді. якщо код містить один IF, тоді наявні два шляхи в сирцевому коді, один якщо твердження IF оцінюється як TRUE і другий якщо як FALSE.

Математично, цикломатична складність структурної програми визначається за допомогою орієнтованого графа утворенного базовими блоками програми, з ребрами між двома базовими блоками якщо керування може бути передане від першого до другого (граф потоку керування програми). Тоді складність визначається як:

M = E − N + 2P

де

M = цикломатична складність

E = кількість ребер в графі

N = кількість вершин в графі

P = кількість компонент зв'язності

Із тією самою функцією, що й нагорі, показаний як сильно-зв'зний граф потоку керування, для обрахунку через альтернативний спосіб. Для цього графа E = 10, N = 8 і P = 1, тож цикломатична складність залишається 3.

Альтернативний спосіб це використання графа в якому кінцева вершина зв'язана з вхідною. В цьому випадку, кажуть, що граф є сильно зв'язним, і цикломатична складність прогами дорівнює цикломатичному числу графа (також відомому як перше число Бетті), яке визначається як:

M = E − N + P

На це можна дивитись як на підрахунок числа лінійно незалежних циклів, що існують в графі. Зауважимо, що з'єднання кінцевої і вхідної вершин програми, гарантує наявність щонайменше одного такого циклу.

Для однієї програми (оба підпрограми), P завжди дорівнює 1. Однак, цикломатична складність може бути обчислена і для декількох таких програм або підпрограм одночасно (наприклад, для всіх методів класу), в цьому випадку P буде дорівнювати кількості піпрограм в питанні, кожна підпрограма буде з'являтись як незв'язана підмножина графа.

Можна показати, що цикломатична складність будь-якої структурної програми тільки з однією точкою входу і однією виходу дорівнює кількості місць прийняття рішень (тобто, IF тверджень або умовних циклів), що містяться в цій програмі плюс один.

Цикломатичну складність можна обчислювати і для програм з багатьма точками виходу; в цьому випадку вона дорівнює:

π - s + 2

де π це кількість місць прийняття рішень в програмі, а s це кількість точек виходу.

Формальне визначення

формально, цикломатична складність може бути визначена як відносне число Бетті, розмір відноснооднородної групи:

$M := b_1(G,t) := \operatorname{rank}\,H_1(G,t)$

це читається як «перший однорідний граф G, відносно термінальної вершини t». Це технічний шлях сказати «кількість лінійно незалежних маршрутів через граф від входу до виходу».

Етимологія

Назва Цикломатична складність призводить до певної плутанини, через те, що ця метрика не тільки підраховує цикли в програмі. Натомість, ця назва пов'язана з кількістю різних циклів в графі потоку керування програми, після додання уявного переходу із кінцевої вершини до вхідної вершинри.

На думку Томаса Мак Кабе кращою назвою для повсюдного використання була б умовна складність (англ. Conditional Complexity).

Дивіться також

• Цикломатичне число — характеристика графів.

Примітки

Посилання

• A Complexity Measure (англ.) — оригінальна праця Мак Кабе (1976).