Steven Watanabe skrev:
AMDG
Thorsten Ottosen wrote:
Andrew Sutton skrev:
Not specifically. Building at bitmap-based adjacency matrix shouldn't actually be too difficult, if you're considering it as a space-optimization of the adjacency matrix. Just overload the same set of functions for the adjacency_matrix.
Yes, it is a space optimization, but it is also an optimization is other ways, because we can sometimes make linear operations happen in O(1) time.
Really? Which ones?
A simple example would be to compute the common neighbours of A and B. This is simply
adjbitset(A) & adjbitset(B)
in O(1) time. No iteration is needed. I think there will be many other examples where the big-O characteristics are different when you look into it.
Since when can you compute the bitwise and of an arbitrary size bitset in constant time?
Well, if the bitset size is less than or equal the word size. For larger sizes, the O(1/W * n ) complexity is also significantly better. -Thorsten