Как реализовать статический граф в C

Question

Мне нужно хранить график для карты игры на игровом сервере, написанном на C.

График имеет ~ 200 узлов и 3 вида ребер, которые могут соединять два узла (эти три вида могуттакже перекрываются: узел может быть связан, например, двумя ребрами двух разных типов).Максимальная степень узла - что-то вроде 5-6 узлов.

Мне бы хотелось, чтобы эта статическая структура была реализована эффективным способом, позволяющим мне выполнять простые операции, такие как

* 1006.* подключен n1 к n2?(со всеми видами ребер в случае положительного ответа) с чем связан n1?(со всеми видами ребер или определенным)

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

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

Я бы хотел избежать использования STL или Boostна данный момент ... есть ли у вас какие-либо подсказки относительно структуры данных, которая могла бы хорошо подойти?

(это не преждевременная оптимизация, дело в том, что она будет работать на VPS, и у меня не так много оперативной памятимощность процессора, поэтому мне нужно держать ее в узде)

РЕДАКТИРОВАТЬ : только потому, что я забыл (и благодаря тому, что я понял это) график ненаправлен , так что каждый крайсимметрично ..

Заранее спасибо

Answer 1

Возможно много ответов.Это зависит от того, что у вас относительно мало узлов.Преимущество этого подхода, вероятно, непревзойденная производительность.

Идея состоит в том, чтобы представить ваш график в виде матрицы байтов 200x200, каждая запись представляет ребро.Байт дает вам 256 различных возможных значений, где 0, очевидно, будет означать «отсутствие соединения», а любая ненулевая комбинация битов может представлять до 8 различных типов ребер.

Позвольте «строке» этой матрицыбыть начальным узлом, а «столбец» - местом назначения.Инициализируйте структуру так, чтобы для каждого ребра, соединяющего один узел с другим, на пересечении начала / конца было значение.Это значение может быть комбинацией битов, представляющих типы ребер.

Чтобы выяснить, соединяется ли один узел с другим, просто запросите байт на пересечении одного узла и другого: если там есть ненулевое значение, тосоединение установлено, и его значение скажет вам, какого типа.

Для 200 узлов эта структура данных израсходует 40 КБ, что довольно умеренно.Он не будет слишком хорошо масштабироваться, когда вы выйдете, скажем, за 1000 узлов.

Пока ничего (кроме однократной инициализации) никогда не пишет в эту структуру, она будет естественно поточно-безопасной, так каксостояние никогда не меняется.

Answer 2

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

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