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