M5: 1 – 3 – 4 – 6 – 8 – 14 независимые

m6: 1 – 3 – 5 – 7 – 9 – 10 – 11 – 12 – 14ациклические

m7: 1 – 3 – 4 – 5 – 7 – 9 – 10 – 11 – 12 – 13 – 14маршруты

M8: 1 – 3 – 4 – 5 – 7 – 9 – 10 – 11 – 12 – 14

Определение структурной сложности по второму критерию:

m1: 6 - 8= 1

m2: 9 - 10= 1

m3: 7 - 9 - 10 – 11 = 2

m4: 1 - 2 – 14 = 1

m5: 1- 3 - 4 - 6 - 8 – 14 = 4

m6: 1 - 3 - 5 - 7 - 9 - 10 - 11 - 12 – 14 = 5

m7: 1 - 3 - 4 - 5 - 7 - 9 - 10 - 11 - 12 – 14 = 6

m8: 1 - 3 - 4 - 5 - 7 - 9 - 10 - 11 - 12 - 13 – 14 = 6

Для правильно структурированных программ (программ, которые не имеют циклов с несколькими выходами, не имеют переходов внутрь циклов или условных операторов и не имеют принудительных выходов из внутренней части циклов или условных операторов) цикломатическое число Z можно определить путем подсчета числа вершинn_в, в которых происходит ветвление. Тогда

Z = n_в +1

Для рассматриваемого примера Z = 7 + 1 = 8(ветвления имеют место ввершинах графа 1, 3, 4, 8, 10, 11, 12).

Исследования графов реальных программных модулей с достаточно большим фиксированным числом вершин показали, что:

· Суммарная сложность тестов почти не зависит от детальной структуры графа и в основном определяется числом предикатов – ветвлений графа;

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

В.В. Липаев показал, что для Z £ 10 модули корректно проверяемы и число ошибок в таких модулях будет минимальным. Приемлемыми значениями Z считаются 10 £ Z £30. При Z > 30 устранить ошибки в процессе тестирования практически невозможно.

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

Матрица смежности – это квадратная матрица, в которой 1 располагается в позиции (i, j),если в графе имеется дуга (i, j).

Для рассматриваемого графа программы матрица смежности имеет вид, показанный в табл.7.

Таблица 7

Матрицей достижимости называется квадратная матрица, в которой 1 располага-ется в позиции, соответствующей дуге (i, j). Для рассматриваемого графа программы матри-ца достижимости имеет вид, показанный в табл.8.

Таблица 8

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

С помощью матрицы достижимости можно сравнительно просто выделить циклы, отмечая диагональные элементы, равные 1, и идентичныестрок.

Для рассматриваемого примера одинаковыми являются строки 6и 8, которые имеют 1на диагонали, следовательно, вершины 6и 8образуют цикл. Аналогично можно выделить еще два маршрута с циклами, образованными вершинами 9и10 и 7, 9, 10и11 соответственно.

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

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

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

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

M1: 1 – 2 – 14

m2: 1– 3– 4– 6 – 8 – 14

M3: 1 – 3 – 5 – 7 – 9 – 10 – 11 – 12 – 14

M4: 1 – 3 – 4 – 5 – 7 – 9 – 10 – 11 – 12 – 14

M5: 1 – 3 – 5 – 7 – 9 – 10 – 11 – 12 – 13 – 14

m6: 1 – 3– 4 – 5 – 7 – 9 – 10 – 11 – 12 – 13 – 14

m7: 1 – 3– 4– 6 – 8– 6 – 8 – 14

m8: 1 – 3 – 5 – 7 – 9 – 10 – 9 – 10 – 11 – 7 – 9 – 10 – 11 – 12 – 14

m9: 1 – 3 – 4 – 5 – 7 – 9 – 10 – 9 – 10 – 11 – 7 – 9 – 10 – 11 – 12 – 14

m10: 1 – 3 – 5 – 7 – 9 – 10 – 9 – 10 – 11 – 7 – 9 – 10 – 11 – 12 – 13 – 14

m11: 1 – 3 – 4– 5 – 7 – 9 – 10 – 9 – 10 – 11 – 7 – 9 – 10 – 11 – 12 – 13 – 14

Определим структурную сложность заданной программы по третьему критерию:

m1: 1 - 2 - 14 = 1

m2: 1- 3-4 – 6 –8– 14 = 4

m3: 1 - 3 -5 - 7 - 9 - 10 - 11 - 12 - 14 = 5

m4: 1 - 3 - 4 - 5 - 7 - 9 - 10 - 11 - 12 – 14 = 6

m5: 1 - 3 - 5 - 7 - 9 - 10 - 11 - 12 - 13 - 14= 5

m6: 1 - 3 - 4 - 5 - 7 - 9 - 10 - 11 - 12 - 13 – 14 = 6

m7: 1-3-4- 6 -8- 6 -8- 14 = 5

m8: 1 - 3 - 5 - 7 - 9 - 10 - 9 - 10 - 11 - 7 - 9 - 10 - 11 - 12 – 14 = 8

m9: 1- 3- 4- 5 - 7 - 9 - 10 - 9 - 10 - 11 - 7 - 9 - 10 - 11 - 12 – 14 = 9

m10: 1- 3- 5 - 7 - 9 - 10 - 9 - 10 - 11 - 7 - 9 - 10 - 11 - 12 – 13 – 14 = 8

m11: 1- 3 - 4 - 5 - 7 - 9 - 10 - 9 - 10 - 11 - 7 - 9 - 10 - 11 - 12 – 13 – 14 = 9

S₂ = 1 + 4 + 5 + 6 + 5 + 6 + 5 + 8 + 9 + 8 + 9 = 66

Особенностью четырех последних маршрутов с циклами, так же как соответствующих им ациклических маршрутов, является полный переборсочетаний ветвлений в вершинах 3 и 12.