[Boost-users] [BGL] complexity of random_vertex/random_edge

From: martin f krafft (madduck_at_[hidden])
Date: 2005-05-16 16:28:55

http://www.boost.org/libs/graph/doc/random.html claims that
random_vertex and random_edge both have a runtime complexity linear
in the number of vertices and edges, respectively. This seems weird.

Given a random access iterator and the number of elements,
retrieving a random member should be doable in constant time. Is the
complexity guarantee here based on the worst case of the lists only
being directionally accessible? If yes, does using container class
implementing the RandomAccessIterator concept automatically select
constant-time versions of these random retrievers?

Thanks for your comments.

-- 
martin;              (greetings from the heart of the sun.)
  \____ echo mailto: !#^."<*>"|tr "<*> mailto:" net_at_madduck
 
invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver!
spamtraps: madduck.bogus_at_[hidden]
 
this product is under strict quality contril with perfect packing and
quality when leving the factory.please keep away from damp.high
temperature or sun expose.If found any detectives when purchasing.
please return the productby airmail to our administration section and
inform the time, place.and store of this purchase for our
improvement.We shall give you a satisfactory reply.Thanks for your
patronage and welcome your comments.
                                             -- http://www.engrish.com