Цикломатичне число Маккейба
Для обчислення цикломатичного числа Маккейба Z(G) застосовується формула
деe -число дуг орієнтованого графа G;v- Число вершин;2p- Число компонентів зв'язності графа.
Число компонентів зв'язності графа можна розглядати як кількість дуг, які необхідно додати для перетворення графа на сильнозв'язний.Сильнозв'язнимназивається граф, будь-які дві вершини якого взаємно досяжні. Для графів коректних програм, тобто. графів, які мають недосяжних від точки входу ділянок і «висячих» точок входу і виходу, сильнозв'язаний граф виходить шляхом замикання дугою вершини, що позначає кінець програми на вершину, що позначає точку входу до цієї програми. Як правило,р= 1
Насправді Z(G) визначає число лінійно незалежних контурів у сильнозв'язному графі. Інакше висловлюючись, цикломатичне число Маккейба показує необхідну кількість проходів покриття всіх контурів сильнозв'язкового графа чи кількість тестових прогонів програми, необхідні вичерпного тестування за критерієм " працює кожна гілка "
зображено на малюнку 1,
цикломатичне число приe= 10,v= 8,p= 1,
визначиться як Z(G) = 10-8+2=4. Таким чином, є сильнозв'язний граф з чотирма лінійно незалежними контурами: a-b-c-g-e-h-a; a-b-c--e-h-a; a-b-d-f-e-h-a; a-b-d-e-h-a.
Цикломатичне число залежить лише від кількості предикатів, складність яких при цьому не враховується.
Наприклад, є два оператори умови:
IF (X>0 &FLAG = '1'B) !
Обидва оператори припускають єдине розгалуження і можуть бути представлені тим самим графом (рис. 2). Очевидно, цикломатичне число буде для обох операторіводнаковим, що не відображає складності предикатів, що дуже суттєво в оцінці програм.
Виходячи з цього, Г.Майєрс запропонував розширення цієї метрики. Суть підходу Г.Майерса полягає у поданні метрики складності програм як інтервалу [Z(G), Z(G)+h]. Для простого предикату h ≠ 0, а n-місцевих предикатів h=n-1. Таким чином, першому оператору відповідає інтервал [2, 2], а другому [2, 6].
Така метрика дозволяє розрізняти програми, які представлені однаковими графами.