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