Данные для тестирования алгоритмов графа

36

Я ищу источник огромных наборов данных для проверки реализации алгоритма графа. Просьба также предоставить некоторую информацию о типе / распределении (например, направленных / ненаправленных, простых / не простых, взвешенных / невзвешенных) графиков в источнике, если они известны.

Кава
источник
Соответствующий пост: cstheory.stackexchange.com/questions/16751/…
Нил Янг
Как это теоретически? :-)
Нильс

Ответы:

17

Я постараюсь дать более высокий ответ, чем другие.

Следующие классы входных данных часто полезны для проверки работоспособности предложенного алгоритма или обоснованности гипотезы в теории графов:

  1. Случайные графы : для многих свойств графов случайные графы являются экстремальными в ожидании. Например, число раз, когда данный полный двудольный граф встречается, когда подграф минимизируется в случайном графе. (Это прекрасная гипотеза Эрдёша-Симоновича и Сидоренко о том, что если - двудольный граф, то случайный граф с реберной плотностью p в асимптотическом порядке имеет минимальное количество копий H по всем графам одного порядка и реберной плотности.) Распределения, заданные через случайные графы, являются источником множества нижних границ для алгоритмов рандомизированных графов по принципу минимакса Яо . ЧАСпЧАС

  2. Структурированные графы . Это грубое обозначение для класса графов, которые каким-то образом специально структурированы для рассматриваемой задачи. Например, теорема Турана гласит, что самый плотный граф на вершинах, не имеющий треугольников, является полным двудольным графом K n / 2 , n / 2 ; этот график явно специально построен, чтобы избежать треугольников.NКN/2,N/2

  3. «Неслучайные» графы : они являются промежуточными между тем, чтобы быть полностью общими, как в случайных графах, и полностью специфичными для проблемы, как в структурированных графах. Например, такое семейство может быть случайными подграфами структурированных графов. Такие примеры часто встречаются при создании более сильных вариантов леммы регулярности Семереди . Одним из способов создания этих примеров является определение «псевдослучайности», которая моделирует случайные входные данные, так что для псевдослучайных входных данных вы можете показать, что ваш алгоритм или ваша гипотеза работают. Затем вы идентифицируете препятствия псевдослучайности, и графы, которые имеют эти препятствия, могут затем создать большую коллекцию неслучайных графов, которые являются контрпримерами. Более активное обсуждение этого принципа можно найти наICM разговор Терри Тао в 2006 году . Эти неслучайные графики примерно соответствуют «нулевым последовательностям» в некоторых его работах с Беном Грином и другими.

Арнаб
источник
14

Для создания графиков я обычно использую gengпрограмму, которая поставляется с nauty:

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

Это создает неориентированные графы (также известные как «графы»). Для создания ориентированных графов вы можете направить вывод, через directgкоторый также идет nauty.

Использование geng подходит для сценариев, в которых вы хотите проверить все графики, скажем, вплоть до nвершин, или все связанные графы с mребрами или что-то в этом роде. Если у вас есть более конкретные требования, укажите их в своем вопросе.

Эмиль
источник
11

Stanford GraphBase может помочь вам: http://www-cs-staff.stanford.edu/~knuth/sgb.html

Однако, по всей вероятности, вы, вероятно, захотите сгенерировать графики самостоятельно, и вы, вероятно, захотите, чтобы все сгенерированные графики имели (или не имели) определенные свойства. Случайные графы часто являются плохим приближением графов, к которым фактически применяется алгоритм.

Питер Бут
источник
9

Не огромный, но, возможно, все еще полезный, 3054 "стандартных именованных графов" из коллекции GraphData Mathematica

Формат - один граф на строку, с именем и списком соседних узлов, как это

{<имя графа>, {{1, 4}, {1, 5}, {1, 6}, {2, 5}, {2, 6}, {3, 6}}

<имя графа> банка в форме "AGraph" или {"Andrasfai", 6}

Ярослав Булатов
источник
Это графы или ориентированные графы?
Эмиль
4

Существует интересный и многообещающий новый проект для графической базы данных на базе сообщества:

Представляем бумаги

Архив Open Graph: усилие сообщества

или прямая ссылка

Graph-Archive.org

Время покажет, подходит ли это для тестовых экземпляров.

Марк Бери
источник
3

Девятым DIMACS Реализация Challenge - Кратчайшие пути провел в 2005-2006 годах с целью производства «стандартный набор экземпляров тестов и генераторов, а также реализации тестов хорошо известных алгоритмов кратчайших путей.»

Страница загрузки содержит сжатые графы дорожной сети США, которые варьируются от 2 МБ до 335 МБ с весами расстояния и времени.

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

Я нашел это полезным для сравнения моих собственных игрушечных реализаций функций графа.

infogulch
источник
0

Вы можете использовать мушкетер, смотрите

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

Это генератор многомасштабных графов, который принимает некоторый входной граф и генерирует другой граф, который может быть произвольно похож на оригинал. Параметры достаточно гибкие, чтобы генерировать новую структуру с различными крупнозернистыми разрешениями. Смотрите примеры в галерее. Этот пакет идеально подходит для создания экспериментальных примеров для алгоритмов проверки и тестирования.

Илья Сафро
источник