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

From: Douglas Gregor (dgregor_at_[hidden])
Date: 2005-01-28 02:35:31

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