Re: [Boost-users] [BGL] adjacency_list: OutEdgeList and EdgeList

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2004-02-11 11:18:03

Hi Ded,

On Feb 11, 2004, at 10:07 AM, Ded Panas wrote:

> I'm somewhat unclear about the difference between OutEdgeListS and 
> EdgeListS selectors of adjacency_list.

The EdgeListS selector determines the container used to store the edge 
properties for all the edges in
the graph. THe OutEdgeListS selector determines the container that 
stores the out edges for each vertex.

> My questions is:
> 1. Why EdgeListS defaults to listS, while OutEdgeListS to vecS (BTW, 
> doc says that EdgeListS defaults to vecS also) ?

EdgeListS defaults to listS so that removing an internal edge property 
can be accomplished
in constant time.

OutEdgeListS defaults to vecS to allow for faster traversal. Granted, 
edge removal is a bit slower... it
is linear with respect to the number of out edges for a particular 
vertex, but that number is often small.
Of course, this is just the default and you can choose listS if you 
want.

Thanks for spotting the error in the docs.

> 2. In the docs ("Choosing the Edgelist and VertexList"), what is 
> Edgelist: OutEdgeListS or EdgeListS? It is unclear (seems it is 
> OutEdgeListS).

Thanks for spotting that. It should be OutEdgeListS.

(In an earlier version of the BGL, there was no EdgeList parameter, and 
the OutEdgeList parameter
was named EdgeList, so you're seeing stuff that never got updated).

Cheers,
Jeremy

_______________________________________________
Jeremy Siek <jsiek_at_[hidden]>
http://www.osl.iu.edu/~jsiek
Ph.D. Student, Indiana University Bloomington
C++ Booster (http://www.boost.org)
Office phone: [phone]
_______________________________________________