[BGL] Get properties from an out_edge_iterator efficiently
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. Cheers, Shaun
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
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
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
participants (2)
-
Jeremiah Willcock -
Shaun Jackman