Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk