Тестирование софта - статьи


Обход полного графа и его модификаций - часть 2


D(KM(KN))=M × D(KN) + D(KM).

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

Оценка длины обхода графа KM KN снизу также равна количеству его дуг
E(KM × KN) = M × E(KN) + N × E(KM) = M × N × (N + M - 2).

Графdfsm, длинаdfsm, времяndfsm, длинаndfsm, времямин. длина
KK51 269265 62 8108 1 7956
KK51 804614 186 14024 5 13770
KK51 1694413 406 20348 5 19992
KK53 301095 68 8744 2 8576
KK53 898884 216 15104 4 14840
KK53 1890675 302 21888 5 21520
KK55 335337 50 9404 2 9240
KK55 1000234 164 16224 3 15950
KK55 2101501 365 23484 5 23100

Таблица 5. Длина и время обходов графов KM KN.

Теперь длина обхода с помощью dfsm уже не может быть определена с помощью аналогичной формулы.

Приведенные таблицы показывают, что на многих графах обходчик ndfsm работает эффективнее dfsm, и, если проверка детерминизма графа не является необходимым элементом тестирования, предпочтительнее использовать первый обходчик.

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


Начало  Назад  Вперед