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

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-07-27 17:35:53

On 7/27/07, Doug Gregor <dgregor_at_[hidden]> wrote:
> Hi Aaron,
>
> On Apr 1, 2007, at 12:04 PM, Aaron Windsor wrote:
> > I've implemented a small suite of tools for dealing with planar
> > graphs and
> > would like to add it to the BGL. The core of this suite is built
> > around the
> > recent Boyer-Myrvold algorithm for planarity testing/embedding.
> > (see http://www.emis.de/journals/JGAA/accepted/2004/
> > BoyerMyrvold2004.8.3.pdf)
>
> I've been digging into your planar graphs suite a bit, and I am very
> impressed.  I would love to see this in the BGL.
>
> Just a few documentation nits:
>
>         - PlanarEmbedding: This construct description should be its own
> page. Likewise for AddEdgeVisitor.
>         - GridPositionMap is the same as the PositionMap used by the layout
> routines in the BGL, e.g., fruchterman_reingold_force_directed_layout
>         - I think the discussion of planar graphs would benefit from a
> paragraph or two that describes your approach to dealing with planar
> embeddings in the BGL
>         - Everything paragraph and title in planar_graphs.html is centered
> (I'm using Safari); that should all be left-justified (which we do
> throughout the BGL).
>
> Since you already have read/write permission to the Boost
> repositories, please go ahead and integrate your planar graphs suite
> into the BGL at your earliest convenience, so that we can put it into
> Boost 1.35.0. Great work!

Hi Doug,

Ugh - I certainly didn't mean to center an entire page! Thanks for the
comments - I'll do another round of clean-up, including addressing the
above comments, and then commit.

One thing though - the GridPositionMap concept is really a refinement
of the PositionMap concept, since the positions it maps to are
guaranteed to be "grid points" - in this case, non-negative integers,
whereas the PositionMap seems to map to real numbers. Or is this too
trivial a distinction?

Regards,
Aaron