Материал: Алгоритм распознавания единичного интервального графа

Следует отметить, что проверка на UI порядок также требует обхода всех вершин и ребер графа и, как показали расчеты, занимает процессорное время сравнимое с этапами LBFS. То есть данный алгоритм условно можно назвать «четырехмаховым».

Рис.9 - Пример единичного интервального графа

Для единичного интервального графа, показанного на Рис.9 необходимы три прохода для получения UI порядка:

σ = c [b d] a e

σ+ = e d [b c] a

σ++ = a b c d e

Если на третьем проходе использовать алгоритм LBFS, то получим: a b [c d] e. Необходим произвольный выбор из вершин c и d. Но при использовании алгоритма LBFS+ вершины c и d отсортированы на втором этапе в порядке σ+. И хотя на втором этапе присутствует случайная выборка между вершинами b и c, это никак не влияет на получаемый в итоге результат: вершины b и c выбираются в нужной последовательности на третьем этапе.

В трехмаховом алгоритме возможно использование алгоритма MNS и MNS+ [7], вместо LBFS и LBFS+.

2.6    Алгоритм LBFS*

Алгоритма LBFS+ достаточно для трехмахового алгоритма распознавания единичных интервальных графов, но для случая интервальных графов необходимы дополнительные алгоритмы. Одним из таких алгоритмов является алгоритм LBFS* [6]. В нем на этапе выборки из множества вершин с наибольшими лексикографическими метками используются дополнительные параметры, сосчитанные по предыдущему этапу LBFS. Пусть  граф с  вершинами и порядок (последовательность) вершин . Обозначим  множество (закрытое множество соседей вершины  минус вершина ) и  пустое множество. Обозначим число  как .

Пусть  множество вершин с лексикографически наибольшим номером.

Пусть  и

пусть  некоторая вершина  такая что

Необходимая вершина выбирается следующим образом:  когда  иначе  когда  и  когда

2.7    Алгоритм "четырех махов" для распознавания единичных интервальных и интервальных графов

Этапы алгоритма [6]:

1.       δ ←LBFS

2.       σ ←LBFS+(δ)

3.       Расчет  и  для всех вершин

4.       ρ ←LBFS*(σ)

.        τ ←LBFS+(ρ)

6.       если τ является UI порядком, то граф единичный интервальный;

.        если τ является I порядком, то граф интервальный, иначе «граф не интервальный».

Следует отметить, что в данном алгоритме на каждом из 6 этапов выполняется полный обход вершин и ребер графа, то есть условно данный алгоритм «шестимаховый».

3.      Программные модули проекта

Все программы были реализованы на языке С++ на персональной ЭВМ с операционной системой Windows. Каждая программа представляет собой консольное приложение, которому в виде параметров командной строки можно передать необходимые для работы данные. Общий объем всех кодов с комментариями более 2500 строк и около 100 кбайт.

3.1    Представление графа в памяти ЭВМ

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

Таблица 1 - значения элементов массива ig представляющего граф в памяти ЭВМ

Размерность массива составляет число вершин графа плюс удвоенное число ребер плюс два.

Для поиска соседей вершины i (1 <= i <= N) используется цикл for (j=ig[i]; j<ig[i+1]; j++) и номера соседей ig[j].

Число соседей вершины i (1 <= i <= N) составляет ig[i+1]-ig[i].

Реализованная структура хранения позволяет быстро записать и считать данные из файла на жестком диске как в двоичном, так и в текстовом виде.

3.2    Программа задания единичного интервального графа

Для проведения тестов была написана программа задания единичного интервального графа. Входные параметры: число вершин, длина отрезка на котором задается граф, имя файла для записи результатов (Рис.10, Рис.11). Если имя файла имеет расширение bin, то записывается двоичный файл, иначе текстовый, что удобно для визуального контроля и отладки.

Рис.10

Рис.11

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

Изменяя длину отрезка графа можно для заданного числа вершин изменять число ребер графа.

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

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

Программа задания интервального графа была реализована по аналогии с программой задания единичного интервального графа. Изменения коснулись алгоритмов задания связей графа с помощью I-порядка. Для каждой вершины случайно задается число соседей вверх, например, для вершины j число r, 0 <= r <= N-j. Считаем, что вершина связана ребрами с вершинами j+1, j+2, ... , j+r. Для вершины возможны соседи и с меньшими номерами - соответствующие ребра задаются для вершин с меньшими номерами. Таким образом, интервальный граф задается с помощью всего одного массива целых чисел размерностью N. Сразу известно число ребер графа V - это сумма всех элементов массива. Для того, чтобы преобразовать эти данные о связности интервального графа в виде представленный в таблице 1, необходим временный массив размерностью 4*V для хранения списков ребер, так как мы не знаем заранее, сколько ребер у каждой вершины. При формировании временного массива легко выполняются проверки на связность графа - может оказаться так, что никакие из вершин с меньшими номерами не связаны ребрами с рассматриваемой вершиной (и значит со всеми остальными). Так как перебор вершин и формирование их ребер осуществляется последовательно снизу вверх, то если у рассматриваемой вершины кроме первой в списках нет ребер, то имеет место несвязность графа. Граф легко сделать связным, если соединить ребром рассматриваемую вершину с предыдущей. После этого данные из временного массива можно записать в необходимом формате таблицы 1, также как для единичного интервального графа выполнить перемешивание номеров вершин, и записать результат в текстовом или двоичном виде в выходной файл.

Входные параметры программы задания интервального графа: число вершин, параметр Лямбда (Число ребер / Число вершин), имя файла для записи результатов.

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

Пример работы программы показан на Рис.12

Рис.12

3.4    Программа задания случайных графов Эрдёша - Реньи

Программа реализует алгоритм задания случайных графов Эрдёша - Реньи. В качестве входных параметров задаются число вершин и число ребер. Вершины ребер выбираются случайным образом. Используются списки ребер, как в программе задания интервальных графов. Для связности графа при необходимости добавляются дополнительные ребра. Для этого используется рекурсивный алгоритм закраски вершин графа. Как показали тестовые расчеты, такой алгоритм дает хорошие результаты для графов с большим числом вершин, но небольшим соотношением Число Ребер / Число Вершин. Если это соотношение увеличивается, то время работы программы сильно растет из-за необходимости проверок на уже наличие в графе нового случайного ребра: при этом идет перебор всех соседей одной из вершин. Для задания графов с относительно небольшим числом вершин и большим числом ребер был разработан и реализован другой алгоритм задания графов Эрдёша-Реньи. Так как число вершин невелико, то связность такого графа можно задавать с помощью матрицы связности, где для каждого возможного ребра есть отдельный элемент матрицы. Кроме того, если задаваемое число ребер превышает половину максимального числа ребер графа, то эффективнее задавать случайным образом отсутствующие ребра. Из полученной матрицы связности далее формируются списки ребер, выполняется проверка на связность и формирование нужных текстовых или двоичных файлов так же, как и в первом варианте алгоритма. Два реализованных алгоритма позволили задавать случайные графы Эрдёша-Реньи с любым числом вершин и ребер, ограниченным только оперативной памятью ЭВМ.

3.5    Программа добавления/удаления ребер графа

Входные параметры: входной файл, выходной файл, номер вершины, номер вершины.

Если задаваемые номера вершин положительные, то добавляется соответствующее ребро, иначе удаляется. На Рис.13 Рис.14 показаны оба варианта соответственно.

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

Рис.13

Рис.14

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

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

Рис.15

Рис.16

Первоначальный вариант программы реализовывал алгоритмы MNS и MNS+ (обозначим, как MNS3). После реализации алгоритма LBFS и алгоритма четырех махов стало возможным легко и быстро реализовать алгоритм трех махов с использованием LBFS и LBFS+ (обозначим, как LBFS3). Ниже приводится сравнение быстродействия этих алгоритмов.

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

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

Рис.17

Рис.18

Рис.19

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

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

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

4.      Результаты численных экспериментов

Численные эксперименты были проведены для следующих целей:

·        Подтверждение корректности алгоритмов.

·        Подтверждение линейности временных затрат алгоритмов.

В расчетах были использованы три алгоритма:

·        Алгоритм четырех махов (обозначим, как LBFS4, раздел 2.7);

·        Алгоритм трех махов LBFS3 (раздел 2.5);

·        Алгоритм трех махов MNS3 (раздел 2.5).