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

Subject: Re: [Boost-users] [Graph] Using a bit-based ajacency matrix.
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2009-02-28 15:14:31

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