What is the most space efficient way to implement a graph data structure?

Question

I typically implement graphs as doubly linked lists but this is fairly space inefficient in my experience as I need k pointers/references for k neighbors so for an undirected graph I'd have ~2k neighbor links within the lists if my math is right. Is there a better way of saving space? I know that some of the links can be made singular if the graph is directed but is there a way to do a better job of this?

Answer 1

Well if space efficiency is all you care about then a compressed data structure would be best - but of course this isn't very efficient for access or update.....

If your graph has a relatively small number of nodes and is fairly dense (lets say at least 5% of all possible connections exist) then you may find it is more space efficient to create an adjacency matrix rather than using edge lists. This would require just one bit per possible (directed) connection, and n*n bits total where you have n nodes.

Otherwise if you need to use neighbour links then you can't easily do better than one reference per link since this is the minimum information content you need to store. If you want back-links you will need twice as many links.

There are some tricks you could try on top of this. For example, you could try sharing subsets of links ( if A and B refer to each of C, D, E then only store the list of links C,D,E once.....). However this will get complex pretty quickly and I doubt it will be worth the effort in most cases.

One other trick - assuming your graph has a reasonable number of nodes, you will certainly save space by indexing - e.g. using a 16-bit node index number rather than a full pointer / reference.

Answer 2

It's going to depend on the structure your data.

For a dense graph with undirected edges, you can't really beat a list of bit arrays representing a triangular matrix. A List<BitArray> for example. Logically, it would look like this:

 0123
0
11
211
3001
41010

From there, you can use the index of the root BitArray to index into a list that stores your node data.

For example, getting all of the neighbours of a node would go like:

// C#
List<Node> Nodes = /* populated elsewhere */
List<BitArray> bits = /* populated elsewhere */
public static IEnumerable<Node> GetNeighbours(int x)    
{
    for (int i = 0; i < bits[idx].Count; i++)
    {
        if (this.bits[idx][i])
            yield return this.Nodes[i];
    }

    for (int i = 0; i < this.Nodes.Count; i++)
    {
        if (idx < this.bits[i].Count && this.bits[i][idx])
            yield return this.Nodes[i];
    }    
}

(note that you can also choose the index type, depending on the amount of data, to be a byte or ushort or something along those lines as all indexes will be positive. I don't consider this a micro-optimization as it's trivial)

For a directed graph, you would go the route of a n*n array of bits to store the connectivity... unless it's very sparse compared to the number of nodes, where you can go to an adjacency list of indices.