
Boost Users : 
From: hicks (hicks_at_[hidden])
Date: 20020506 06:18:03
Choosing the EdgeList type
The EdgeList parameter determines what kind of container will be used to
store the outedges (and possibly inedges) 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 ``bigO'' notation to express the
length of an outedge list. Strictly speaking this is not accurate
because E/V merely gives the average number of edges per vertex in a
random graph. The worstcase number of outedges for a vertex is V
(unless it is a multigraph). 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
offtheshelf.
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/cgibin/boost_wiki/wiki.pl>
>Unsubscribe: <mailto:boostusersunsubscribe_at_[hidden]>
>
>
>Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
>
>
>
[Nontext portions of this message have been removed]
Boostusers 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