5

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?
2
  • What are you using the graph for? Mar 28, 2012 at 17:08
  • I'm writing a friend recommendation algorithm and using the graph for the data
    – Ali
    Mar 28, 2012 at 17:11

2 Answers 2

4

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.

6
  • Thanks a lot. So for the data type part is there anything more efficient than the int ?
    – Ali
    Mar 28, 2012 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.
    – user395760
    Mar 28, 2012 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. Mar 28, 2012 at 17:16
  • You indeed fixed that before I finished my comment. I noticed later and adapted :) Nevertheless, two issues remain.
    – user395760
    Mar 28, 2012 at 17:17
  • Thanks a lot for the statements of these issues
    – Ali
    Mar 28, 2012 at 17:19
1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.