Стратегия построения тестовых графиков для алгоритма Дейкстры? - PullRequest
Новая
       31

Стратегия построения тестовых графиков для алгоритма Дейкстры?

2 голосов
/ 13 марта 2012

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

В настоящее время я использую наивный метод. Узлы создаются в случайных местах в 2d пространстве (где x и y - целые числа без знака между 0 и некоторой константой MAX_SPACE). Ребра создаются случайным образом для соединения узлов, так что каждый узел имеет степень не менее 1 (и не более MAX_DEGREE). Indegree не применяется. Затем я ищу путь между первым и последним узлами в наборе, который может или не может быть подключен.

В более реалистичной ситуации вероятность подключения узлов будет пропорциональна их близости в 2-мерном пространстве. Какова хорошая стратегия для построения случайных тестовых графиков с этим свойством?

ПРИМЕЧАНИЯ

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

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

  • MIN_NODES, MAX_NODES: диапазон размеров для графика
  • СОЕДИНЕНИЕ: средний уровень
  • БЛИЗОСТЬ: вес, отданный предпочтению соединения проксимальных узлов

1 Ответ

1 голос
/ 23 марта 2012

Вы можете начать с просмотра различных генераторов случайных графов, доступных в JUNG (библиотека Java):

  • Генератор Барабаси Альберта - Простой развивающийся безмасштабный генератор случайных графов. На каждом временном шаге создается новая вершина, которая соединяется с существующими вершинами в соответствии с принципом «преимущественного присоединения», причем вершины с более высокой степенью вероятности выбираются для присоединения.

  • Генератор степенных законов Эппштейна - Генератор графов, который генерирует неориентированные графы со степенным распределением степеней.

Существуют различные другие генераторы, доступные для - См. Список здесь

Для python есть библиотека NetworkX , которая также предоставляет множество генераторов графов - Listed Here

Со многими из этих генераторов вы можете указать размер, чтобы вы могли начать с малого и идти оттуда.

...