How to implement a static graph in C

Question

Hello, I need to store a graph for the map of a game inside a game server written in C.

The graph has ~200 nodes and 3 kinds of edges that can connect two nodes (these three kind can also overlap: a node can be connected by 2 edges of two different types for example). The maximum degree of a node is something like 5-6 nodes.

What I would like to have is to have this static structure implemented in an efficient way to allow me to do simple operations like

• is n1 connected to n2? (with all kinds of edges in case of affermative response)
• what is n1 connected to? (with all kinds of edges or a specific one)

but in a multi-threaded environment since there will be many instances of the game that relies on the same static graph.

Since the graph can't be modified and the structure is well known I'm sure there are some tricks to implement it in a cool fashion to use least resources possible.

I would like to avoid using STL or Boost for now.. do you have any clues on a data structure that could suit well?

(it's not a premature optimization, the fact is that it will run on a vps and I don't have many ram neither cpu power so I need to keep it tight)

EDIT: just because I forgot (and thanks to make me realize it) the graph is undirected so every edge is symmetric..

Thanks in advance

Answer 1

Since degrees are limited, you can get very good performance by just representing a node by a struct with arrays of pointers to other nodes (one array for each edge type).

Regardless of the data structure you pick, you can avoid worrying about multithreading if your graph is read-only (OK for multiple thread to access it without synchronization).

Answer 2

Many answers are possible. This one relies on the fact that you have relatively few nodes. The advantage of this approach is probably unbeatable performance.

The idea is to represent your graph as a 200x200 matrix of bytes, each entry representing an edge. The byte gives you 256 different possible values, where a 0 will obviously mean "no connection" and any non-zero combination of bits can represent up to 8 different edge types.

Let the "row" of this matrix be the starting node and the "column" be the destination. Initialize the structure such that for every edge connecting one node with another, there's a value at the intersection of starting / ending. That value can be a combination of bits representing edge types.

To find out whether one node connects to another, simply query the byte at the intersection of one node and the other: If there's a nonzero value there, then there is a connection, and the value will tell you what kind.

For 200 nodes, this data structure will eat up 40 KB, which is pretty moderate. It won't scale too well once you get beyond, say, 1000 nodes.

As long as nothing (apart from one-time initialization) ever writes to this structure, it will be naturally thread safe, as its state never changes.