Цикломатическая сложность

Цикломати́ческая сло́жность програ́ммы (англ. cyclomatic complexity of a program) — структурная (или топологическая) мера сложности компьютерной программы. Мера была разработана Томасом Дж. Маккейбом в 1976 году.

При вычислении цикломатической сложности используется граф потока управления программы. Узлы графа соответствуют неделимым группам команд программы, они соединены ориентированными рёбрами, если группа команд, соответствующая второму узлу, может быть выполнена непосредственно после группы команд первого узла. Цикломатическая сложность может быть также вычислена для отдельных функций, модулей, методов или классов в пределах программы.

Маккейб применял вычисление цикломатической сложности при тестировании. Предложенный им метод заключался в тестировании каждого линейно независимого маршрута через программу, в этом случае число необходимых тестов равно цикломатической сложности программы.^[1]

Описание

Граф управления потоком простой программы. Программа начинает выполняться с красного узла, затем идут циклы (после красного узла идут две группы по три узла). Выход из цикла осуществляется через условный оператор (нижняя группа узлов) и конечный выход из программы в синем узле. Для этого графа E = 9, N = 8 и P = 1, цикломатическая сложность программы равна 9 − 8 + 2 × 1 = 3 (рассчитано по первому варианту)

Цикломатическая сложность части программного кода — количество линейно независимых маршрутов через программный код. Например, если исходный код не содержит никаких точек ветвления или циклов, то сложность равна единице, поскольку есть только единственный маршрут через код. Если код имеет единственный оператор IF, содержащий простое условие, то существует два пути через код: один если условие оператора IF имеет значение TRUE и один — если FALSE.

Математически цикломатическая сложность структурированной программы^[2] определяется с помощью ориентированного графа, узлами которого являются блоки программы, соединенные рёбрами, если управление может переходить с одного блока на другой. Тогда сложность определяется как:^[3]:

M = E − N + 2P,

где:

M = цикломатическая сложность,

E = количество рёбер в графе,

N = количество узлов в графе,

P = количество компонент связности.

Сильносвязный граф управления потоком той же функции. Для этого графа E = 10, N = 8 и P = 1, следовательно, цикломатическая сложность программы, рассчитанная по второму варианту, также равна 10 − 8 + 1 =3

В другой формулировке используется граф, в котором каждая точка выхода соединена с точкой входа. В этом случае граф является сильносвязным, и цикломатическая сложность программы равна цикломатическому числу этого графа (также известному как первое число Бетти), которое определяется как^[3]

M = E − N + P.

Это определение может рассматриваться как вычисление числа линейно независимых циклов, которые существуют в графе, то есть тех циклов, которые не содержат в себе других циклов. Так как каждая точка выхода соединена с точкой входа, то существует по крайней мере один цикл для каждой точки выхода.

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

Может быть показано, что цикломатическая сложность любой структурированной программы с только одной точкой входа и одной точкой выхода эквивалентна числу точек ветвления (то есть, операторов if или условных циклов), содержащихся в этой программе, плюс один.^[3][4]

Цикломатическая сложность может быть распространена на программу с многочисленными точками выхода; в этом случае она равна^[4][5]

π − s + 2,

где:

π — число точек ветвления в программе,

s — число точек выхода.

Формальное определение

Формально, цикломатическая сложность может быть определена как относительное число Бетти:

${\displaystyle M:=b_{1}(G,t):=\operatorname {rank} H_{1}(G,t),}$

то есть «первая гомология графа G относительно терминальных узлов t. Это другой способ сказать «число линейно независимых маршрутов через граф от входа к выходу».

Кроме того, цикломатическую сложность можно вычислить через абсолютное число Бетти (с помощью абсолютной гомологии, а не относительной), объединив все терминальные узлы данного компонента (что эквивалентно соединению точек выхода с точкой входа), в этом случае для нового, расширенного, графа ${\displaystyle {\tilde {G}}}$

${\displaystyle M=b_{1}({\tilde {G}})=\operatorname {rank} H_{1}({\tilde {G}}).}$

Применение

Ограничение сложности при разработке

Одно из первоначально предложенных Маккейбом применений состоит в том, что необходимо ограничивать сложность программ во время их разработки. Он рекомендует, чтобы программистов обязывали вычислять сложность разрабатываемых ими модулей и разделять модули на более мелкие всякий раз, когда цикломатическая сложность этих модулей превысит десять.^[3] Эта практика была включена НИСТ-ом в методику структурного тестирования с замечанием, что со времени исходной публикации Маккейба выбор значения 10 получил весомые подтверждения, однако в некоторых случаях может быть целесообразно ослабить ограничение и разрешить модули со сложностью до 15. В данной методике признаётся, что иногда могут существовать причины для выхода за рамки согласованного лимита. Это сформулировано как рекомендация: «Для каждого модуля следует либо ограничивать цикломатическую сложность до согласованных пределов, либо предоставить письменное объяснение того, почему лимит был превышен».

Применение при тестировании программного обеспечения

Другое применение цикломатической сложности — определение количества тестов, необходимых для полного покрытия кода.

Он полезен, поскольку цикломатическая сложность M имеет два свойства, для конкретного модуля:

• M — оценка сверху для количества тестов, обеспечивающих покрытие условий (точек ветвления);
• M — оценка снизу для количества маршрутов через граф потока управления и, таким образом, количества тестов для полного покрытия путей.

В составе других метрик

Цикломатическая сложность используется в качестве одного из параметров в индексе удобства сопровождения (англ. maintainability index)^[6].

Примечания

1. A. J. Sobey. Основной маршрут тестирования  (неопр.). Дата обращения: 2 мая 2009. Архивировано 26 апреля 2012 года.
2. Здесь термин «структурированная» означает, что программа имеет только одну точку выхода.
3. McCabe. A Complexity Measure (англ.) // IEEE Transactions on Software Engineering^[англ.] : journal. — 1976. — December. — P. 308—320. Архивировано 29 декабря 2009 года.
4. Belzer, Kent, Holzman and Williams. Encyclopedia of Computer Science and Technology (англ.). — CRC Press, 1992. — P. 367—368.
5. Harrison. Applying Mccabe's complexity measure to multiple-exit programs (англ.) // Software: Practice and Experience : journal. — J Wiley & Sons, 1984. — October.
6. Linda M. Laird, M. Carol Brennan John. Software Measurement and Estimation: A Practical Approach. — Wiley & Sons, 2006.