Estou procurando uma fonte de enormes conjuntos de dados para testar alguma implementação do algoritmo gráfico. Forneça também algumas informações sobre o tipo / distribuição (por exemplo, direcionado / não direcionado, simples / não simples, ponderado / não ponderado) dos gráficos na fonte, se forem conhecidos.
36
Respostas:
Verifique os seguintes links para instâncias de gráfico
DIMACS gráficos: instâncias de benchmark e Melhor superior Bounds foo
Instâncias de coloração de gráfico
Instâncias de benchmark CLIQUE
fonte
Vou tentar dar uma resposta de mais alto nível do que as outras.
As seguintes classes de entradas são frequentemente úteis para testar o desempenho de um algoritmo proposto ou a validade de uma conjectura na teoria dos grafos:
Gráficos aleatórios : para muitas propriedades de gráficos, os gráficos aleatórios são extremais em expectativa. Por exemplo, o número de vezes que um determinado gráfico bipartido completo ocorre quando um subgráfico é minimizado em um gráfico aleatório. (É uma bela conjectura de Erdős-Simonovits e Sidorenko que se é um gráfico bipartido, o gráfico aleatório com densidade de arestas p tem na expectativa assintoticamente o número mínimo de cópias de H em todos os gráficos da mesma ordem e densidade de arestas.) As distribuições especificadas através de gráficos aleatórios são a fonte de muitos limites inferiores para algoritmos de gráficos aleatórios, através do princípio minimax de YaoH p H .
Gráficos estruturados : Esta é uma designação aproximada para uma classe de gráficos que são de alguma forma especialmente estruturados para o problema em questão. Por exemplo, o teorema de Turán diz que o gráfico mais denso em vértices que não possui triângulo é o gráfico bipartido completo K n / 2 , n / 2 ; este gráfico é claramente construído especialmente para evitar triângulos.n Kn / 2 , n / 2
Gráficos "não aleatórios" : são intermediários entre serem completamente genéricos, como em gráficos aleatórios, e completamente específicos para o problema, como em gráficos estruturados. Por exemplo, essa família pode ser subgráficos aleatórios de gráficos estruturados. Tais exemplos surgem frequentemente na criação de variantes mais fortes do lema da regularidade de Szemerédi . Uma maneira de produzir esses exemplos é chegar a uma definição de "pseudo-aleatoriedade" que modela entradas aleatórias, para que, para entradas pseudo-aleatórias, você possa mostrar que seu algoritmo ou sua conjectura funcionam. Em seguida, você identifica obstruções à pseudo-aleatoriedade e os gráficos que possuem essas obstruções podem produzir uma grande coleção de gráficos não aleatórios que são contra-exemplos. Uma discussão mais envolvida desse princípio pode ser encontrada emPalestra de Terry Tao no ICM em 2006 . Esses gráficos não aleatórios correspondem aproximadamente às "nil subsequências" em alguns de seus trabalhos com Ben Green e outros.
fonte
Para gerar gráficos, eu costumo usar o
geng
programa que acompanhanauty
:http://cs.anu.edu.au/~bdm/nauty/
Isso produz gráficos não direcionados (também conhecidos como "gráficos"). Para produzir gráficos direcionados, você pode canalizar a saída através da
directg
qual também é fornecido com nauty.O uso do geng é adequado para cenários em que você deseja testar todos os gráficos em (digamos) até
n
vértices, ou todos os gráficos conectados comm
arestas ou algo parecido. Se você tiver requisitos mais específicos, indique-os na sua pergunta.fonte
O Stanford GraphBase pode ser útil para você: http://www-cs-staff.stanford.edu/~knuth/sgb.html
Com toda a probabilidade, no entanto, você provavelmente desejará gerar os gráficos por conta própria e provavelmente os gráficos gerados terão todas (ou não possuir) certas propriedades. Gráficos aleatórios geralmente são uma aproximação ruim dos gráficos nos quais um algoritmo realmente é usado.
fonte
Não é enorme, mas talvez ainda útil, 3054 "gráficos nomeados padrão" da coleção GraphData do Mathematica
O formato é um gráfico por linha, com nome e lista de nós adjacentes como este
{<nome do gráfico>, {{1, 4}, {1, 5}, {1, 6}, {2, 5}, {2, 6}, {3, 6}}
<nome do gráfico> lata no formato "AGraph" ou {"Andrasfai", 6}
fonte
O pacote Igraph possui diferentes tipos de gerador de gráficos, incluindo gráficos aleatórios e gráficos estruturados.
http://igraph.sourceforge.net/doc/html/igraph-Generators.html
fonte
Há um novo projeto interessante e promissor baseado na comunidade para um banco de dados de gráficos:
Apresentando o artigo
The Open Graph Archive: um esforço impulsionado pela comunidade
ou o link direto
Graph-Archive.org
O tempo mostrará se é um bom lugar para as instâncias de teste.
fonte
O 9º Desafio de Implementação do DIMACS - Caminhos Mais Curtos foi realizado em 2005-2006, com o objetivo de produzir "um conjunto padrão de instâncias e geradores de benchmark, bem como implementações de benchmark de algoritmos de caminho mais curto conhecidos".
A página de download contém gráficos compactados da rede rodoviária nos EUA, que variam de 2 MB a 335 MB com distâncias e tempo.
http://www.dis.uniroma1.it/challenge9/download.shtml
Achei isso útil para comparar minhas próprias implementações de brinquedo de funções gráficas.
fonte
Você pode usar o Mosqueteiro, consulte
https://people.cs.clemson.edu/~isafro/musketeer/index.html
Este é um gerador de gráficos em várias escalas que aceita algum gráfico de entrada e gera outro gráfico que pode ser arbitrariamente semelhante ao original. Os parâmetros são flexíveis o suficiente para gerar uma nova estrutura em diferentes resoluções de granulação grossa. Veja exemplos na galeria. Este pacote é perfeito para criar instâncias experimentais para algoritmos de verificação e benchmarking.
fonte