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

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-04-02 06:30:03

On 4/2/07, Jens Müller <jens.mueller_at_[hidden]> wrote:
> 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 point is, there's no concept for a planar graph, as such, but there
is a concept for a planar embedding. So any algorithm that works on a
planar graph expects a graph and a planar embedding. The traversal you're
talking about - walking around the face of a graph - is implemented in my
code using visitor event points (like the BGL depth-first and breadth-first
search), which I would prefer to using specially-constructed iterators.

>
> > 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?
>

Yes - if you have a guarantee that the edges will be stored in the order you
put them in, then you can define a property map to do this for you.

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

Sound good.

Regards,
Aaron