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-28 14:58:04

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.

>     I not sure, but I think it would require a new graph concept to take
>     advantage of it.
> 
> 
> That seems unlikely. As far as I know, there aren't many algorithms that 
> dispatch on different graph kinds - except for directionality, but even 
> that's quite rare. As the library stands, the graph concepts are 
> primarily descriptive.
> 
> If there's a substantial difference between the adjacency bitmap and the 
> adjacency matrix, it would be worthwhile to define a refinement.

Ok.

-Thorsten