Boost logo

Boost Users :

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


Boost-users 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