Генератор псевдо-случайных UDG-графов с наперед заданными свойствами

Назначение - генерация псевдо-случайных Unit Disk Graphs (UDG-графов)
Область применения - моделирование сенсорных и Mesh сетей

Используемый алгоритм:

Граф G=(V,E) называется UDG-графом (unit disk graph), если ребро (u,v)  существует тогда и только тогда, когда расстояние между вершинами u и v меньше либо равно 1 (в общем случае - d).Программа генерирует на заданной области случайные UDG-графы с наперед заданными свойствами (связность, ограничение на степень вершин, ограничение на количество хопов).

Реализованы три способа генерации UDG-графов::

1. Традиционный алгоритм (случайный выбор точек в заданной области и проверка заданных свойств)
2. Алгоритм C-Crug (используются полярные координаты для выбора каждой следующей вершины [1])
3. Алгоритм Lattice (строится дополнительная сетка в заданной области, которая используется для выбора каждой следующей вершины. Использование распределения Пуассона при выборе ячеек сетки) [2]. Осуществляется сбор статистики по распределению степеней для серии сгенерированных графов.

Функциональные возможности - Во вложении приведена таблица времени генерации UDG-графов в зависимости от количества вершин и способа генерации.
Инструментальные средства создания - Lazarus.

[1] Furuzan Atay Onat, Ivan Stojmenovic, Halim Yanikomeroglu Generating random graphs for the simulation of wireless ad hoc, actuator, sensor, and internet networks. Pervasive and Mobile Computing, 4:597-615, 2008.

[2] Шахов В.В., Соколова О.Д., Юргенсон А.Н. "Эффективный метод для генерации псевдо-случайных UDG-графов" // Труды конференции «Информационные технологии и системы — 2013», Светлогорск, ISBN 978-5-901158-23-4, стр. 411-414.