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.
I not sure, but I think it would require a new graph concept to take advantage of it.
That seems unlikely. As far as I know, there aren't many algorithms that dispatch on different graph kinds - except for directionality, but even that's quite rare. As the library stands, the graph concepts are primarily descriptive.
If there's a substantial difference between the adjacency bitmap and the adjacency matrix, it would be worthwhile to define a refinement.
Ok. -Thorsten