Estoy buscando una fuente de grandes conjuntos de datos para probar la implementación de algoritmos gráficos. Proporcione también información sobre el tipo / distribución (por ejemplo, dirigida / no dirigida, simple / no simple, ponderada / no ponderada) de los gráficos en la fuente si se conocen.
36
Respuestas:
Consulte los siguientes enlaces para instancias de gráficos
Gráficos DIMACS: instancias de referencia y mejor foo de los límites superiores
Instancias para colorear gráficos
Instancias de referencia de CLIQUE
fuente
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:
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 .H pags H
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.norte Kn / 2 , n / 2
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.
fuente
Para generar gráficos, generalmente uso el
geng
programa que viene connauty
: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
directg
cual 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
n
vértices, o todos los gráficos conectados conm
bordes o algo así. Si tiene requisitos más específicos, indíquelos en su pregunta.fuente
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.
fuente
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}
fuente
El paquete Igraph tiene diferentes tipos de generador de gráficos, incluidos gráficos aleatorios y gráficos estructurados.
http://igraph.sourceforge.net/doc/html/igraph-Generators.html
fuente
Hay un nuevo proyecto interesante y prometedor basado en la comunidad para una base de datos gráfica:
Introducción de papel
The Open Graph Archive: un esfuerzo impulsado por la comunidad
o el enlace directo
Graph-Archive.org
El tiempo mostrará si es un buen lugar para las instancias de prueba.
fuente
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.
fuente
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.
fuente