Генерация большого случайного плоского графа

Question

Каков наиболее эффективный способ генерации большого (~ 300k вершин) случайного плоского графа («случайный» здесь означает равномерно распределенный)?

Answer 1

Другая возможность состоит в случайном выборе координат, а затем в вычислении триангуляции Делоне, которая является плоским графом (и также хорошо выглядит). См. http://en.wikipedia.org/wiki/Delaunay_triangulation Для вычисления такой триангуляции существуют алгоритмы O (n log (n)).

Answer 2

Вы смотрели на выборку Больцмана? См. Статью Эрика Фуси «Равномерная случайная выборка плоских графов за линейное время». Документ и реализация доступны на его домашней странице , которая, как говорится в документе, может создать экземпляры размером 100 КБ за несколько секунд.

Answer 3

Без каких-либо других требований, я бы сказал, посмотрите случайное поколение лабиринтов. Если вы хотите, чтобы на графике были циклы, удалите несколько случайных стен из простого лабиринта. Пересечения в лабиринте становятся узлами на вашем графике, а удаленные стены - ребрами. Это означает, что вы можете выбрать количество узлов, выбрав размер лабиринта.

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

Answer 4

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

https://github.com/briandconnelly/seeds/blob/master/seeds/plugins/topology/CartesianTopology.py

Answer 5

Ну, один из методов - попытаться сгенерировать случайный граф, который удовлетворяет ограничениям, подобным планарному графу (например, ребра <= 3 * вершин - 6), и проверить, является ли он плоским за O (n) время, используя Тарьянаалгоритм проверки на плоскостность.Если оно не плоское, генерируйте снова.Не уверен, насколько эффективно это будет для вершин 300K !, хотя (или если это даже даст вам графы с одинаковой вероятностью). </p>

Существует некоторая литература по созданию плоских графов, я мог бы найти одну статью здесь: Создание помеченных плоских графиков , которые, очевидно, ожидали O (n ^ 4) времени работы, и, возможно, также не стоили бы этого.Возможно, ссылки там помогут вам отыскать что-то, что может вам помочь.

Удачи!