9. Потоковый граф и цикломатическая сложность программы. Примеры.

Для представления программы используется потоковый граф. Перечислим его особенности.

1. Граф строится отображением управляющей структуры программы. В ходе отображения закрывающие скобки условных операторов и операторов циклов (end if; end loop) рассматриваются как отдельные (фиктивные) операторы.

2. Узлы (вершины) потокового графа соответствуют линейным участкам программы, включают один или несколько операторов программы.

3. Дуги потокового графа отображают поток управления в программе (передачи управления между операторами). Дуга — это ориентированное ребро.

4. Различают операторные и предикатные узлы. Из операторного узла выходит одна дуга, а из предикатного — две дуги.

5. Предикатные узлы соответствуют простым условиям в программе. Составное условие программы отображается в несколько предикатных узлов. Составным называют условие, в котором используется одна или несколько булевых опера­ций (OR, AND).

Например, фрагмент программы

if a OR b

then x

else у

end if;

вместо прямого отображения в потоковый граф вида, показанного на рис. 5.3, отображается в преобразованный потоковый граф (рис. 5.4).

Рис. 5.3. Прямое отображение в потоковый граф

Нет

Да

Нет

Рис. 5.4. Преобразованный потоковый граф

6. Замкнутые области, образованные дугами и узлами, называют регионами.

6. Окружающая граф среда рассматривается как дополнительный регион. Например, показанный здесь граф имеет три региона — Rl, R2, R3.

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

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

• количество независимых путей в базовом множестве программы;

• верхнюю оценку количества тестов, которое гарантирует однократное выполнение всех операторов.

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

Путь начинается в начальном узле, а заканчивается в конечном узле графа. Независи­мые пути формируются в порядке от самого короткого к самому длинному. Каждый новый путь включает новую дугу.

Все независимые пути графа образуют базовое множество.

Свойства базового множества:

1) тесты, обеспечивающие его проверку, гарантируют:

- однократное выполнение каждого оператора;

- выполнение каждого условия по True-ветви и по False-ветви;

2) мощность базового множества равна цикломатической сложности потокового графа.

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

Цикломатическая сложность вычисляется одним из трех способов:

1. цикломатическая сложность равна количеству регионов потокового графа;

2. цикломатическая сложность определяется по формуле: V(G)=E-N+2, где Е — количество дуг, N — количество узлов потокового графа;

3. цикломатическая сложность формируется по выражению V(G) = р + 1, где р — количество предикатных узлов в потоковом графе G.

Вычислим цикломатическую сложность графа из примера каждым из трех спо­собов:

1. потоковый граф имеет 3 региона;

2. V(G) = 7 дуг - 6 узлов + 2 = 3;

3. V(G) = 2 предикатных узла +1= 3.