Сформировать большой случайный плоский граф

Ответ 1

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

Ответ 2

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

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

Ответ 3

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

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

Ответ 4

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

Ответ 5

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

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

Удачи!