Re: [Boost-users] [Graph] Using a bit-based ajacency matrix.

Andrew Sutton skrev:

On Tue, Feb 24, 2009 at 12:13 PM, Thorsten Ottosen mailto:thorsten.ottosen@dezide.com> wrote:

Dear All,

Does anybody have experience with the above. That is, to represent the graph as a bit-based ajacency matrix, and then use that together with Boost.Graph?

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.

I'm thinking that Boost.Graph will not exploit this representation optimally. Am I correct?

Maybe, maybe not - it depends on your meaning. The efficiency of BGL algorithms depends on the efficiency of the overloads you provide.

I not sure, but I think it would require a new graph concept to take advantage of it. -Thorsten