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

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-07-02 22:00:20

On 7/2/07, Jens Müller <jens.mueller_at_[hidden]> wrote:
> Aaron Windsor wrote:
> > I've put two sets of files in the vault under Home/Algorithms/graph: the
> > first is called planar_graphs.zip (also planar_graphs.tar.gz) and contains
> > the .hpp files, the documentation, and the examples. The second is called
> > planar_graph_testing.zip (also planar_graph_testing.tar.gz) and contains
> > over 1000 test graphs and a small program that can be compiled to give an
> > example of how these planar graph tools can be used. I'd appreciate any
> > comments!
>
>
> 1. It would be nice if bidirectional graphs could be supported as well.

Hi Jens,

Thanks for taking a look at my implementation. Yes, it would be nice
if bidirectional graphs were supported - they should be, and if it
doesn't turn out to be too much trouble, I'd like to support them.
I'll check on this when I have a little more time over the next couple
of days.

>
> 2. I have an (directed) graph which should be planar:
>
>       http://i11www.iti.uni-karlsruhe.de/~jmueller/100x250.graphml
>
>    I read it into a LEDA graph using the GraphML reader from graph-tool.
>    LEDA confirms that the graph is indeed planar.
>
>    To test it with your implementation, I changed it to undirected
>
>    edges:
>
> http://i11www.iti.uni-karlsruhe.de/~jmueller/100x250-undirected.graphml
>
>    I read it into a boost::adjacency_list with undirectedS
> directionality (instead of bidirectionalS which I would be using
> normally), and boyer_myrvold_planarity_test returns false ...
>
> Maybe you can take a look at the graph?

It's because you've got parallel edges - each edge is repeated twice
(for example, {n0,n2} shows up as source=n0, target=n2 and source=n2,
target=n0). I cleaned up the file and ran it through my code and it
was recognized as a planar graph.

> 3. What is your implementation doing when the graph is not undirected or
> when there are self-loops?

It's undefined on anything that isn't an undirected graph with no
self-loops and no parallel edges. The Boyer-Myrvold algorithm relies
on several computations on an undirected DFS tree like lowpoint, least
ancestor, and the full suite of planar testing/embedding/drawing
algorithms rely on some algorithms that are only defined on undirected
graphs, like testing simple connectivity and finding biconnected
components. This is a case when it would be nice to have some adapters
in the BGL to treat directed graphs as undirected or vise-versa.

Regards,
Aaron