Boost logo

Boost Users :

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


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