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

Subject: Re: [Boost-users] [Graph] Using a bit-based ajacency matrix.
From: Thorsten Ottosen (thorsten.ottosen_at_[hidden])
Date: 2009-02-27 10:55:11

Andrew Sutton skrev:
> 
> 
> On Tue, Feb 24, 2009 at 12:13 PM, Thorsten Ottosen 
> <thorsten.ottosen_at_[hidden] <mailto:thorsten.ottosen_at_[hidden]>> 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