algorithm - resueltos - teoria de grafos
Generar un grafo plano al azar grande (5)
¿Cuál es la manera más eficiente de generar un gráfico planar aleatorio grande (~ 300k vértices) ("aleatorio" significa aquí distribuido uniformemente)?
¿Has mirado el muestreo de Boltzmann? Vea 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 100 K en pocos segundos.
Bueno, un método sería intentar generar un gráfico aleatorio que satisfaga restricciones similares a un gráfico planar (por ejemplo, bordes <= 3 * vértices - 6) y verificar si es planar en tiempo O (n) usando el algoritmo de prueba de planaridad de Tarjan . Si no es plano, vuelve a generar. Sin embargo, no estoy seguro de cuán eficiente sería esto para vértices de 300K (o si incluso te dará gráficos con probabilidad uniforme).
Hay algo de literatura sobre la generación de gráficos planares, podría encontrar un artículo aquí: Generar gráficos planos etiquetados que aparentemente ha esperado un tiempo de ejecución de O (n ^ 4), y puede que tampoco valga la pena. Tal vez las referencias allí le ayudarán a localizar algo que pueda ayudar.
¡Buena suerte!
Otra posibilidad consiste en elegir aleatoriamente las coordenadas y luego calcular una Triangulación de Delaunay, que es un gráfico plano (y también se ve bien). Consulte http://en.wikipedia.org/wiki/Delaunay_triangulation Hay algoritmos O (n log (n)) para calcular tal triangulación.
Si por uniforme te refieres a una distribución uniforme 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 planos aleatorios con el grado esperado que especifique, por supuesto, con algunas variaciones a su alrededor. Podría extenderlo para elegir el grado esperado en base a un número aleatorio uniforme si, en cambio, deseara grados aleatorios uniformes en su gráfico planar.
https://github.com/briandconnelly/seeds/blob/master/seeds/plugins/topology/CartesianTopology.py
Sin ningún otro requisito, diría que busca la generación aleatoria de laberintos. Si quieres ciclos en el gráfico, elimina algunas paredes al azar de un simple laberinto. Las intersecciones en el laberinto se convierten en los nodos de tu gráfica y las paredes eliminadas son los bordes. Eso significa que puede seleccionar el número 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 le impida hacer un laberinto en fichas hexagonales, o algo más.