On Sep 10, 2009, at 10:16 AM, Mathieu Malaterre wrote:
Hi there,
I am slowly discovering (Parallel) BGL. Could someone confirm the following:
All the BGL examples I found handle dynamic properties (data attached to a vertex) using 'Dynamic Property Maps'. If I understand correctly dynamic_properties are basically a std::map. The complexity to get a value from a std::map is O(log(n)). Thus a graph traversal of all values is O(n * log(n)).
If you have a dynamic graph then this is the best you can do unless you want to define some sort of 'graph mutation phase' and re-index at the end of it.
If this is correct, my question is: is there another approach where I could have a O(1) complexity to access data associated with an edge ?
Yep, if you have a static graph you assign indices to all the vertices and edges and use the indices to index the associated property maps, which is O(1) if the underlying container provides random access. The distributed adjacency list and distributed compressed sparse row graphs both supply edge and vertex indices by default. This method of O(1) lookup is the default behavior for bundled properties and external property maps in PBGL. Andrew could probably confirm/deny the BGL side of things, or I can look later and make sure I don't tell you unconfirmed nonsense. If your graphs aren't static... PBGL doesn't do well with dynamic graphs at the moment, they'll *sort of* work... *sometimes* :) Thanks, Nick
Thanks, -- Mathieu _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users