BGL: EdgeList template parameter specification for undirected graphs
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<vecS, vecS, undirectedS, no_property, no_property, no_property, setS> GraphType; 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). 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? Regards, A.Petkevich
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<vecS, vecS, undirectedS, no_property, no_property, no_property, setS> 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
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" <dgregor@cs.indiana.edu> To: <boost-users@lists.boost.org> 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<vecS, vecS, undirectedS, no_property, no_property, no_property, setS> 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
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
participants (3)
-
Anatoly Petkevich -
Douglas Gregor -
Douglas Gregor