A Complexity Measure
THOMAS J. McCABE. San Francisco, California, USA — October 13 - 15, 1976 Изложение в pdf – http://dl.acm.org/citation.cfm?id=807712&CFID=878209961&CFTOKEN=70636417
Введение
В статье описана метрика позволяющая оценить на сколько сложно будет тестировать программу и на сколько сложно будет ее поддерживать. Вводится понятие - цикломатической сложности программы (англ. Cyclomatic complexity of a program) — структурная (или топологическая) мера сложности компьютерной программы. При вычислении цикломатической сложности используется граф потока управления программы. Узлы графа соответствуют неделимым группам команд программы, они соединены ориентированными рёбрами, если группа команд, соответствующая второму узлу, может быть выполнена непосредственно после группы команд первого узла. Цикломатическая сложность может быть также вычислена для отдельных функций, модулей, методов или классов в пределах программы. Мак-Кейб применял вычисление цикломатической сложности при тестировании. Предложенный им метод заключался в тестировании каждого линейно независимого маршрута через программу, в этом случае число необходимых тестов равно цикломатической сложности программы.
Содержание
Цикломатическая сложность части программного кода — количество линейно независимых маршрутов через программный код. Например, если исходный код не содержит никаких точек ветвления или циклов, то сложность равна единице, поскольку, есть только единственный маршрут через код. Если код имеет единственный оператор IF, содержащий простое условие, то существует два пути через код: один если условие оператора IF имеет значение TRUE и один — если FALSE. Математически цикломатическая сложность структурированной программы определяется с помощью ориентированного графа, узлами которого являются блоки программы, соединенные рёбрами, если управление может переходить с одного бока на другой. Тогда сложность определяется как::
v(G) = E − N + 2P,
где:
E = количество рёбер в графе,
N = количество узлов в графе,
P = количество компонент связности.
В другой формулировке используется граф, в котором каждая точка выхода соединена с точкой входа. В этом случае граф является сильносвязным и цикломатическая сложность программы равна цикломатическому числу этого графа которое определяется как::
v(G) = E − N + P
Это определение может рассматриваться как вычисление числа линейно независимых циклов, которые существуют в графе, то есть тех циклов, которые не содержат в себе других циклов. Так как каждая точка выхода соединена с точкой входа, то существует по крайней мере один цикл для каждой точки выхода. Для простой программы, или подпрограммы, или метода P всегда равно 1. Однако цикломатическая сложность может применяться к нескольким таким программам или подпрограммам , в таком случае P равно числу подпрограмм, о которых идёт речь, так как каждая подпрограмма может быть представлена как независимая часть графа. Может быть показано, что цикломатическая сложность любой структурированной программы с только одной точкой входа и одной точкой выхода эквивалентна числу точек ветвления (то есть, операторов if или условных циклов), содержащихся в этой программе, плюс один. Цикломатическая сложность может быть распространена на программу с многочисленными точками выхода; в этом случае она равна:
π − s + 2
где:
π — число точек ветвления в программе,
s — число точек выхода.
Примеры графов и их цикломатических чисел из статьи
Тут будут 4 картинки, но пока что у меня недостаточно прав, чтобы их загрузить.
Вывод
В статье рекомендуется следить за цикломатической сложностью программы, если цикломатическая сложность вашего кода становится больше 10. Пора подумать над его реструктуризацией и упрощением. Для тестирования же у цикломатического числа есть ещё два приложения:
1) Это оценка сверху на число тест кейсов необходимых для того, чтобы обеспечить покрытие условий при тестировании методом белого ящика.
2) Это оценка снизу на число тест кейсов необходимых, чтобы обеспечить покрытие ветвей при тестирования методом белого ящика.