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-03-01 05:32:49

Steven Watanabe skrev:
> 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?

Well, if the bitset size is less than or equal the word size. For larger 
sizes, the O(1/W * n ) complexity is also significantly better.

-Thorsten