Java – graph data structure in Java (or Python)

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.

You may not necessarily need to solve your problem through a specialized data structure; you can, for instance, find an addressing scheme for each node, which allows you to locate neighbouring nodes in O(1) time, and use a generic data structure to navigate.

A simple scheme here would be assigning to each node a tuple (n, m), where n is the tier and m is the index of the node (assuming 0-indexed, for a node to be valid 0 <= m <= n). For any node, deriving all possible neighbour nodes (ni, mi) is straightforward (smth like (n-1, m-1), (n-1,m), (n, m-1), (n, m+1) etc) - of these you keep those who are valid (0 <= mi <= ni < your triangle size here).

The values can be stored in a vector, the index of node (n, m) is, uniquely, n(n+1)/2 + m.