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

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. Thanks, Anatoly. ----- Original Message ----- From: "Douglas Gregor" To: Sent: Friday, January 28, 2005 09:35 AM Subject: Re: [Boost-users] BGL: EdgeList template parameter specification forundirected graphs

On Tuesday 25 January 2005 07:03 am, Anatoly Petkevich wrote:

...

Hi!

I am trying to use the BGL to create sparse undirected graph using boost::setS as template argument for EdgeList parameter:

typedef adjacency_list GraphType;

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).

...

Impementation of boost::add_edge() for undirected graphs calls g.m_edges.push_back(e), and we get compilation error here since push_back() is not a member of associative container std::set. There is no such a problem for directed graphs (directedS).

Directed graphs don't actually use the EdgeListS parameter. It's only needed for undirected graphs.

...

According to the BGL documentation there are no restrictions on EdgeList parameter for undirected graphs. Is this an undocumented feature or inconsistent implementation or library misuse?

Inconsistent implementation. When adjacency_list was written, I think it was assumed that associative containers would not show up in EdgeListS. I don't know deep that assumption goes, or what it would take to eliminate it.

Doug _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users