Re: [Boost-users] Graph Library Question

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2005-03-17 23:40:50

On Feb 16, 2005, at 3:27 PM, Todd A. Gibson wrote:
> I have a code base which uses adjacency_list as the underlying graph
> structure.  I tried converting from adjacency_list to adjacency_matrix
> and discovered that adjacency_matrix does not implement the in_edges()
> non-member function (nor the corresponding iterators).
>
> What is the design rationale for including only out_edges() in
> adjacency_matrix but not in_edges()?

Not really. Traversal of in-edges will be slower than traversal of 
out-edges (because it would stride across the matrix, causing very bad 
cache behavior for large graphs), but not so slow that we shouldn't 
provide it.

> Is there a recommended alternative for traversing in_edges for an
> adjacency_matrix?

If you need in_edges, then you need in_edges; there's really no way 
around it. It shouldn't be very hard to implement this functionality: 
one would need to implement an iterator adaptor that steps down the 
rows in the adjacency matrix (for the directed case) and deals with the 
triangular storage of the adjacency matrix (for the undirected case). 
If you're willing to implement it, I'd be glad to review, document, and 
integrate the result. If not, I'll create a bug report in the 
Sourceforge bug tracker to get it fixed, but I can't even guess when 
I'll be able to get to it.

        Doug