Re: [Boost-Users] voronoi diagram and BGL

From: hicks (hicks_at_[hidden])
Date: 2002-05-06 06:18:03

      Choosing the EdgeList type

The EdgeList parameter determines what kind of container will be used to 
store the out-edges (and possibly in-edges) for each vertex in the 
graph. The containers used for edge lists must either satisfy the 
requirements for Sequence <http://www.sgi.com/tech/stl/Sequence.html> or 
for AssociativeContainer 
<http://www.sgi.com/tech/stl/AssociativeContainer.html> .

        Time Complexity

In the following description of the time complexity for various 
operations, we use E/V inside of the ``big-O'' notation to express the 
length of an out-edge list. Strictly speaking this is not accurate 
because E/V merely gives the average number of edges per vertex in a 
random graph. The worst-case number of out-edges for a vertex is V 
(unless it is a multi-graph). For sparse graphs E/V is typically much 
smaller than V and can be considered a constant.

    *
    *

edge()

      The time complexity for this operation is O(E/V) when the EdgeList
      type is a Sequence <http://www.sgi.com/tech/stl/Sequence.html> and
      it is O(log(E/V)) when the EdgeList type is an
      AssociativeContainer
      <http://www.sgi.com/tech/stl/AssociativeContainer.html> .

Doesn't the above man entry mean that the edges of a vertex are already 
ordered when using Assoc. Cont. ?
Or are you saying,  "insert using sequence, then finally sort the 
sequence before proceeding to next stage of usage" ?
That would be efficient for many applications, but doesn't look possible 
off-the-shelf.

Craig Hicks

Louis Lavery wrote:

>Hi,
>
>Is it possible to order the edges of a vertex of a boost graph?
>
>>From what I can glean from the BGL documentation, I guess the answer
>will be "No, but may be some time in the future". I so, how soon in
>the future?
>
>Thanks,
>
>Louis.
>
>
>
>Info: <http://www.boost.org>
>Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl>
>Unsubscribe: <mailto:boost-users-unsubscribe_at_[hidden]>
> 
>
>Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 
>
>
>
>
>

[Non-text portions of this message have been removed]