Создание большого случайного планарного графика

Question

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

Answer 1

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

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

Удачи вам!

Answer 2

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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