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

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

Рис.10

Рис.11

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

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

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

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

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

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

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

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

Рис.12

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




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

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