Метрики цикломатической сложности по Мак-Кейбу

Показатель цикломатической сложности является одним из наиболее распространенных показателей оценки сложности программных проектов. Данный показатель был разработан ученым Мак-Кейбом в 1976 г., относится к группе показателей оценки сложности потока управления программой и вычисляется на основе графа управляющей логики программы (control flow graph). Данный граф строится в виде ориентированного графа, в котором вычислительные операторы или выражения представляются в виде узлов, а передача управления между узлами - в виде дуг.

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

Для вычисления цикломатического числа Мак-Кейба l(G) применяется формула:

l(G) = m - n + 2p,

где m - число дуг ориентированного графа G;

n - число вершин;

p - число компонентов связности графа.

Мак-Кейб использует следующую теорему: в сильно связанном графе G цикломатическое число равно максимальному числу линейно-независимых циклов.

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

Упрощенная формула вычисления цикломатической сложности представляется следующим образом:

l(G) = m - n + 2

Как правило, при вычислении цикломатической сложности логические операторы не учитываются.

В процессе автоматизированного вычисления показателя цикломатической сложности, как правило, применяется упрощенный подход, в соответствии с которым построение графа не осуществляется, а вычисление показателя производится на основании подсчета числа операторов управляющей логики (if, switch и т.д.) и возможного количества путей исполнения программы.

Общий подход состоит в оценке сложности программы с помощью вычисления числа линейно-независимых путей, цикломатической сложности l(G), а также управления размером программ с помощью ограничения l(G) и использования l(G) как основы для методологии тестирования. Мак-Кейб обнаружил, что разумной верхней границей для цикломатической сложности является 10. Если программисты переступают эту границу, им следует или переписать программу, или разбить ее на модули.

В физическом смысле цикломатическое число для каждой дуги m=(v, u)| mÎM графа управления первая вершина (v) является исходной, а вторая (u) – конечной. Путь от одной вершины к другой вершине графа, если он состоит более чем из одной дуги, описывают последовательностью вершин соответствующих дуг (v, а,…, u) так, что исходная вершина будет первой в перечислении, а конечная – последней. Контур – это плоскость, ограниченная циклическим путем, в котором начальная и конечная вершина графа совпадают. Каждому контуру соответствует ограничивающий его путь, ведущий из начальной вершины графа в конечную.

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

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

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

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

Оценка цикломатической сложности Мак-Кейба полезна при подготовке тестовых данных и может дать нужную информацию о логической сложности программы. Однако при такой оценке не принимается во внимание выбор структур данных, алгоритмов, мнемонических имен переменных или комментариев, отсутствует обсуждение таких важных понятий, как удобство переноса, гибкость, эффективность.

Вычисление метрики в ходе реализации проекта (а при детальном проектировании оно возможно еще на этом этапе, не дожидаясь стадии кодирования) позволяет своевременно определить наиболее сложные, сопровождающиеся высокими рисками, структурные единицы и принять меры по устранению рисков за счет внесения корректив.

Рассмотрим пример. Пусть имеется программа, которая считывает из входного потока символы до тех пор, пока не будет обнаружен символ «#». Текст программы на языке Паскаль представлен на рис 6. Соответствующий граф управления программы показан на рис 7.

Рис 6. Программа ввода данных

Для представления программы в виде графа требуются определенные соглашения о том, что считать узлом графа, так как синтаксис операторов в языках программирования довольно разнообразен. При этом обычно учитывают только исполнимые операторы, исключая операторы описания данных. Желательно подобрать такие синтаксические формы операторов, которые в наибольшей степени подходят для отображения узлом графа. Линейные участки программы можно заменить одним узлом графа. В этом отношении использование схем алгоритмов или описание программ на псевдокоде может оказаться даже более предпочтительной формой описания программы, чем текст на языке программирования. В любом случае желательно преобразовать операторы цикла в эквивалентную последовательность операторов ветвления, добавив, при необходимости, операторы суммирования (счетчики) числа повторений цикла с «верхним» или «нижним» окончанием.

Рис 7. Граф управления программы ввода данных

Рис 8. Преобразование графа управления программы ввода данных в полносвязный граф

Определим цикломатическое число Маккейба для графа управления программы, изображенного на рис 7. Количество ребер графа равно пяти, количество вершин тоже равно пяти, поэтому цикломатическое число равно:

    l(G)=5-5+2=2

Программа организации ввода данных, имеющая граф управления с цикломатическим числом, равным 2, не обладает излишней сложностью и для ее тестирования достаточно подобрать два теста, покрывающие ветви (а, b, с) и (а, u) (рис 4). Заметим, что вершины v и а графа управления программы можно объединить, что не приведет к изменению цикломатического числа. Цикломатическое число зависит только от количества управляющих операторов, содержащих условные выражения (предикаты). При этом сложность предиката не учитывается. Если в операторе цикла while программы организации ввода данных (рис 4) усложнить условное выражение (предикат), изменив заголовок

while(s<>'#') на while(s<>'#' or s<>'*') граф управления и цикломатическое число останутся прежними.

Если программа содержит только операторы ветвления (без операторов выбора и переключения), цикломатическое число можно определить, используя выражение

M=u+1,

где u – количество операторов ветвления.

При необходимости операторы выбора или переключения с n ветвями, можно рассматривать как n операторов ветвления.

К достоинствам меры относят простоту ее вычисления и повторяемость результата, а также наглядность и содержательность интерпретации. В качестве недостатков можно отметить: нечувствительность к размеру ПО, нечувствительность к изменению структуры ПО, отсутствие корреляции со структурированностью ПО, отсутствие различия между конструкциями Развилка и Цикл, отсутствие чувствительности к вложенности циклов. Недостатки цикломатической меры привело к появлению ее модификаций, а также принципиально иных мер сложности.

Модификации показателя цикломатической сложности:

· «Модифицированная» цикломатическая сложность - рассматривает не каждое ветвление оператора множественного выбора (switch), а весь оператор как единое целое.

· «Строгая» цикломатическая сложность - включает логические операторы.

· «Упрощенная» вычисление цикломатической сложности - предусматривает вычисление не на основе графа, а на основе подсчета управляющих операторов.

· «актуальная» сложность - определяется как число независимых путей, которые проходит программа при тестировании;

· метрика сложности глобальных данных - вычисляется как цикломатическая сложность модуля и увеличивается на количество взаимосвязей с глобальными данными.

Метрики Чепина

Существует несколько ее модификаций. Рассмотрим более простой, а с точки зрения практического использования - достаточно эффективный вариант этой метрики.

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

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

1. Множество «Р» - вводимые переменные для расчетов и для обеспечения вывода. Примером может служить используемая в программах лексического анализатора переменная, содержащая строку исходного текста программы, то есть сама переменная не модифицируется, а только содержит исходную информацию.

2. Множество «М» - модифицируемые или создаваемые внутри программы переменные.

3. Множество «C» - переменные, участвующие в управлении работой программного модуля (управляющие переменные).

4. Множество «Т» - не используемые в программе (“паразитные”) переменные. Поскольку каждая переменная может выполнять одновременно несколько функций, необходимо учитывать ее в каждой соответствующей функциональной группе.

Далее вводится значение метрики Чепина:

Q = a1P + a2M + a3C + a4T

где a1, a2, a3, a4 - весовые коэффициенты.

Весовые коэффициенты использованы для отражения различного влияния на сложность программы каждой функциональной группы. По мнению автора метрики наибольший вес, равный трем, имеет функциональная группа С, так как она влияет на поток управления программы. Весовые коэффициенты остальных групп распределяются следующим образом: a1=1; a2=2; a4=0.5. Весовой коэффициент группы T не равен нулю, поскольку “паразитные” переменные не увеличивают сложности потока данных программы, но иногда затрудняют ее понимание. С учетом весовых коэффициентов выражение примет вид:

Q = P + 2M + 3C + 0.5T.