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

Subject: Re: [boost] [BGL] Get properties from an out_edge_iterator efficiently
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-01-03 10:33:06

On Fri, 31 Dec 2010, Shaun Jackman wrote:

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

In BGL standard graph types, the edge_descriptor is usually something that 
contains the source, target, and some kind of index to find properties, or 
some subset of that the can be used to look up the rest.  One problem with 
your approach is that edges are passed into functions and algorithms using 
edge_descriptors, not out_edge_iterators, and those would need to be 
changed.  Also, what about iterating through edges using in_edge_iterators 
or edge_iterators?

-- Jeremiah Willcock