how to implement a huge adjacent matrix?

[luke.yolanda]

Hi everyone
Now i'm designing a random instances generator for maximum clique
problem using C.
So I planing to implement a adjacent matrix in this generator to store
the whole graph going to be generated. I couldn't find a method other
than using an unsigned char[][], but in this way, 7 bits in a unsigned
char will be wasted. Could anyone teach me a more effective way to
implement it? Thank you!

 

[Vladimir S. Oka]

Hi everyone
Now i'm designing a random instances generator for maximum clique
problem using C.
So I planing to implement a adjacent matrix in this generator to store
the whole graph going to be generated. I couldn't find a method other
than using an unsigned char[][], but in this way, 7 bits in a
unsigned char will be wasted. Could anyone teach me a more effective
way to implement it? Thank you!

If I understand your problem correctly, you actually want an /adjacency/
matrix which, if memory serves is just a 0/1 matrix. So, it seems you
want to pack your bits, instead of using a whole `char` for each one.
You can still use the same sort of matrix you say you have now, just
pack your bits into it's elements. To make this as portable as
possible, do not assume, say, 8 bits, but use CHAR_BIT defined in
<limits.h> to tell you the size of `char` on your system. This will be
more work, so you will lose some performance extracting and packing
bits, but not too much.

 

[Keith Thompson]

Hi everyone
Now i'm designing a random instances generator for maximum clique
problem using C.
So I planing to implement a adjacent matrix in this generator to store
the whole graph going to be generated. I couldn't find a method other
than using an unsigned char[][], but in this way, 7 bits in a
unsigned char will be wasted. Could anyone teach me a more effective
way to implement it? Thank you!

If I understand your problem correctly, you actually want an /adjacency/
matrix which, if memory serves is just a 0/1 matrix. So, it seems you
want to pack your bits, instead of using a whole `char` for each one.
You can still use the same sort of matrix you say you have now, just
pack your bits into it's elements. To make this as portable as
possible, do not assume, say, 8 bits, but use CHAR_BIT defined in
<limits.h> to tell you the size of `char` on your system. This will be
more work, so you will lose some performance extracting and packing
bits, but not too much.

And use unsigned char, not plain char (which can be either signed or
unsigned).