
Boost : 
From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 20070702 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.unikarlsruhe.de/~jmueller/100x250.graphml
>
> I read it into a LEDA graph using the GraphML reader from graphtool.
> LEDA confirms that the graph is indeed planar.
>
> To test it with your implementation, I changed it to undirected
>
> edges:
>
> http://i11www.iti.unikarlsruhe.de/~jmueller/100x250undirected.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 selfloops?
It's undefined on anything that isn't an undirected graph with no
selfloops and no parallel edges. The BoyerMyrvold 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 viseversa.
Regards,
Aaron
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk