Datos para probar algoritmos gráficos

Respuestas:

17

Trataré de dar una respuesta de más alto nivel que las otras.

Las siguientes clases de entradas a menudo son útiles para probar el rendimiento de un algoritmo propuesto o la validez de una conjetura en la teoría de grafos:

  1. Gráficos aleatorios : para muchas propiedades de gráficos, los gráficos aleatorios tienen una expectativa extrema. Por ejemplo, el número de veces que se produce un gráfico bipartito completo dado que un subgrafo se minimiza en un gráfico aleatorio. (Es una hermosa conjetura de Erdős-Simonovits y Sidorenko que si es un gráfico bipartito, entonces el gráfico aleatorio con densidad de borde p tiene en espera asintóticamente el número mínimo de copias de H sobre todos los gráficos del mismo orden y densidad de borde). Las distribuciones especificadas a través de gráficos aleatorios son la fuente de muchos límites inferiores para algoritmos de gráficos aleatorios, a través del principio minimax de Yao . HpagsH

  2. Gráficos estructurados : esta es una designación aproximada para una clase de gráficos que de alguna manera están especialmente estructurados para el problema en cuestión. Por ejemplo, el teorema de Turán dice que el gráfico más denso en vértices que está libre de triángulos es el gráfico bipartito completo K n / 2 , n / 2 ; Este gráfico está claramente construido especialmente para evitar triángulos.norteKnorte/ /2,norte/ /2

  3. Gráficos "no aleatorios" : son intermedios entre ser completamente genéricos, como en los gráficos aleatorios, y completamente específicos del problema, como en los gráficos estructurados. Por ejemplo, una familia así podría ser subgrafías aleatorias de gráficos estructurados. Tales ejemplos surgen a menudo al crear variantes más fuertes del lema de regularidad de Szemerédi . Una forma de producir estos ejemplos es proponer una definición de "pseudoaleatoriedad" que modele entradas aleatorias, de modo que para las entradas pseudoaleatorias, pueda mostrar que su algoritmo o su conjetura funcionan. Luego, identifica las obstrucciones a la pseudoaleatoriedad, y los gráficos que tienen estas obstrucciones pueden producir una gran colección de gráficos no aleatorios que son contraejemplos. Una discusión más complicada de este principio se puede encontrar enCharla ICM de Terry Tao en 2006 . Estos gráficos no aleatorios corresponden aproximadamente a las "secuencias nulas" en algunos de sus trabajos con Ben Green y otros.

arnab
fuente
14

Para generar gráficos, generalmente uso el gengprograma que viene con nauty:

http://cs.anu.edu.au/~bdm/nauty/

Esto produce gráficos no dirigidos (también conocidos como "gráficos"). Para producir gráficos dirigidos, puede canalizar la salida a través de la directgcual también viene con nauty.

El uso de geng es adecuado para escenarios en los que desea probar todos los gráficos en (por ejemplo) hasta los nvértices, o todos los gráficos conectados con mbordes o algo así. Si tiene requisitos más específicos, indíquelos en su pregunta.

Emil
fuente
11

Stanford GraphBase puede ser de ayuda para usted: http://www-cs-staff.stanford.edu/~knuth/sgb.html

Sin embargo, con toda probabilidad, es probable que desee generar los gráficos usted mismo, y probablemente querrá que todos los gráficos generados tengan (o no tengan) ciertas propiedades. Los gráficos aleatorios son a menudo una aproximación pobre de los gráficos en los que un algoritmo realmente se utiliza.

Peter Boothe
fuente
9

No es enorme, pero puede ser útil, 3054 "gráficos con nombre estándar" de la colección GraphData de Mathematica

El formato es un gráfico por línea, con el nombre y la lista de nodos adyacentes como este

{<nombre del gráfico>, {{1, 4}, {1, 5}, {1, 6}, {2, 5}, {2, 6}, {3, 6}}

<nombre del gráfico> lata de la forma "AGraph" o {"Andrasfai", 6}

Yaroslav Bulatov
fuente
¿Son estos gráficos o gráficos dirigidos?
Emil
3

El noveno desafío de implementación de DIMACS: las rutas más cortas se ejecutó en 2005-2006 con el objetivo de producir "un conjunto estándar de instancias y generadores de referencia, así como implementaciones de referencia de algoritmos de ruta más corta conocidos".

La página de descarga contiene gráficos de red de carreteras de EE. UU. Comprimidos que varían de 2 MB a 335 MB con pesos de distancia y tiempo.

http://www.dis.uniroma1.it/challenge9/download.shtml

Encontré esto útil para comparar mis propias implementaciones de juguete de funciones gráficas.

infogulch
fuente
0

Puedes usar Mosquetero, mira

https://people.cs.clemson.edu/~isafro/musketeer/index.html

Este es un generador de gráficos multiescala que acepta algunos gráficos de entrada y genera otro gráfico que puede ser arbitrariamente similar al original. Los parámetros son lo suficientemente flexibles como para generar una nueva estructura con diferentes resoluciones de grano grueso. Ver ejemplos en la galería. Este paquete es perfecto para crear instancias experimentales para algoritmos de verificación y evaluación comparativa.

Ilya Safro
fuente