Re: [Boost-users] PBGL / Dynamic Property Maps complexity

Subject: Re: [Boost-users] PBGL / Dynamic Property Maps complexity
From: Nick Edmonds (ngedmond_at_[hidden])
Date: 2009-09-12 15:39:09

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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users