Daten zum Testen von Graph-Algorithmen

Ich suche nach einer Quelle mit riesigen Datenmengen, um die Implementierung eines Graph-Algorithmus zu testen. Bitte geben Sie auch einige Informationen über die Art / Verteilung (z. B. gerichtet / ungerichtet, einfach / nicht einfach, gewichtet / ungewichtet) der Diagramme in der Quelle an, sofern diese bekannt sind.

Überprüfen Sie die folgenden Links auf Diagramminstanzen

DIMACS-Diagramme: Benchmark-Instanzen und beste obere Schranken foo

Graph Coloring Instances

CLIQUE Benchmark-Instanzen

Ich werde versuchen, eine allgemeinere Antwort zu geben als die anderen.

Die folgenden Klassen von Eingaben sind häufig nützlich, um die Leistung eines vorgeschlagenen Algorithmus oder die Gültigkeit einer Vermutung in der Graphentheorie zu testen:

1. Zufällige Diagramme : Bei vielen Diagrammeigenschaften sind zufällige Diagramme extrem erwartungsgemäß. Beispielsweise wird die Häufigkeit, mit der ein gegebener vollständiger zweigliedriger Graph auftritt, wenn ein Teilgraph in einem Zufallsgraphen minimiert wird. (Es ist eine schöne Vermutung von Erdős-Simonovits und Sidorenko, dass, wenn ein zweigliedriger Graph ist, der Zufallsgraph mit der Kantendichte p erwartungsgemäß asymptotisch die minimale Anzahl von Kopien von H über alle Graphen derselben Ordnung und Kantendichte hat.) Verteilungen, die durch Zufallsgraphen spezifiziert werden, sind die Quelle vieler unterer Schranken für randomisierte Graphenalgorithmen nach dem Minimax-Prinzip von Yao . $H$$p$$H$

2. Strukturierte Diagramme : Dies ist eine grobe Bezeichnung für eine Klasse von Diagrammen, die irgendwie speziell für das jeweilige Problem strukturiert sind. Zum Beispiel sagt Turáns Theorem , dass der dichteste Graph auf Ecken, der frei von Dreiecken ist, der vollständige zweigeteilte Graph K n / 2 , n / 2 ist ; Dieses Diagramm wurde speziell entwickelt, um Dreiecke zu vermeiden.$n$$K_{n/2,n/2}$

3. "Nicht zufällige" Diagramme : Diese liegen zwischen der vollständigen Generierung wie bei zufälligen Diagrammen und der vollständigen Spezifizierung des Problems wie bei strukturierten Diagrammen. Zum Beispiel könnte eine solche Familie zufällige Untergraphen von strukturierten Graphen sein. Solche Beispiele tauchen häufig bei der Schaffung stärkerer Varianten von Szemerédis Regelmäßigkeits-Lemma auf . Eine Möglichkeit, diese Beispiele zu erstellen, besteht darin, eine Definition von "Pseudozufälligkeit" zu erstellen, die Zufallseingaben modelliert, sodass Sie für Pseudozufällige Eingaben zeigen können, dass Ihr Algorithmus oder Ihre Vermutung funktioniert. Dann identifizieren Sie Hindernisse für die Pseudozufälligkeit, und Diagramme, die diese Hindernisse aufweisen, können dann eine große Sammlung nicht zufälliger Diagramme erzeugen, die Gegenbeispiele sind. Eine ausführlichere Diskussion dieses Prinzips findet sich unterTerry Taos ICM-Vortrag im Jahr 2006 . Diese nicht zufälligen Graphen entsprechen in etwa den "Nullsequenzen" in einigen seiner Arbeiten mit Ben Green und anderen.

Normalerweise benutze ich zum Generieren von Grafiken das gengProgramm, das im Lieferumfang enthalten ist nauty:

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

Dies erzeugt ungerichtete Graphen (auch als "Graphen" bezeichnet). Um gerichtete Grafiken zu erstellen, können Sie die Ausgabe directgleiten, die auch mit nauty geliefert wird.

Die Verwendung von geng eignet sich für Szenarien, in denen Sie alle Diagramme bis zu nEckpunkten oder alle verbundenen Diagramme mit mKanten oder Ähnlichem testen möchten . Wenn Sie spezifischere Anforderungen haben, geben Sie diese bitte in Ihrer Frage an.

Die Stanford GraphBase kann Ihnen dabei helfen: http://www-cs-staff.stanford.edu/~knuth/sgb.html

Höchstwahrscheinlich möchten Sie die Diagramme jedoch wahrscheinlich selbst generieren, und Sie möchten wahrscheinlich, dass alle generierten Diagramme bestimmte Eigenschaften haben (oder nicht haben). Zufällige Graphen sind oft eine schlechte Annäherung an die Graphen, auf die ein Algorithmus tatsächlich angewendet wird.

Nicht sehr groß, aber vielleicht immer noch nützlich: 3054 "standard named graphs" aus der GraphData-Sammlung von Mathematica

Das Format ist ein Diagramm pro Zeile mit dem Namen und der Liste benachbarter Knoten wie folgt

{<Grafikname>, {{1, 4}, {1, 5}, {1, 6}, {2, 5}, {2, 6}, {3, 6}}

<Graphenname> Dose der Form "AGraph" oder {"Andrasfai", 6}

Das Igraph-Paket verfügt über verschiedene Arten von Diagrammgeneratoren, darunter sowohl Zufallsdiagramme als auch strukturierte Diagramme.

http://igraph.sourceforge.net/doc/html/igraph-Generators.html

Es gibt ein interessantes und vielversprechendes neues Community-basiertes Projekt für eine Graphendatenbank:

Einführungspapier

Das Open-Graph-Archiv: Ein von der Community getragenes Unterfangen

oder die direkte Verbindung

Graph-Archive.org

Die Zeit wird zeigen, ob es ein guter Ort für Testinstanzen ist.

Die 9. DIMACS-Implementierungsherausforderung - kürzeste Wege wurde 2005-2006 mit dem Ziel durchgeführt, "einen Standardsatz von Benchmark-Instanzen und Generatoren sowie Benchmark-Implementierungen bekannter Shortest Path-Algorithmen zu erstellen".

Die Download-Seite enthält gezippte USA-Straßennetzdiagramme mit einem Bereich von 2 MB bis 335 MB, wobei sowohl die Entfernung als auch die Zeit berücksichtigt werden.

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

Ich fand dies nützlich, um meine eigenen Spielzeugimplementierungen von Graphenfunktionen zu vergleichen.

Sie können Musketier verwenden, sehen

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

Dies ist ein Mehrskalendiagrammgenerator, der ein Eingabediagramm akzeptiert und ein anderes Diagramm generiert, das dem Original beliebig ähnlich sein kann. Die Parameter sind flexibel genug, um eine neue Struktur mit verschiedenen grobkörnigen Auflösungen zu generieren. Siehe Beispiele in der Galerie. Dieses Paket eignet sich perfekt zum Erstellen experimenteller Instanzen für Verifizierungs- und Benchmarking-Algorithmen.