Dane do testowania algorytmów grafowych

36

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.

Kaveh
źródło
Jak to jest teoretyczne? :-)
Nils

Odpowiedzi:

17

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.pH.

  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.nK.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.

arnab
źródło
14

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.

Emil
źródło
11

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.

Peter Boothe
źródło
9

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}

Jarosław Bułatow
źródło
Czy to są wykresy czy skierowane wykresy?
Emil
3

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.

infogulch
źródło
0

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.

Ilya Safro
źródło