Я пытаюсь выяснить, какую структуру данных использовать для моделирования гипотетического, идеализированного использования сети.
В моем сценарии несколько пользователей, которые враждебны друг другу, все пытаются сформировать сети компьютеров, где все потенциальные соединения известны. Компьютеры, к которым должен подключиться один пользователь, могут отличаться от компьютеров, к которым должен подключаться другой пользователь; пользователю 1 может потребоваться подключить компьютеры A, B и D, а пользователю 2 может потребоваться подключить компьютеры B, C и E.
Изображение сгенерировано с помощью NCTM Graph Creator
Я думаю, что ядром этого будет неориентированный циклический граф с узлами, представляющими компьютеры, и ребрами, представляющими кабели Ethernet. Однако из-за характера сценария есть несколько необычных возможностей, которые исключают списки смежности и матрицы смежности (по крайней мере, без нетривиальных модификаций):
- края могут стать ограниченным использованием; то есть, если один пользователь получает данное сетевое соединение, никакой другой пользователь не может использовать это соединение
- в этом примере зеленый пользователь не может подключиться к компьютеру A, но красный пользователь подключил B к E, несмотря на отсутствие прямой связи между ними.
- в некоторых случаях данная пара узлов будет соединена более чем одним ребром
- в этом примере есть два независимых кабеля, идущих от D до E, так что зеленый и синий пользователи могли напрямую подключать эти машины; однако красный больше не может сделать такую связь
- если два компьютера соединены более чем одним кабелем, каждому пользователю может принадлежать не более одного из этих кабелей
Мне нужно сделать несколько операций над этим графиком, например:
- определение, подключена ли какая-либо конкретная пара компьютеров для данного пользователя
- определение оптимального пути для данного пользователя для подключения целевых компьютеров
- определение компьютерного соединения с наибольшей задержкой для данного пользователя (т. е. самый длинный путь без разветвления)
Моей первой мыслью было просто создать коллекцию всех ребер, но это ужасно для поиска. Лучшее, что я могу сейчас сделать, - это изменить список смежности, чтобы каждый элемент в списке содержал не только длину ребра, но также его стоимость и текущего владельца. Это разумный подход? Предполагая, что пространство не является проблемой, было бы разумно создать несколько копий графика (по одной для каждого пользователя), а не один граф?
источник
Ответы:
Мне кажется, что вы должны использовать то, что мы могли бы обозначить как «слоистые графы», т.е. добавить комбинатор для графов, скажем
@
так, чтобы:С помощью таких многоуровневых графиков вы можете определить K как общую доступную информацию, а R, G, B - каждую личную информацию, так что каждый игрок фактически видит R @ K, G @ K, B @ K.
Чтобы фактически реализовать это, вы можете искать библиотеку графов, реализующую алгоритмы в общем, то есть, чтобы алгоритм самого длинного пути и т. Д. Были параметризованы фактическим представлением вашего графа. Так что если ваша библиотека говорит
Вы можете легко заменить его на
где вы поставляете
LayeredGraphs
и заимствуете остальное из библиотеки.источник
То, что вам нужно, называется «приписанным графом». В приписанном графе информация (атрибуты) прикреплена к дугам. Взвешенный граф один из простейших приписанных графов.
Чтобы представить приписанный граф, вы можете использовать список смежности, добавляя дополнительные столбцы или матрицы смежности, добавляя больше информации в каждую ячейку. Большинство алгоритмов для неприписанных графов будут работать, если вы фильтруете дуги на основе атрибутов. Многие алгоритмы были разработаны для атрибутивных графов, поэтому я не буду их здесь описывать.
источник