Suitable data structure for large graphs

Question

I have a large graph, is there any other data structure other than adjacency list and "adjacency matrix" in c++ stl or some other data structure which I can employ for such a large graph, actually the adjacency matrix of my graph does not fit in the main memory. My graph is directed and I am implementing dijkstra algorithm in C++.

I have seen the previous posts...but I am searching for a suitable data structure with respect to dijkstra.

By large I mean a graph containing more than 100 million nodes and edges.

Answer 1

It's common to represent adjacency lists as lists of integers, where the integer is the index of a node. How about getting some more space efficiency by instead treating the adjacency list as a bit string 00010111000... where a 1 in nth position represents an edge between this node and node n? Then compress the bitstring by some standard algorithm; uncompress it as you need it. The bit strings will probably compress pretty well, so this trades space efficiency for higher computational cost.