Take the 2-minute tour ×

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;

  1. Is it going to be a huge impact if I change my adjacency matrix(the one that I'm currently using) to a adjacency list. I have no problem with the implementation just asking will it worth the time to convert it to list?
  2. Since I just store 1 and 0 is there a special data type no store this. I'm using in and I guess a byte data type would save a lot of time.
  3. Any other structure than adjacency matrix or list that could be better for this typical problem?
share|improve this question
What are you using the graph for? –  Jakub Zaverka Mar 28 '12 at 17:08
I'm writing a friend recommendation algorithm and using the graph for the data –  Ali Mar 28 '12 at 17:11
add comment

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
Thanks a lot. So for the data type part is there anything more efficient than the int ? –  Ali Mar 28 '12 at 17:12
Consider: (1) One can pack the booleans in the adjacency matrix very tightly - you need some bit fiddling, but you can end up using each bit efficently (2) For the adjacency lists, you'll need something larger than 16 bit integers, as 80500 > 2^16. –  delnan Mar 28 '12 at 17:13
Every edge is represented by two integers. So we take 5.5 million edges = 11 million integers. If we use short int for saving, then each number will take two bytes. 11 million numbers * 2 bytes = 22 million bytes. You might be confused, I actually corrected a mistake I made previously. –  Jakub Zaverka Mar 28 '12 at 17:16
You indeed fixed that before I finished my comment. I noticed later and adapted :) Nevertheless, two issues remain. –  delnan Mar 28 '12 at 17:17
@delnan see edit –  Jakub Zaverka Mar 28 '12 at 17:19
show 2 more comments

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.

share|improve this answer
add comment

Your Answer


