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

17

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

    
задан viaclectic 12.07.2010 в 22:33
источник

5 ответов

6

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

    
ответ дан Ivo Blöchliger 15.01.2013 в 11:41
  • , но он будет иметь фиксированную степень 3? –  andrew cooke 15.01.2013 в 12:36
  • У него не будет фиксированной степени 3, но она будет плоской. –  Ivo Blöchliger 23.01.2013 в 19:11
  • о, извините, вы правы - я думаю о двойном. –  andrew cooke 24.01.2013 в 01:52
3

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

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

    
ответ дан phkahler 19.01.2011 в 17:36
2

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

ответ дан Valentas 08.05.2013 в 10:23
2

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

Ссылка

    
ответ дан LuisZaman 03.04.2011 в 16:52
  • Кажется, этот алгоритм может генерировать графики, края которых пересекаются? Это не плоский граф. Например, если в круге данного радиуса есть 4 точки, все они будут соединяться друг с другом, а диагонали пересекаются, делая график непланарным. –  Sid Datta 29.11.2012 в 22:10
1

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

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

Удачи!

    
ответ дан Aryabhatta 12.07.2010 в 23:25
  • наверняка почти все случайные графы не являются плоскими? –  andrew cooke 15.01.2013 в 12:35