[Boost-users] PBGL / Dynamic Property Maps complexity

Subject: [Boost-users] PBGL / Dynamic Property Maps complexity
From: Mathieu Malaterre (mathieu.malaterre_at_[hidden])
Date: 2009-09-10 10:16:23

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 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
?

Thanks,
-- 
Mathieu