Re: [Boost-users] complexity of boost::num_vertices boost::num_edges

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-08-12 16:30:35

On 8/12/07, Heiko Bauke <heiko.bauke_at_[hidden]> wrote:
> Hi,
>
> I wonder what is the time complexity of boost::num_vertices and
> boost::num_edges? Are these constant time operations? I could not find
> an answer to this question in BGL documentation.

Hi Heiko,

Neither of these is necessarily a constant-time operation. In the
BGL's adjacency_list, the size() method of the underlying container
used to store edges or vertices is called, which can take time O(n) on
a container of n elements if a std::list is used. Directed
adjacency_lists are also an exception; num_edges takes either O(n) or
O(m) for an n-vertex, m-edge graph, depending on how the edge list is
stored.

Regards,
Aaron