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

11

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

В моем сценарии несколько пользователей, которые враждебны друг другу, все пытаются сформировать сети компьютеров, где все потенциальные соединения известны. Компьютеры, к которым должен подключиться один пользователь, могут отличаться от компьютеров, к которым должен подключаться другой пользователь; пользователю 1 может потребоваться подключить компьютеры A, B и D, а пользователю 2 может потребоваться подключить компьютеры B, C и E.

введите описание изображения здесь

Изображение сгенерировано с помощью NCTM Graph Creator

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

  1. края могут стать ограниченным использованием; то есть, если один пользователь получает данное сетевое соединение, никакой другой пользователь не может использовать это соединение
    • в этом примере зеленый пользователь не может подключиться к компьютеру A, но красный пользователь подключил B к E, несмотря на отсутствие прямой связи между ними.
  2. в некоторых случаях данная пара узлов будет соединена более чем одним ребром
    • в этом примере есть два независимых кабеля, идущих от D до E, так что зеленый и синий пользователи могли напрямую подключать эти машины; однако красный больше не может сделать такую ​​связь
  3. если два компьютера соединены более чем одним кабелем, каждому пользователю может принадлежать не более одного из этих кабелей

Мне нужно сделать несколько операций над этим графиком, например:

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

Моей первой мыслью было просто создать коллекцию всех ребер, но это ужасно для поиска. Лучшее, что я могу сейчас сделать, - это изменить список смежности, чтобы каждый элемент в списке содержал не только длину ребра, но также его стоимость и текущего владельца. Это разумный подход? Предполагая, что пространство не является проблемой, было бы разумно создать несколько копий графика (по одной для каждого пользователя), а не один граф?

попса
источник
Это как-то кажется актуальным. youtube.com/watch?v=xdiL-ADRTxQ
RubberDuck
Я действительно не вижу, как это поможет здесь.
появляется
Поэтому я немного подумал об этом. В большинстве алгоритмов для графов у вас есть прежде всего две вещи, которые вам нужно сделать: перечислить соседей или найти вес ребра. Все перечисленные вопросы касаются только одного пользователя. Для одного пользователя перечисление соседей или определение веса ребра может быть получено либо в постоянное время (если число пользователей ограничено), либо в журнале N, просто отражая либо список смежности, либо матрицу с «владельцем». В связи с этим, я думаю, что любой из них может быть легко расширен, и его следует выбирать исходя из традиционных преимуществ, а не отвлекать внимание пользователя.
J Trana

Ответы:

6

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

Мне кажется, что вы должны использовать то, что мы могли бы обозначить как «слоистые графы», т.е. добавить комбинатор для графов, скажем @так, чтобы:

  • Если A и B являются графами, то A @ B также является графом (то есть может использоваться для алгоритмов вашей библиотеки графов).
  • Множество вершин в A @ B является объединением вершин в A и B.
  • Множество ребер в A @ B является объединением ребер в A и B.
  • Структура A @ B не владеет какой-либо вершиной или ребром, а использует A и B в качестве контейнеров данных.

С помощью таких многоуровневых графиков вы можете определить K как общую доступную информацию, а R, G, B - каждую личную информацию, так что каждый игрок фактически видит R @ K, G @ K, B @ K.

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

ConcreteGraphAlgorithms = GenericAlgorithms(ConcreteGraphImplementation)

Вы можете легко заменить его на

LayeredGraphAlgorithms = GenericAlgorithms(LayeredGraphs(ConcreteGraphImplementation))

где вы поставляете LayeredGraphsи заимствуете остальное из библиотеки.

Михаэль Ле Барбье Грюневальд
источник
К сожалению, не обращая внимания на мой предыдущий комментарий, я немного неправильно понял ваш ответ. Это в основном то, что я делаю, хотя я не смог воспользоваться существующими библиотеками графов, потому что я по глупости не думал, чтобы увидеть, если таковые существуют.
всплывает
1

То, что вам нужно, называется «приписанным графом». В приписанном графе информация (атрибуты) прикреплена к дугам. Взвешенный граф один из простейших приписанных графов.

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

walrii
источник
1
конечно, матрица смежности обычно не может представлять более 1 ребра между каждой парой узлов
jk.
1
@jk, обычно ты прав. Но информация, вложенная в матрицу смежности, может иметь количество дуг и отдельные атрибуты для каждой дуги. Но в большинстве случаев я бы использовал список смежности, потому что это было бы проще.
Валерий
1
если вы прикрепляете информацию к каждому ребру в ячейку, у вас все равно есть смежный список, вы теряете преимущество, которое дает матрица для плотных графов
jk.