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

Subject: Re: [Boost-users] [Graph] Using a bit-based ajacency matrix.
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-02-28 11:13:10

>
> 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?

> 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.

Andrew Sutton
andrew.n.sutton_at_[hidden]