Dane do testowania algorytmów grafowych

Szukam źródła ogromnych zestawów danych do przetestowania implementacji algorytmu grafowego. Proszę również podać informacje o typie / rozkładzie (np. Skierowane / nieukierowane, proste / nie proste, ważone / nieważone) wykresów w źródle, jeśli są one znane.

Sprawdź poniższe łącza, aby znaleźć wystąpienia wykresu

DIMACS Graphs: Benchmark Instances and Best Upper Bounds foo

Graficzne instancje kolorystyczne

Instancje wzorcowe CLIQUE

Spróbuję udzielić odpowiedzi na wyższym poziomie niż inne.

Następujące klasy danych wejściowych są często przydatne do testowania wydajności proponowanego algorytmu lub ważności domniemania w teorii grafów:

1. Wykresy losowe : W przypadku wielu właściwości wykresów losowe wykresy są wyjątkowo oczekiwane. Na przykład, ile razy dany pełny wykres dwustronny występuje, gdy podgraph jest minimalizowany na losowym wykresie. (To piękne przypuszczenie Erdősa-Simonovitsa i Sidorenko, że jeśli jest grafem dwustronnym, to losowy wykres z gęstością krawędzi p ma asymptotycznie minimalną liczbę kopii H na wszystkich grafach tego samego rzędu i gęstości krawędzi.) Rozkłady określone przez losowe wykresy są źródłem wielu dolnych granic dla algorytmów losowych wykresów, zgodnie z zasadą minimax Yao . $H$$p$$H$

2. Wykresy strukturalne : Jest to zgrubne oznaczenie dla klasy wykresów, które są w jakiś sposób specjalnie skonstruowane dla danego problemu. Na przykład twierdzenie Turána mówi, że najgęstszym wykresem wierzchołków, który jest wolny od trójkątów, jest pełny dwuczęściowy wykres K n / 2 , n / 2 ; ten wykres jest specjalnie zbudowany, aby uniknąć trójkątów.$n$$K_{n/2,n/2}$

3. Wykresy „nieprzypadkowe” : są to wartości pośrednie między byciem całkowicie ogólnymi, jak w przypadku wykresów losowych, a całkowicie specyficznymi dla problemu, jak na wykresach strukturalnych. Na przykład taką rodziną mogą być losowe podgrupy wykresów strukturalnych. Takie przykłady pojawiają się często przy tworzeniu silniejszych wariantów lematu regularności Szemerédiego . Jednym ze sposobów na wytworzenie tych przykładów jest opracowanie definicji „pseudolosowości”, która modeluje przypadkowe dane wejściowe, aby w przypadku danych pseudolosowych można pokazać, że działa algorytm lub domniemanie. Następnie identyfikujesz przeszkody na drodze pseudolosowej, a wykresy, które mają te przeszkody, mogą następnie wygenerować duży zbiór nieprzypadkowych wykresów, które są kontrprzykładami. Bardziej zaangażowaną dyskusję na temat tej zasady można znaleźć na stronieWystąpienie Terry Tao w ICM w 2006 roku . Te nieprzypadkowe wykresy z grubsza odpowiadają „zerowym ciągom” w niektórych jego dziełach z Benem Greenem i innymi.

Do generowania wykresów zwykle używam gengprogramu dostarczonego z nauty:

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

W ten sposób powstają niekierowane wykresy (znane również jako „wykresy”). Aby utworzyć ukierunkowane wykresy, możesz directgprzesłać dane wyjściowe, przez które również pochodzi z nauty.

Korzystanie z geng jest odpowiednie w scenariuszach, w których chcesz przetestować wszystkie wykresy (powiedzmy) do nwierzchołków lub wszystkie połączone wykresy z mkrawędziami lub coś w tym rodzaju. Jeśli masz bardziej szczegółowe wymagania, podaj je w swoim pytaniu.

Stanford GraphBase może ci pomóc: http://www-cs-staff.stanford.edu/~knuth/sgb.html

Najprawdopodobniej najprawdopodobniej zechcesz samodzielnie wygenerować wykresy i prawdopodobnie zechcesz, aby wszystkie wygenerowane wykresy miały (lub nie) pewne właściwości. Wykresy losowe są często słabym przybliżeniem wykresów, na których algorytm faktycznie się przyzwyczaja.

Niezbyt duże, ale być może nadal przydatne, „standardowe wykresy o nazwie 3054” z kolekcji GraphData Mathematiki

Format to jeden wykres na linię, z nazwą i listą sąsiednich węzłów w ten sposób

{<nazwa wykresu>, {{1, 4}, {1, 5}, {1, 6}, {2, 5}, {2, 6}, {3, 6}}

<nazwa wykresu> może mieć postać „AGraph” lub {„Andrasfai”, 6}

Pakiet Igraph ma różne typy generatorów wykresów, w tym zarówno wykresy losowe, jak i wykresy strukturalne.

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

Istnieje ciekawy i obiecujący nowy projekt społecznościowy dotyczący bazy danych grafów:

Przedstawiamy papier

Archiwum Open Graph: wysiłek kierowany przez społeczność

lub bezpośredni link

Graph-Archive.org

Czas pokaże, czy jest to dobre miejsce na instancje testowe.

9-ci DIMACS Realizacja Challenge - Najkrótsze ścieżki prowadził w latach 2005-2006 z celem wytworzenia „standardowy zestaw przypadkach porównawczych i generatorów, a także implementacje porównawczych znanych algorytmów najkrótszych ścieżek”.

Strona pobierania zawiera spakowane wykresy sieci drogowej w USA, które zawierają się w przedziale od 2 MB do 335 MB, zarówno z wagą odległości, jak i czasu.

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

Uznałem, że jest to użyteczne do testowania własnych implementacji zabawek funkcji graficznych.

Możesz użyć Muszkietera, patrz

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

Jest to generator wykresów wieloskalowych, który akceptuje niektóre wykresy wejściowe i generuje inny wykres, który może być dowolnie podobny do oryginału. Parametry są wystarczająco elastyczne, aby wygenerować nową strukturę przy różnych gruboziarnistych rozdzielczościach. Zobacz przykłady w galerii. Ten pakiet jest idealny do tworzenia eksperymentalnych instancji dla algorytmów weryfikacji i testów porównawczych.