2015-05-06
1409
Критерий 1. По этому критерию граф программы по управлению должен быть покрыт минимальным набором путей, проходящих через каждый оператор ветвления по каждой дуге. Повторная проверка дуг не оценивается и считается избыточной. При этом в процессе проверки гарантируется выполнение всех передач управления между операторами программы и каждого оператора не менее одного раза.
Поток управления – последовательность выполнения различных модулей и операторов программы.
Граф потока управления – ориентированный граф, моделирующий поток управления программы.
В настоящее время разработаны алгоритмы, позволяющие автоматизировать процесс получения минимального множества маршрутов по этому критерию.
Рассмотрим структурную сложность типичной программы управления, содержащей 100 – 200 команд, граф потока управления которой, представленный на рис.3, содержит 14 вершин, 20 дуг и 3 цикла.
Для полной проверки этой программы по первому критерию достаточно следующих четырех маршрутов:
|
|
|
M1: 1 – 2 – 14
M2: 1 – 3 – 4 – 6 – 8 – 6 – 8 – 14
M3: 1 – 3 – 5 – 7 – 9 – 10 – 11 – 12 – 13 – 14
M4: 1 – 3 – 4 – 5 – 7 – 9 – 10 – 9 – 10 – 11 – 7 – 9 – 10 – 11 – 12 – 14
 |
Рис.3
Структурная сложность программы по первому критерию вычисляется следующим образом:
m
S = S pi ,
i =1
гдеpi – количество вершин ветвления в i - том маршруте без учета последней вершины
m1: 1 - 2 - 14 = 1
m2: 1 - 3 - 4 - 6 - 8 - 6 - 8 - 14 = 5
m3: 1 - 3 - 5 - 7 - 9 - 10 - 11 - 12 - 13 - 14 = 5
m4: 1 - 3 - 4 - 5 - 7 -9 - 10 - 9 - 10 - 11 - 7 - 9 - 10 - 11 - 12 - 14 = 9
Таким образом, сложность программы, представленной графом на рис.3, составляет некоторую метрику в 20 единиц.
Недостаток первого критерия: не учитывается комбинаторика сочетания условий на разных участках маршрутов (например, при сочетаниях ветвлений в вершинах 3 и 12).
Критерий 2. Основан на анализе базовых маршрутов в программе, формируемых и оцениваемых на основе цикломатического числа графа потока управления программы (см. работы Т.МcCabe и В.В.Липаева).
Цикломатическое число Z исходного графа программы определяется формулой
Z = Y - N +2*W,
где Y – общее число дуг в графе;
N – общее число вершин в графе;
W – число связных компонент графа.
Число связных компонент графа W равно количеству дуг, необходимых для превращения исходного графа в максимально связный граф.
Максимально связным графом называется граф, у которого любая вершина доступна из любой другой вершины.
Максимально связный граф получается из исходного графа путем замыкания конечных и начальной вершин. Для большинства корректных (не содержащих висячих и тупиковых вершин) графов достаточно одной замыкающей дуги.
|
|
|
Для рассматриваемого графа максимально связанный граф получается путем добавления дуги (14, 1)
Z = Y - N + 2´P = 20 - 14 + 2´1 = 8
Второй критерий (выбранный по цикломатическому числу) требует однократной проверки или тестирования каждого линейно-независимого цикла и каждого линейно-независимого ациклического участка программы. Каждый линейно-независимый ациклический маршрут или цикл отличается от всех остальных хотя бы одной вершиной или дугой, т.е. его структура не можетбыть полностью образована компонентами других маршрутов.
При использовании второго критерия количество проверяемых маршрутовравно цикломатическому числу.
M1: 6 – 8
m2: 9 – 10 Линейно-независимые циклические маршруты
m3: 7 – 9 – 10 – 11
m4: 1 – 2 – 14 Линейно-
