I wonder what is the fastest method to access edge properties of an adjacency_list when iterating over edges. Actually, the only way I know of for accessing properties is via operator[]:

typedef boost::adjacency_list<listS, vecS, boost::directedS, NodeProperty, EdgeProperty > Graph;

Graph g;

for( tie( ei, ei_end ) = edges( graph ); ei != ei_end; ++ei ) { g[*ei]=something; }

From this I conclude, that the right EdgeProperty is stored in some associative container, with edge_descriptor being the key-type. Or does edge_iterator store any information besides a pair<vertex_descriptor, vertex_descriptor>? What is the time complexity of this look_up?

To me it feels that there should be a faster way to access properties via an edge_iterator, and by browsing the source I found that edge_iterator has a member function get_property(), however, since it returns void*, and I did not find anything in the documentation, I'm not sure if it is there for this purpose.

That's probably the best way to think of it. For an adjacency_list, the edge descriptor is actually a triple of (u, v, p), where p is a pointer to the stored edge property. Operator[] just deref's that pointer, giving you the edge property in constant time. Andrew Sutton andrew.n.sutton@gmail.com

on Mon Dec 08 2008, Julius Ziegler <ziegler-AT-mrt.uka.de> wrote:

Hello list,

I wonder what is the fastest method to access edge properties of an adjacency_list when iterating over edges. Actually, the only way I know of for accessing properties is via operator[]:

typedef boost::adjacency_list<listS, vecS, boost::directedS, NodeProperty, EdgeProperty > Graph;

Graph g;

for( tie( ei, ei_end ) = edges( graph ); ei != ei_end; ++ei ) { g[*ei]=something; }

IIUC that allows you to access bundled edge properties, but in the general case (where you are not depending on the properties being stored in bundles or even internally to the graph) you'd extract property maps and use get and put to do it. Either way should be equally fast. -- Dave Abrahams BoostPro Computing http://www.boostpro.com