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? In Christ, Steven Watanabe