Re: [boost] [BGL] Tools for planar graph testing/embedding/drawing in the vault

From: Jens Müller (jens.mueller_at_[hidden])
Date: 2007-04-02 04:06:15

Aaron Windsor wrote:

> 
>>Have you specified concepts for planar graphs?
>>
>>If so, maybe I can pimp the leda_graph.hpp accordingly.
> 
> 
> Yes - basically, the concept for a "planar graph" is a graph plus a planar
> embedding. A planar embedding is a property map that maps any vertex
> in the graph to an ordered list of edges adjacent to that vertex.

Umm ... I'd say this is your implementation, but not really the concept.

It could be done more abstract, right?

So you can have an iterator that walks around a face of the graph, or 
the edges of a vertex in clockwise order.

> The ordered
> list of edges corresponds to the clockwise ordering of those edges in a
> plane drawing of the graph. So, it's a little more flexible than having, say,
> a PlanarGraph concept that refines one of the other graph concepts in the
> BGL - if you actually want the algorithm to re-arrange the edges in your
> graph, it can do so, through the indirection of a property map. But you
> can also store the planar embedding externally, with a vector of vectors,
> for example.

Would it be possible with the current interface to have an 
adjacency_list implementation that directly stores ordered edge lists?

> Right now, the concept of a planar embedding is an lvalue property map
> p that supports p[v].begin(), p[v].end(), p[v].push_back(Edge), p[v].clear(),
> but I'm still open to changing this - maybe having free functions begin, end
> push_back, and clear that take a planar embedding's value_type as the
> template parameter and an argument to the function would be a little more
> general, since they could default to actually calling begin(), end(),
> push_back(Edge), and clear() member functions, but would be a little easier
> to override in the case you don't want to store the planar embedding in
> something that acts like an STL container.

OK, I think I'll take a look at your code first and then come back to 
the issue ...