Genera un gran gráfico plano aleatorio

Question

¿Cuál es la forma más eficiente de generar un gráfico planar aleatorio grande (~ 300k vértices) ("aleatorio" aquí significa distribución uniforme)?

Answer 1

Bien, un método sería intentar generar un gráfico aleatorio que satisfaga restricciones similares como un gráfico plano (por ejemplo, bordes < = 3 * vértices - 6) y verificar si es plano en el tiempo O (n) usando Algoritmo de prueba de planitud de Tarjan. Si no es plano, genera de nuevo. Sin embargo, no estoy seguro de cuán eficiente sería esto para 300,000 vértices (o si incluso le dará gráficos con probabilidad uniforme).

Hay algo de literatura en la generación de gráficos planos, podría encontrar un documento aquí: Generating Labeled Planar Graphs que aparentemente ha esperado O (n^4) tiempo de ejecución, y no valdría la pena tampoco. Tal vez las referencias allí le ayudarán a encontrar algo que podría ayudar.

¡Buena suerte!

Answer 2

Sin ningún otro requisito, yo diría buscar generación laberinto al azar. Si desea ciclos en el gráfico, elimine algunas paredes al azar de un simple laberinto. Las intersecciones en el laberinto se convierten en los nodos en su gráfico y las paredes eliminadas son los bordes. Eso significa que puede seleccionar la cantidad de nodos eligiendo el tamaño del laberinto.

Los laberintos normalmente se realizan en una cuadrícula 2d con un máximo de 4 conexiones de un punto a otro, pero no hay nada que te impida hacer un laberinto en mosaicos hexagonales, o algo más.

Answer 3

Si por uniformidad te refieres uniformemente distribuido en el espacio, entonces este es un algoritmo bastante rápido que desarrollé para generar gráficos planos para un simulador espacial ecológico/evolutivo. Generará gráficos planar aleatorios con un grado esperado que especifique, por supuesto con alguna variación a su alrededor. Puede ampliarlo para elegir el grado esperado en función de un número aleatorio uniforme si, en cambio, desea grados aleatorios uniformes en su gráfica plana.

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

Answer 4

Otra posibilidad consiste en elegir al azar coordenadas y luego calcular una triangulación de Delaunay, que es un gráfico planar (y se ve bien también). Ver http://en.wikipedia.org/wiki/Delaunay_triangulation Hay algoritmos O (n log (n)) para calcular dicha triangulación.

Answer 5

¿Has mirado el muestreo de Boltzmann? Ver el artículo de Eric Fusy "Muestreo aleatorio uniforme de gráficos planos en tiempo lineal". El documento y la implementación están disponibles en su homepage, que según el documento puede generar instancias de tamaño 100K en unos pocos segundos.