Memory Layout for Graphs

[SebastianStehle]

As a co-founder of https://busradar.com I was working on a similar solution but it was not as good as itinero. I would like to understand the memory layout of the graphs.

I had a look to Graph.cs and DirectedGraph.cs

In my understanding...

Graph.cs

• Structures the edge as double linked list.
• If an edge is removed the slot is "lost"
• You can undo the fragmentation by calling "compress"

DirectedGraph.cs

• I have problems to understand the structure, I guess that they the edges are stored in continuous memory to improve memory locality and to improve performance.
• But this would mean that the pointers to the first edges are updated after an edge is added or removed and I don't see it in memory.

Can you clarify this for me or do you have a good paper?

[xivk]

You are basically correct in you assumptions on graph.cs. Over the years I have found some room for improvement but it has to stay like this for now because of backwards compat. The biggest improvement is to have the vertices point to the last edge added not the first. This saves an enumeration of all existing edges for a vertex when adding new edges.

As for the directed graph, you have vertices that point to their first edge and have a count with the # of edges. There are always a # of free slots allocated for edges per vertex as a power of 2. When the edge count exceeds that count they are all copied to the end of the edges array. There is always as much space reserved for each vertex's edges as the first power of 2 larger than the # of edges.

Trim() again reclaims all empty slots and compres makes the graph readonly by removing all empty slots for each vertex with # of edges not equal to a power of 2.

This is from memory, not sure about all the details, it's been a while since I built this.