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

On 8/12/07, Heiko Bauke 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