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

From: Anatoly Petkevich (phanat_at_[hidden])
Date: 2005-01-28 10:55:18

> 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_at_[hidden]>
To: <boost-users_at_[hidden]>
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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>