Re: [boost] [BGL] Get properties from an out_edge_iterator efficiently

Subject: Re: [boost] [BGL] Get properties from an out_edge_iterator efficiently
From: Shaun Jackman (sjackman_at_[hidden])
Date: 2010-12-31 19:54:18

Hi Jeremiah,

In many cases, an edge_descriptor is a pair<vertex_descriptor,
vertex_descriptor>. If the container of adjacent vertices is an unsorted
vector or list, then it requires searching that list. An
out_edge_iterator on the other hand is likely an iterator pointing
directly to the edge in question. Yes, an edge_descriptor could contain
an edge_iterator, but that increases the size and complexity of an
edge_descriptor unnecessarily.

Cheers,
Shaun

On Thu, 2010-12-16 at 22:11 -0800, Jeremiah Willcock wrote:
> On Thu, 16 Dec 2010, Shaun Jackman wrote:
> 
> > Hi,
> >
> > I have a graph implementation where
> >        get(tag, graph, out_edge_iterator)
> > is much more efficient than
> >        get(tag, graph, edge_descriptor)
> > which is probably not an usual case.
> >
> > Would it make sense for BGL to provide a default implementation of the
> > former that dereferences the iterator and calls the latter? Graphs for
> > which the former is more efficient could then specialize this function
> > template.
> 
> I don't see many use cases where an iterator would be that much faster to 
> access properties from than an edge descriptor.  If the performance is 
> really a lot better for your implementation, you can store a copy of the 
> iterator (or whatever information from it needed to get the properties 
> more quickly) into the edge descriptor itself.
> 
> -- Jeremiah Willcock