
Boost Users : 
Subject: Re: [Boostusers] [Graph] Using a bitbased ajacency matrix.
From: Thorsten Ottosen (thorsten.ottosen_at_[hidden])
Date: 20090301 05:32:49
Steven Watanabe skrev:
> AMDG
>
> Thorsten Ottosen wrote:
>> Andrew Sutton skrev:
>>> Not specifically. Building at bitmapbased adjacency matrix
>>> shouldn't actually be too difficult, if you're considering it as
>>> a spaceoptimization 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 bigO 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
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net