Reputation: 5476
There might be similar questions but I still have some parts that I couldn't figure out. I'm trying represent an undirected graph with no weights but just 1 for connected and 0 for not connected. I'm trying to represent a graph (reading from a file) which have 80500 nodes and over 5.5 million edges. I was wondering;
Upvotes: 5
Views: 1862
Reputation: 97004
If your data is not sparse then you may not get as much space savings with an adjacency list. You could use an adjacency matrix with compressed or encoded rows (or columns, but your graph is unidirected, so compressing rows is probably more natural for lookups). With compression you will reduce space, at the time cost of decompressing rows on lookup.
Upvotes: 1
Reputation: 8874
Adjacency lists are wayyyy more better space-wise. Because then you just need to save 5.5 million * 2 numbers = 11 000 000 integers. Assuming you save short integers (2 bytes), then you need 22 000 000 bytes.
If you represent it using adjacency matrix, then you need to save 80500 * 80500 = 6 480 250 000 elements. Even is you save them as bytes, having 22 million bytes is much better than having over 6 billion of them.
EDIT: If you save eges as two 4-byte integers, then you have 44 000 000 bytes. If you save the matrix very efficiently with bit fiddling, then you can save 8 elements in one byte. But is means you still need to have 810 031 250 bytes. Not that large difference now, but it's still 20 times more.
Upvotes: 4