Программа распознавания единичного или интервального графа, Подпрограмма изменения последовательности вершин графа - Алгоритмы нескольких махов

Программа реализует алгоритм четырех махов. Входным параметром является имя файла. На выходе печать: является ли граф единичным интервальным, интервальным или не интервальным, а также время работы алгоритма и программы. На Рис.17, Рис.18 и Рис.19 показаны все три варианта.

Рис.17

Рис.18

Рис.19

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

Подпрограмма изменения последовательности вершин графа

На этапе отладки алгоритма четырех махов возникла следующая проблема: результат расчета мог зависеть от входной последовательности вершин графа. Если изначально вершины расположены в нужном порядке, то распознавание интервального графа выполняется успешно, если вершины перемешаны, то результат был нестабилен. Перемешивание вершин случайным образом выполняется при задании графов. Для отладки кода была реализована отдельная подпрограмма, которая сохраняя структуру ребер графа, перемешивает вершины графа в памяти программы. Это позволило быстро выполнять тестирование кода на одном и том же графе, но с разной последовательностью вершин и отладить алгоритм LBFS*. Результаты, полученные с помощью данного алгоритма, приведены в разделе 4.1.

Похожие статьи




Программа распознавания единичного или интервального графа, Подпрограмма изменения последовательности вершин графа - Алгоритмы нескольких махов

Предыдущая | Следующая