Re: [Boost-users] BGL: EdgeList template parameter specification for undirected graphs

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2005-03-14 11:03:43

On Jan 28, 2005, at 10:55 AM, Anatoly Petkevich wrote:

>> That's an interesting configuration... so the vertices and out-edges 
>> are
>> stored in vectors, but the list of edges--as accessed via 
>> edges(g)--would be
>> sorted according to some criteria? Is this the representation that's 
>> right
>> for your application? (I haven't seen a need for such a representation
>> before).
>
> Generated graph is a planar proximity graph - some subgraph of 
> Delaunay triangulation. It is known that vertex degree for such graphs
> is at most 6. I do not need edge erdering or parallel edge 
> elimination, thus vecS is used as OutEdgeList argument.  Besides, 
> vector-based storage
> is more space (and time) effecient for such sparse graph than list or 
> associative container.
>
> Proximity graph is derived from original graph by sequence of edge 
> removal. This operation is time-critical for our application. This is 
> the main reason I use
> setS as EdgeListS - to get logarithmic removal time instead of linear.

Depending on the number of edges you're removing and how you determine 
that they need to be removed, you _might_ be able to keep 
EdgeListS=listS and then do one O(|E|) sweep through the graph to 
remove edges via remove_edge_if.

I've entered this as a bug in our bug database. I can't promise when 
I'll get to it, because I'm currently swamped, but I can't forget about 
it. Sorry I can't be of more immediate help :(

        Doug