Цикломатична складність
Цикломатична складність програми(англ. cyclomatic complexity of a program) - структурна (або топологічна) міра складності комп'ютерної програми. Захід був розроблений Томасом Дж. Маккейбом в 1976 році.
Під час обчислення цикломатичної складності використовується граф потоку управління програми. Вузли графа відповідають неподільним групам команд програми, вони з'єднані орієнтованими ребрами, якщо група команд, яка відповідає другому вузлу, може бути виконана безпосередньо після групи команд першого вузла. Цикломатична складність може бути обчислена для окремих функцій, модулів, методів або класів в межах програми.
Маккейб застосовував обчислення цикломатичної складності під час тестування. Запропонований ним метод полягав у тестуванні кожного лінійно незалежного маршруту через програму, у цьому випадку кількість необхідних тестів дорівнює цикломатичній складності програми. [1]
Зміст
Цикломатична складність частини програмного коду – кількість лінійно незалежних маршрутів через програмний код. Наприклад, якщо вихідний код не містить жодних точок розгалуження або циклів, складність дорівнює одиниці, оскільки є тільки єдиний маршрут через код. Якщо код має єдиний оператор IF , що містить просту умову, то існує два шляхи через код: якщо умова оператора IF має значення TRUE і один - якщо FALSE .
Математично цикломатична складність структурованої програми [2] визначається за допомогою орієнтованого графа, вузлами якого є блоки програми, з'єднані ребрами, якщо керування може переходити з одного блоку на інший. Тоді складність визначається як: [3] :
M= цикломатична складність,E= кількість ребер у графі,N=кількість вузлів у графі,P= кількість компонент зв'язності.
В іншому формулюванні використовується граф, у якому кожна точка виходу з'єднана з точкою входу. У цьому випадку граф є сильнозв'язним, і цикломатична складність програми дорівнює цикломатичному числу цього графа (також відомому як перше число Бетті), яке визначається як [3]
Це визначення може розглядатися як обчислення числа лінійно незалежних циклів, які існують у графі, тобто тих циклів, які не містять інших циклів. Так як кожна точка виходу з'єднана з точкою входу, існує принаймні один цикл для кожної точки виходу.
Для простої програми, або підпрограми, або методуPзавжди дорівнює 1. Однак цикломатична складність може застосовуватися до кількох таких програм або підпрограм (наприклад, до всіх методів у класі), у такому разіPдорівнює числу підпрограм, про які мова, оскільки кожна підпрограма може бути представлена як незалежна частина графа.
Може бути показано, що цикломатична складність будь-якої структурованої програми з лише однією точкою входу і однією точкою виходу еквівалентна числу точок розгалуження (тобто операторів if або умовних циклів), що містяться в цій програмі плюс один. [3] [4]
Цикломатична складність може бути поширена на програму з численними точками виходу; у цьому випадку вона дорівнює [4] [5]
π - число точок розгалуження в програмі,s- число точок виходу.
Формальне визначення
Формально, цикломатична складність може бути визначена як відносне число Бетті:
тобто «перша гомологія графаGщодо термінальних вузлівt. Це інший спосіб сказати «число лінійнонезалежних маршрутів через граф від входу до виходу.
Крім того, цикломатичну складність можна обчислити через абсолютне число Бетті (за допомогою абсолютної гомології, а не відносної), об'єднавши всі термінальні вузли даного компонента (що еквівалентно з'єднанню точок виходу з точкою входу), у цьому випадку для нового, розширеного, графа G
Обмеження складності під час розробки
Застосування під час тестування програмного забезпечення
Інше застосування цикломатичної складності — визначення кількості тестів, необхідні повного покриття коду.
Він корисний, оскільки цикломатична складністьMмає дві властивості для конкретного модуля:
- M- оцінка зверху для кількості тестів, що забезпечують покриття умов (крапок розгалуження);
- M— оцінка знизу кількості маршрутів через граф потоку управління і, таким чином, кількості тестів для повного покриття шляхів.
У складі інших метрик
Цикломатична складність використовується як один з параметрів в індексі зручності супроводу (англ. maintainability index) [6] .