ПРИМЕЧАНИЕ. Путь начинается в начальном узле, а заканчивается в конечном узле графа

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

Перечислим независимые пути для потокового графа из примера 1:

Путь 1: 1-8.

Путь 2: 1-2-3-7а-7b-1-8.

Путь 3: 1-2-4-5-7а-7b-1-8.

Путь 4: 1-2-4-6-7а-7b-1-8.

Заметим, что каждый новый путь включает новую дугу.

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

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

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

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

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

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

Значение 2-го свойства трудно переоценить — оно дает априорную оценку количества независимых путей, которое имеет смысл искать в графе.

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

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

2) цикломатическая сложность определяется по формуле

V(G)-E-N+2,

где Е — количество дуг, N — количество узлов потокового графа;

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

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

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

2) V(G) = 11 дуг - 9 узлов + 2 = 4;

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

Таким образом, цикломатическая сложность потокового графа из примера 1 равна четырем.