Boost logo

Boost Users :

Subject: Re: [Boost-users] [Boost.Graph] Accessing edge properties via an edge_iterator
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2008-12-08 15:22:06


>
> 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_at_[hidden]



Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net