Покрытие путей потока управления

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

, где имеет вид , при 1 ≤ i ≤ n . Упорядоченным подмножеством пути назовём последовательность такую, что . Заметим, что в упорядоченном подмножестве пути конечный оператор перехода может не совпадать с начальным оператором следующего за ним перехода.

Пусть есть два пути

и , и пусть

причём

и . Тогда пути и имеют общее упорядоченное подмножество размера m.

Обозначим через length(R) длину пути R, а через

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

Здесь path(t) - это путь, по которому приходит управление при выполнении теста t. Значение в правой части равно количеству переходов в путях R и path(t), не входящих в максимальное общее упорядоченное подмножество этих путей. Оно равно 0 тогда и только тогда, когда пути R и path(t) совпадают.

Содержание раздела

---

---