Data untuk pengujian algoritma grafik

Saya mencari sumber set data besar untuk menguji beberapa implementasi algoritma grafik. Harap berikan juga informasi tentang jenis / distribusi (mis. Diarahkan / tidak diarahkan, sederhana / tidak sederhana, berbobot / tidak berbobot) dari grafik di sumber jika diketahui.

Periksa tautan berikut untuk contoh grafik

DIMACS Graphs: Instans Benchmark dan Best Upper Bounds foo

Contoh Pewarnaan Grafik

Instance Benchmark CLIQUE

Saya akan mencoba memberikan jawaban tingkat lebih tinggi daripada yang lain.

Kelas input berikut sering berguna untuk menguji kinerja algoritma yang diusulkan atau validitas dugaan dalam teori grafik:

1. $H$$p$$H$

2. $n$$K_{n/2,n/2}$

3. Grafik "non-acak" : Ini adalah perantara antara yang sepenuhnya generik, seperti dalam grafik acak, dan sepenuhnya spesifik untuk masalah, seperti dalam grafik terstruktur. Misalnya, keluarga seperti itu bisa berupa subgraph acak dari grafik terstruktur. Contoh-contoh semacam itu sering muncul dalam menciptakan varian yang lebih kuat dari lemma keteraturan Szemerédi . Salah satu cara untuk menghasilkan contoh-contoh ini adalah dengan membuat definisi "pseudorandomness" yang memodelkan input acak, sehingga untuk input pseudorandom, Anda dapat menunjukkan bahwa algoritma Anda atau dugaan Anda berfungsi. Kemudian, Anda mengidentifikasi penghalang untuk pseudorandomness, dan grafik yang memiliki penghalang ini kemudian dapat menghasilkan banyak koleksi grafik non-acak yang merupakan contoh tandingan. Diskusi yang lebih terlibat tentang prinsip ini dapat ditemukan diPembicaraan ICM Terry Tao pada tahun 2006 . Grafik non-acak ini kira-kira sesuai dengan "nilafterences" dalam beberapa karyanya dengan Ben Green dan lainnya.

Untuk menghasilkan grafik, saya biasanya menggunakan gengprogram yang datang dengan nauty:

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

Ini menghasilkan grafik yang tidak terarah (juga dikenal sebagai "grafik"). Untuk menghasilkan grafik terarah Anda dapat menyalurkan output directgyang juga disertai dengan nauty.

Menggunakan geng cocok untuk skenario di mana Anda ingin menguji semua grafik pada (katakanlah) hingga nsimpul, atau semua grafik yang terhubung dengan mtepi atau sesuatu seperti itu. Jika Anda memiliki persyaratan yang lebih spesifik, silakan sebutkan ini dalam pertanyaan Anda.

Stanford GraphBase dapat membantu Anda: http://www-cs-staff.stanford.edu/~knuth/sgb.html

Namun, dalam semua kemungkinan, Anda mungkin ingin membuat grafik sendiri, dan Anda mungkin ingin semua grafik yang dihasilkan memiliki (atau tidak memiliki) properti tertentu. Grafik acak seringkali merupakan perkiraan grafik yang buruk yang digunakan algoritma.

Tidak besar, tapi mungkin masih bermanfaat, 3054 "grafik bernama standar" dari koleksi GraphData Mathematica

Formatnya adalah satu grafik per baris, dengan nama dan daftar node yang berdekatan seperti ini

{<nama grafik>, {{1, 4}, {1, 5}, {1, 6}, {2, 5}, {2, 6}, {3, 6}}

<nama grafik> kaleng dalam bentuk "AGraph" atau {"Andrasfai", 6}

Paket Igraph memiliki berbagai jenis generator grafik termasuk grafik acak dan grafik terstruktur.

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

Ada proyek berbasis komunitas baru yang menarik dan menjanjikan untuk basis data grafik:

Memperkenalkan kertas

Arsip Grafik Terbuka: Upaya Berbasis Komunitas

atau tautan langsung

Graph-Archive.org

Waktu akan menunjukkan apakah itu tempat yang baik untuk contoh uji.

Tantangan Implementasi DIMACS ke - 9 - Jalur Terpendek berjalan pada 2005-2006 dengan tujuan untuk menghasilkan "seperangkat contoh standar dan generator, serta implementasi benchmark dari algoritma jalur terpendek yang terkenal."

Halaman unduhan berisi grafik jaringan jalan USA yang di-zip yang berkisar dari 2MB hingga 335MB dengan bobot jarak dan waktu.

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

Saya menemukan ini berguna untuk membandingkan implementasi mainan saya dari fungsi grafik.

Anda dapat menggunakan Musketeer, lihat

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

Ini adalah generator grafik berskala banyak yang menerima beberapa grafik input dan menghasilkan grafik lain yang dapat secara sewenang-wenang serupa dengan aslinya. Parameter cukup fleksibel untuk menghasilkan struktur baru pada resolusi berbutir kasar yang berbeda. Lihat contoh di galeri. Paket ini sangat cocok untuk membuat instance eksperimental untuk verifikasi dan algoritma pembandingan.